二叉树非递归遍历算法
Bob
两种二叉树非递归遍历实现的比较分析，先序和中序实现思路基本一样，主要区别是对根节点的访问时机的不同。第一种实现简介，第二种主要是算法分析清晰。
第一种：
先序遍历
void preorder(btree *bt)
{
btree *p,
*stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(bt != NULL)//先判断是否为空树
{
stack[top] = bt; //根结点入栈
while(top >= 0)
{
p = stack[top--]; //栈顶元素出栈
printf("%d", p->data);//输出该结点
if(p->rchild != NULL)
//如果该结点有右孩子，将右孩子入栈
{
stack[++top] = p->rchild;
}
if(p->lchild != NULL)
//如果该结点有左孩子，将左孩子入栈，按照后入先出原则，左孩子先出栈
{
stack[++top] = p->lchild;
}
}
}
}
或者：
void preorder(btree *bt)
{
btree *p,
*stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(bt != NULL)//先判断是否为空树
{
p = bt;
while (p || top > 0)
{
if (p)
{
stack[top++] = p;
printf("%c", p->data);//输出该结点
p = p->lchild;
}
else
{
p = stack[--top]; //栈顶元素出栈
p = p->rchild;
}
}
}
}
中序遍历
void inorder(btree *bt)
{
btree *p=bt, *stack[MAX];
//p表示当前结点，栈stack[]用来存储结点
int top=0;
if(p != NULL) //先判断是否为空树
{
while(top >= 0)
{
if(p != NULL) //先处理结点的左孩子结点
{
stack[top++] = p; //当前结点入栈
p = p->lchild; //寻找左孩子结点
}
else //找到最左边的孩子结点后
{
if(top == 0)
//表示全部元素均已输出，结束输出
break;
p = stack[--top];//栈顶元素出栈
printf("%d", p->data); //输出该结点
p = p->rchild; //处理其右孩子结点
}
}
}
}
或者：
void inorder(btree *bt)
{
btree *p=bt,
*stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int top=-1;
do
{
while(p !=
NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
p = stack[top--];//栈顶元素出栈
printf("%d", p->data); //输出该结点
p = p->rchild; //处理其右孩子结点
}
} while((p != NULL)||(top >= 0));
}
后序遍历
void postorder(btree *bt)
{
btree *p=bt,
*stack[MAX];//p表示当前结点，栈stack[]用来存储结点
int tag[MAX];
int top=-1;
do
{
while(p !=
NULL)//先处理结点的左孩子结点，把所有左孩子依次入栈
{
stack[++top] = p;
tag[top] = 0;
p = p->lchild;
}
if(top >= 0) //所有左孩子处理完毕后
{
if(!tag[top])
//如果当前结点的右孩子还没被访问
{
p = stack[top];//输出栈顶结点 ，但不退栈
，因为要先输出其孩子结点
p = p->rchild; //处理其右孩子结点
tag[top] = 1;
//表示栈中top位置存储的结点的右孩子被访问过了，下次轮到它退栈时可直接输出
}
else //如果该结点的左右孩子都被访问过了
{
printf("%d", stack[top--]->data);
//栈顶元素出栈，输出该结点，此时结点p指向NULL
}
}
} while((p != NULL)||(top >= 0));
}
第二种：
1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
//通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild;
//通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data);
//tag为R，表示右子树访问完毕，故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
=====================================