<s>关于_p 二_m 叉_q 链_n 表_n 的_u 非_h 递_vn 归_vn 先序_n 遍历_v 输出_vn 问题_n ，_w 输出_v 的_u 时候_n 出_v 问题_n 了_y ，_w 请_v 大神_r 指点_v 一_m 二_m ！_w</s><s>！！_w</s>
<s>引用_v 1_m 楼_n zhao4zhong1_nx 的_u 回复_vn :_w 仅_d 供_v 参考_v ：_w #_q include_nx <_w locale_nx ._w h_nx >_w #_q include_nx <_w stdio_nx ._w h_nx >_w #_q include_nx <_w stdlib_nx ._w h_nx >_w #_q include_nx <_w malloc_nx ._w h_nx >_w typedef_nx struct_nx BiTNode_nx {_w /_w /_w 二_m 叉_n 树_n 结_n 点_n char_nx data_n ;_w /_w /_w 数据_n struct_nx BiTNode_nx *_w lchild_nx ,_w *_w rchild_nx ;_w /_w /_w 左右_f 孩子_n 指针_n }_w BiTNode_nx ,_w *_w BiTree_nx ;_w int_nx nn_nx =_w 0_m ;_w int_nx CreateBiTree_nx (_w BiTree_nx *_w T_nx )_w {_w /_w /_w 按_p 先序_n 序列_n 创建_v 二_m 叉_n 树_n char_nx data_nx ;_w scanf_nx (_w "_w %_w c_nx "_w ,_w &_w data_nx )_w ;_w /_w /_w 按_p 先序_n 次序_n 输入_v 二_m 叉_n 树_n 中_f 结_n 点_n 的_u 值_n （_w 一_m 个_q 字符_n ）_w ，_w ‘_w #_n ’_w 表示_v 空_a 树_n if_nx (_w data_nx =_w =_w '_w #_n '_w )_w {_w *_w T_nx =_w NULL_nx ;_w }_w else_nx {_w *_w T_nx =_w (_w BiTree_nx )_w malloc_nx (_w sizeof_nx (_w BiTNode_nx )_w )_w ;_w nn_nx +_w +_w ;_w (_w *_w T_nx )_w -_w >_w data_nx =_w data_nx ;_w /_w /_w 生成_v 根_n 结点_n CreateBiTree_nx (_w &_w (_w *_w T_nx )_w -_w >_w lchild_nx )_w ;_w /_w /_w 构造_n 左子_n 树_n CreateBiTree_nx (_w &_w (_w *_w T_nx )_w -_w >_w rchild_nx )_w ;_w /_w /_w 构造_n 右子_f 树_n }_w return_v 0_m ;_w }_w void_n Visit_n (_w BiTree_nx T_nx )_w {_w /_w /_w 输出_v if_nx (_w T_nx -_w >_w data_nx !_w =_w '_w #_q '_w )_w {_w printf_nx (_w "_w %_w c_nx "_w ,_w T_nx -_w >_w data_nx )_w ;_w }_w }_w void_n PreOrder_n (_w BiTree_nx T_nx )_w {_w /_w /_w 先序_n 遍历_v if_r (_w T_nx !_w =_w NULL_nx )_w {_w Visit_n (_w T_n )_w ;_w /_w /_w 访问_v 根节点_n PreOrder_nx (_w T_nx -_w >_w lchild_nx )_w ;_w /_w /_w 访问_v 左子_f 结点_n PreOrder_nx (_w T_nx -_w >_w rchild_nx )_w ;_w /_w /_w 访问_v 右子_f 结_n 点_n }_w }_w void_n InOrder_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 中序_n 遍历_v if_nx (_w T_nx !_w =_w NULL_nx )_w {_w InOrder_nx (_w T_nx -_w >_w lchild_nx )_w ;_w /_w /_w 访问_v 左子_f 结点_n Visit_nx (_w T_nx )_w ;_w /_w /_w 访问_v 根节点_n InOrder_nx (_w T_nx -_w >_w rchild_nx )_w ;_w /_w /_w 访问_v 右子_f 结点_n }_w }_w void_n PostOrder_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 后序_n 遍历_v if_nx (_w T_nx !_w =_w NULL_nx )_w {_w PostOrder_nx (_w T_nx -_w >_w lchild_nx )_w ;_w /_w /_w 访问_v 左子_f 结点_n PostOrder_nx (_w T_nx -_w >_w rchild_nx )_w ;_w /_w /_w 访问_v 右子_n 结点_n Visit_nx (_w T_nx )_w ;_w /_w /_w 访问_v 根节点_n }_w }_w void_n PreOrder2_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 先序_n 遍历_v (_w 非_d 递归_v )_w /_w /_w 访问_v T_nx -_w >_w data_nx 后_f ，_w 将_p T_nx 入栈_v ，_w 遍历_v 左子树_n ；_w 遍历_v 完_l 左_v 子_n 树_l 返_l 回_v 时_l ，_v 栈_v 顶_v 元_v 素_v 应_v 为_v T_v ，_v 出_v 栈_v ，_v 再_n 先_l 序_n 遍_l 历_l T_v 的_l 右子_v 树_v 。_v</s><s>BiTree_nx *_w stack_nx =_w (_w BiTree_nx *_w )_w malloc_nx (_w nn_nx *_w sizeof_nx (_w BiTree_nx )_w )_w ;_w int_nx sp_nx =_w 0_m ;_w BiTree_nx p_nx =_w T_nx ;_w /_w /_w p_nx 是_v 遍历_vn 指针_n while_nx (_w p_nx |_w |_w sp_nx )_w {_w /_w /_w 栈_Ng 不_d 空_a 或者_c p_nx 不_d 空_a 时_Ng 循环_v if_nx (_w p_nx !_w =_w NULL_nx )_w {_w stack_nx [_w sp_nx ]_w =_w p_nx ;_w sp_nx +_w +_w ;_w /_w /_w 存入_v 栈_Ng 中_f printf_nx (_w "_w %_w c_nx "_w ,_w p_nx -_w >_w data_nx )_w ;_w /_w /_w 访问_v 根_n 节_n 点_n p_nx =_w p_nx -_w >_w lchild_nx ;_w /_w /_w 遍历_v 左子_f 树_n }_w else_nx {_w sp_nx -_w -_w ;_w p_nx =_w stack_nx [_w sp_nx ]_w ;_w /_w /_w 退_v 栈_Ng p_nx =_w p_nx -_w >_w rchild_nx ;_w /_w /_w 访问_v 右_f 子_n 树_n }_w }_w free_nx (_w stack_nx )_w ;_w }_w void_n InOrder2_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 中序_b 遍历_vn (_w 非_d 递_v 归_v )_w /_w /_w T_nx 是_v 要_v 遍历_v 树_n 的_u 根_n 指针_n ，_w 中序_b 遍历_vn 要求_v 在_p 遍历_v 完_v 左_f 子_n 树_n 后_f ，_w 访问_v 根_n ，_w 再_d 遍历_v 右_f 子_Ng 树_n 。_w</s><s>//_w 先_d 将_p T_nx 入_v 栈_Ng ，_w 遍历_v 左子树_n ；_w 遍历_v 完_v 左子树_n 返回_v 时_Ng ，_w 栈_Ng 顶_f 元素_n 应_v 为_v T_nx ，_w 出栈_v ，_w 访问_v T_nx -_w >_w data_nx ，_w 再_d 中序_b 遍历_v T_nx 的_u 右_f 子_Ng 树_n 。_w</s><s>BiTree_nx *_w stack_nx =_w (_w BiTree_nx *_w )_w malloc_n (_w nn_nx *_w sizeof_nx (_w BiTree_nx )_w )_w ;_w int_nx sp_nx =_w 0_m ;_w BiTree_nx p_nx =_w T_nx ;_w /_w /_w p_nx 是_v 遍历_vn 指针_n while_nx (_w p_nx |_w |_w sp_nx )_w {_w /_w /_w 栈_Ng 不_d 空_a 或者_c p_nx 不_d 空_a 时_Ng 循环_v if_nx (_w p_nx !_w =_w NULL_nx )_w {_w stack_nx [_w sp_nx ]_w =_w p_nx ;_w sp_nx +_w +_w ;_w /_w /_w 存入_v 栈_Ng 中_f p_nx =_w p_nx -_w >_w lchild_nx ;_w /_w /_w 遍历_v 左子_n 树_n }_w else_nx {_w sp_nx -_w -_w ;_w p_nx =_w stack_nx [_w sp_nx ]_w ;_w /_w /_w 退栈_v printf_nx (_w "_w %_w c_nx "_w ,_w p_nx -_w >_w data_nx )_w ;_w p_nx =_w p_nx -_w >_w rchild_nx ;_w /_w /_w 访问_v 右子_n 树_n }_w }_w free_nx (_w stack_nx )_w ;_w }_w typedef_nx struct_nx BiTNodePost_nx {_w BiTree_nx biTree_nx ;_w char_nx tag_nx ;_w }_w BiTNodePost_nx ,_w *_w BiTreePost_nx ;_w void_nx PostOrder2_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 后_f 序_n 遍历_v (_w 非_d 递_v 归_v )_w BiTreePost_nx *_w stack_nx =_w (_w BiTreePost_nx *_w )_w malloc_nx (_w nn_nx *_w sizeof_nx (_w BiTreePost_nx )_w )_w ;_w int_nx sp_nx =_w 0_m ;_w BiTree_nx p_nx =_w T_nx ;_w /_w /_w p_nx 是_v 遍历_vn 指针_n BiTreePost_nx BT_nx ;_w while_nx (_w p_nx !_w =_w NULL_nx |_w |_w sp_nx )_w {_w /_w /_w 栈_Ng 不_d 空_a 或者_c p_nx 不_d 空_a 时_Ng 循环_v while_nx (_w p_nx !_w =_w NULL_nx )_w {_w /_w /_w 遍历_v 左子_n 树_n BT_nx =_w (_w BiTreePost_nx )_w malloc_nx (_w sizeof_nx (_w BiTNodePost_nx )_w )_w ;_w BT_nx -_w >_w biTree_nx =_w p_nx ;_w BT_nx -_w >_w tag_n =_w '_w L_nx '_w ;_w /_w /_w 访问_v 过_u 左子_n 树_n stack_nr [_w sp_nx ]_w =_w BT_nx ;_w sp_nx +_w +_w ;_w /_w /_w 存入_v 栈_Ng 中_f p_nx =_w p_nx -_w >_w lchild_nx ;_w }_w while_nx (_w sp_nx &_w &_w (_w stack_nr [_w sp_nx -_w 1_m ]_w )_w -_w >_w tag_nx =_w =_w '_w R_nx '_w )_w {_w /_w /_w 左_f 右子_n 树_n 访问_v 完毕_v 访问_v 根_n 节_n 点_n sp_nx -_w -_w ;_w BT_nx =_w stack_nx [_w sp_nx ]_w ;_w /_w /_w 退_v 栈_Ng printf_nx (_w "_w %_w c_nx "_w ,_w BT_nx -_w >_w biTree_nx -_w >_w data_nx )_w ;_w free_nx (_w BT_nx )_w ;_w }_w if_nx (_w sp_nx )_w {_w /_w /_w 遍历_v 右子_n 树_n BT_nx =_w stack_nx [_w sp_nx -_w 1_m ]_w ;_w BT_nx -_w >_w tag_nx =_w '_w R_nx '_w ;_w /_w /_w 访问_v 过_u 右子_n 树_n p_nx =_w BT_nx -_w >_w biTree_nx ;_w p_nx =_w p_nx -_w >_w rchild_nx ;_w }_w }_w free_nx (_w stack_nx )_w ;_w }_w void_n LevelOrder_nx (_w BiTree_nx T_nx )_w {_w /_w /_w 层次_n 遍历_v BiTree_nx p_nx ;_w BiT_nx ree_nx *_w queue_n ;_w int_nx h_nx =_w 0_m ,_w t_nx =_w 0_m ,_w n_nx =_w 0_m ;_w if_nx (_w T_nx =_w =_w NULL_nx )_w return_nx ;_w p_nx =_w T_nx ;_w queue_n =_w (_w BiTree_nx *_w )_w malloc_nx (_w nn_nx *_w sizeof_nx (_w BiTree_nx )_w )_w ;_w queue_n [_w t_nx ]_w =_w p_nx ;_w t_nx =_w (_w t_nx +_w 1_m )_w %_w 10_m ;_w n_nx +_w +_nx ;_w /_w /_w 根_p 节点_n 入队_v while_nx (_w n_nx )_w {_w /_w /_w 队列_n 不_d 空_a 循环_v p_nx =_w queue_nx [_w h_nx ]_w ;_w /_w /_w 对头_a 元素_n 出队_v printf_nx (_w "_w %_w c_nx "_w ,_w p_nx -_w >_w data_nx )_w ;_w /_w /_w 访问_v p_nx 指向_v 的_u 结点_n h_nx =_w (_w h_nx +_w 1_m )_w %_w 10_m ;_w n_nx -_w -_w ;_w /_w /_w 退出_v 队列_n if_nx (_w p_nx -_w >_w lchild_nx !_w =_w NULL_nx )_w {_w /_w /_w 左子_n 树_n 不_d 空_a ，_w 将_p 左子_n 树_n 入队_v queue_nx [_w t_nx ]_w =_w p_nx -_w >_w lchild_nx ;_w t_nx =_w (_w t_nx +_w 1_m )_w %_w 10_m ;_w n_nx +_w +_w ;_w }_w if_nx (_w p_nx -_w >_w rchild_nx !_w =_w NULL_nx )_w {_w /_w /_w 右子_n 树_n 不_d 空_a ，_w 将_p 右子_n 树_n 入队_v que_nx ue_nx [_w t_nx ]_w =_w p_nx -_w >_w rchild_nx ;_w t_nx =_w (_w t_nx +_w 1_m )_w %_w 10_m ;_w n_nx +_w +_w ;_w }_w }_w free_n (_w queue_nx )_w ;_w }_w int_nx main_nx (_w )_w {_w BiTree_nx T_nx ;_w setlocale_nx (_w LC_nx __w ALL_v ,_w "_w chs_nx "_w )_w ;_w CreateBiTree_nx (_w &_w T_nx )_w ;_w printf_nx (_w "_w 先序_n 遍历_vn ：_w "_w )_w ;_w PreOrder_n (_w T_nx )_w ;_w printf_nx (_w "_w \_w n_n "_w )_w ;_w printf_nx (_w "_w 先序_n 遍历_vn (_w 非_d 递_v 归_v )_w ：_w "_w )_w ;_w PreOrder2_n (_w T_nx )_w ;_w printf_nx (_w "_w \_m n_n "_w )_w ;_w printf_nx (_w "_w \_w n_nx "_w )_w ;_w printf_nx (_w "_w 中序_b 遍历_vn ：_w "_w )_w ;_w InOrder_nx (_w T_nx )_w ;_w printf_nx (_w "_w \_m n_n "_w )_w ;_w printf_nx (_w "_w 中序_b 遍历_vn (_w 非_d 递_v 归_v )_w ：_w "_w )_w ;_w InOrder2_n (_w T_nx )_w ;_w printf_nx (_w "_w \_m n_n "_w )_w ;_w printf_nx (_w "_w \_w n_n "_w )_w ;_w printf_nx (_w "_w 后_f 序_n 遍历_vn ：_w "_w )_w ;_w PostOrder_n (_w T_nx )_w ;_w printf_nx (_w "_w \_w n_n "_w )_w ;_w printf_nx (_w "_w 后_f 序_n 遍历_vn (_w 非_d 递_v 归_v )_w ：_w "_w )_w ;_w PostOrder2_n (_w T_n )_w ;_w printf_n (_w "_w \_m n_n "_w )_w ;_w printf_nx (_w "_w \_m n_n "_w )_w ;_w printf_n (_w "_w 层次_n 遍历_vn ：_w "_w )_w ;_w LevelOrder_n (_w T_n )_w ;_w printf_n (_w "_w \_m n_n "_w )_w ;_w return_v 0_m ;_w }_w /_w /_w ABC_nx #_w #_w DE_nx #_w G_nx #_n #_w F_nx #_n #_w #_n /_w /_w 先序_n 遍历_vn ：_w A_nx B_j C_r D_m E_r G_r F_nx /_w /_w 先序_n 遍历_vn (_w 非_d 递_v 归_v )_w ：_w A_nx B_j C_nx D_m E_nx G_r F_r /_w /_w /_w /_w 中_f 序_n 遍历_vn ：_w C_nx B_j E_nx G_nx D_m F_r A_r /_w /_w 中序_a 遍历_vn (_w 非_d 递_v 归_v )_w ：_w C_nx B_j E_nx G_m D_m F_r A_r /_w /_w /_w /_w 后_f 序_n 遍历_vn ：_w C_nx G_j E_nx F_r D_m B_n A_r /_w /_w 后_f 序_n 遍历_vn (_w 非_d 递_v 归_v )_w ：_w C_nx G_j E_nx F_r D_nx B_j A_r /_w /_w /_w /_w 层次_n 遍历_vn ：_w A_nx B_j C_nx D_m E_nx F_r G_j /_w /_w /_w /_w /_w A_r /_w /_w /_w /_w /_w /_w /_w B_j /_w /_w /_w /_w \_w /_w /_w /_w C_nx D_r /_w /_w /_w /_w \_w /_w /_w /_w E_r F_r /_w /_w /_w \_w /_w /_w /_w G_m 谢谢_v 赵_nr 4_m 老师_n 指点_v</s>
