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

遍历前中后序和层次遍历"/>

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

#include<stdio.h>
#include<stack.c>
#include<stdbool.h>
#include<SquenceNode.c>#define MaxSize 20typedef 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);}}