二叉树的非递归遍历前中后序和层次遍历

#include<stdio.h> #include<stack.c> #include<stdbool.h> #include<SquenceNode.c> #define MaxSize 20 typedef struct TreeNode *BinTree; typedef BinTree Position; typedef int ElementType; //二叉树的链式存储结构 struct TreeNode { ElementType Data; BinTree Left; BinTree Right; BinTree IsFirst;//用于标志是否是第一次进栈 }; /** * 二叉树的中序遍历(非递归) * */ void InorderTraversal( BinTree BT) { BinTree T = BT; Stack S = CreateStack(MaxSize); while( T || !isEmpty( S ) ) { while( T ) { T->IsFirst = true; //一直向左并将沿途的结点压入堆栈 Push(S,T); T = T->Left; } if(!isEmpty(S)) { //左子树遍历完了,该弹出栈顶结点 T = Pop(S); printf("%d", T->Data); //左子树输出完了,转向右子树 T = T->Right; } } } /** * 先序遍历的非递归遍历算法 * */ void PreOrderTraversal( BinTree BT) { BinTree T = BT; Stack S = CreateStack(MaxSize); while( T || !isEmpty( S ) ) { while( T ) { //一直向左并将沿途的结点压入堆栈 Push(S,T); //第一次遇到这个结点就输出 printf("%d", T->Data); T = T->Left; } if(!isEmpty(S)) { //左子树遍历完了,该弹出栈顶结点 T = Pop(S); //左子树输出完了,转向右子树 T = T->Right; } } } /** * 后序遍历的非递归遍历算法 * */ void PostOrderTraversal( BinTree BT) { BinTree T = BT; Stack S = CreateStack(MaxSize); while( T || !isEmpty( S ) ) { while( T ) { T->IsFirst = true;//标记为第一次进栈 //一直向左并将沿途的结点压入堆栈 Push(S,T); T = T->Left; } if(!isEmpty(S)) { //左子树遍历完了,该弹出栈顶结点 T = Pop(S); if(T->IsFirst == true) { T->IsFirst = false; Push(S,T); T = T->Right; } else { printf("%d", T->Data); T = NULL; } } } } /** * 层次遍历 * */ void LevelOrderTraversal( BinTree BT) { Queue Q; BinTree T; if( !BT ) return; Q = CreateQueue( MaxSize ); Add(Q, BT); while( ! isEmpty(Q) ) { T = Delete(Q); printf("%d\n", T->Data); if(T->Left) Add(Q, T->Left); if(T->Right) Add(Q, T->Right); } }