关于 二 叉 链 表 的 非 递 归 先序 遍历 输出 问题 ， 输出 的 时候 出 问题 了 ， 请 大神 指点 一 二 ！ ！！
引用 1 楼 zhao4zhong1 的 回复 : 仅 供 参考 ： # include < locale . h > # include < stdio . h > # include < stdlib . h > # include < malloc . h > typedef struct BiTNode { / / 二 叉 树 结 点 char data ; / / 数据 struct BiTNode * lchild , * rchild ; / / 左右 孩子 指针 } BiTNode , * BiTree ; int nn = 0 ; int CreateBiTree ( BiTree * T ) { / / 按 先序 序列 创建 二 叉 树 char data ; scanf ( " % c " , & data ) ; / / 按 先序 次序 输入 二 叉 树 中 结 点 的 值 （ 一 个 字符 ） ， ‘ # ’ 表示 空 树 if ( data = = ' # ' ) { * T = NULL ; } else { * T = ( BiTree ) malloc ( sizeof ( BiTNode ) ) ; nn + + ; ( * T ) - > data = data ; / / 生成 根 结点 CreateBiTree ( & ( * T ) - > lchild ) ; / / 构造 左子 树 CreateBiTree ( & ( * T ) - > rchild ) ; / / 构造 右子 树 } return 0 ; } void Visit ( BiTree T ) { / / 输出 if ( T - > data ! = ' # ' ) { printf ( " % c " , T - > data ) ; } } void PreOrder ( BiTree T ) { / / 先序 遍历 if ( T ! = NULL ) { Visit ( T ) ; / / 访问 根节点 PreOrder ( T - > lchild ) ; / / 访问 左子 结点 PreOrder ( T - > rchild ) ; / / 访问 右子 结 点 } } void InOrder ( BiTree T ) { / / 中序 遍历 if ( T ! = NULL ) { InOrder ( T - > lchild ) ; / / 访问 左子 结点 Visit ( T ) ; / / 访问 根节点 InOrder ( T - > rchild ) ; / / 访问 右子 结点 } } void PostOrder ( BiTree T ) { / / 后序 遍历 if ( T ! = NULL ) { PostOrder ( T - > lchild ) ; / / 访问 左子 结点 PostOrder ( T - > rchild ) ; / / 访问 右子 结点 Visit ( T ) ; / / 访问 根节点 } } void PreOrder2 ( BiTree T ) { / / 先序 遍历 ( 非 递归 ) / / 访问 T - > data 后 ， 将 T 入栈 ， 遍历 左子树 ； 遍历 完 左 子 树 返 回 时 ， 栈 顶 元 素 应 为 T ， 出 栈 ， 再 先 序 遍 历 T 的 右子 树 。 BiTree * stack = ( BiTree * ) malloc ( nn * sizeof ( BiTree ) ) ; int sp = 0 ; BiTree p = T ; / / p 是 遍历 指针 while ( p | | sp ) { / / 栈 不 空 或者 p 不 空 时 循环 if ( p ! = NULL ) { stack [ sp ] = p ; sp + + ; / / 存入 栈 中 printf ( " % c " , p - > data ) ; / / 访问 根 节 点 p = p - > lchild ; / / 遍历 左子 树 } else { sp - - ; p = stack [ sp ] ; / / 退 栈 p = p - > rchild ; / / 访问 右 子 树 } } free ( stack ) ; } void InOrder2 ( BiTree T ) { / / 中序 遍历 ( 非 递 归 ) / / T 是 要 遍历 树 的 根 指针 ， 中序 遍历 要求 在 遍历 完 左 子 树 后 ， 访问 根 ， 再 遍历 右 子 树 。 // 先 将 T 入 栈 ， 遍历 左子树 ； 遍历 完 左子树 返回 时 ， 栈 顶 元素 应 为 T ， 出栈 ， 访问 T - > data ， 再 中序 遍历 T 的 右 子 树 。 BiTree * stack = ( BiTree * ) malloc ( nn * sizeof ( BiTree ) ) ; int sp = 0 ; BiTree p = T ; / / p 是 遍历 指针 while ( p | | sp ) { / / 栈 不 空 或者 p 不 空 时 循环 if ( p ! = NULL ) { stack [ sp ] = p ; sp + + ; / / 存入 栈 中 p = p - > lchild ; / / 遍历 左子 树 } else { sp - - ; p = stack [ sp ] ; / / 退栈 printf ( " % c " , p - > data ) ; p = p - > rchild ; / / 访问 右子 树 } } free ( stack ) ; } typedef struct BiTNodePost { BiTree biTree ; char tag ; } BiTNodePost , * BiTreePost ; void PostOrder2 ( BiTree T ) { / / 后 序 遍历 ( 非 递 归 ) BiTreePost * stack = ( BiTreePost * ) malloc ( nn * sizeof ( BiTreePost ) ) ; int sp = 0 ; BiTree p = T ; / / p 是 遍历 指针 BiTreePost BT ; while ( p ! = NULL | | sp ) { / / 栈 不 空 或者 p 不 空 时 循环 while ( p ! = NULL ) { / / 遍历 左子 树 BT = ( BiTreePost ) malloc ( sizeof ( BiTNodePost ) ) ; BT - > biTree = p ; BT - > tag = ' L ' ; / / 访问 过 左子 树 stack [ sp ] = BT ; sp + + ; / / 存入 栈 中 p = p - > lchild ; } while ( sp & & ( stack [ sp - 1 ] ) - > tag = = ' R ' ) { / / 左 右子 树 访问 完毕 访问 根 节 点 sp - - ; BT = stack [ sp ] ; / / 退 栈 printf ( " % c " , BT - > biTree - > data ) ; free ( BT ) ; } if ( sp ) { / / 遍历 右子 树 BT = stack [ sp - 1 ] ; BT - > tag = ' R ' ; / / 访问 过 右子 树 p = BT - > biTree ; p = p - > rchild ; } } free ( stack ) ; } void LevelOrder ( BiTree T ) { / / 层次 遍历 BiTree p ; BiT ree * queue ; int h = 0 , t = 0 , n = 0 ; if ( T = = NULL ) return ; p = T ; queue = ( BiTree * ) malloc ( nn * sizeof ( BiTree ) ) ; queue [ t ] = p ; t = ( t + 1 ) % 10 ; n + + ; / / 根 节点 入队 while ( n ) { / / 队列 不 空 循环 p = queue [ h ] ; / / 对头 元素 出队 printf ( " % c " , p - > data ) ; / / 访问 p 指向 的 结点 h = ( h + 1 ) % 10 ; n - - ; / / 退出 队列 if ( p - > lchild ! = NULL ) { / / 左子 树 不 空 ， 将 左子 树 入队 queue [ t ] = p - > lchild ; t = ( t + 1 ) % 10 ; n + + ; } if ( p - > rchild ! = NULL ) { / / 右子 树 不 空 ， 将 右子 树 入队 que ue [ t ] = p - > rchild ; t = ( t + 1 ) % 10 ; n + + ; } } free ( queue ) ; } int main ( ) { BiTree T ; setlocale ( LC _ ALL , " chs " ) ; CreateBiTree ( & T ) ; printf ( " 先序 遍历 ： " ) ; PreOrder ( T ) ; printf ( " \ n " ) ; printf ( " 先序 遍历 ( 非 递 归 ) ： " ) ; PreOrder2 ( T ) ; printf ( " \ n " ) ; printf ( " \ n " ) ; printf ( " 中序 遍历 ： " ) ; InOrder ( T ) ; printf ( " \ n " ) ; printf ( " 中序 遍历 ( 非 递 归 ) ： " ) ; InOrder2 ( T ) ; printf ( " \ n " ) ; printf ( " \ n " ) ; printf ( " 后 序 遍历 ： " ) ; PostOrder ( T ) ; printf ( " \ n " ) ; printf ( " 后 序 遍历 ( 非 递 归 ) ： " ) ; PostOrder2 ( T ) ; printf ( " \ n " ) ; printf ( " \ n " ) ; printf ( " 层次 遍历 ： " ) ; LevelOrder ( T ) ; printf ( " \ n " ) ; return 0 ; } / / ABC # # DE # G # # F # # # / / 先序 遍历 ： A B C D E G F / / 先序 遍历 ( 非 递 归 ) ： A B C D E G F / / / / 中 序 遍历 ： C B E G D F A / / 中序 遍历 ( 非 递 归 ) ： C B E G D F A / / / / 后 序 遍历 ： C G E F D B A / / 后 序 遍历 ( 非 递 归 ) ： C G E F D B A / / / / 层次 遍历 ： A B C D E F G / / / / / A / / / / / / / B / / / / \ / / / C D / / / / \ / / / E F / / / \ / / / G 谢谢 赵 4 老师 指点
