二叉树前序、中序、后序三种遍历的非递归算法

一。教科书标准算法
1.先序遍历非递归算法
void PreOrderUnrec(Bitree *t)
{
Stack s;
StackInit(s);
Bitree *p=t;

while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}

if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif

}//endwhile
}

2.中序遍历非递归算法
void InOrderUnrec(Bitree *t)
{
Stack s;
StackInit(s);
Bitree *p=t;

while (p!=NULL || !StackEmpty(s))
{
while (p!=NULL) //遍历左子树
{
push(s,p);
p=p->lchild;
}

if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif

}//endwhile
}

3.后序遍历非递归算法
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

二。前序最简洁算法
void PreOrderUnrec(Bitree *t)
{
Bitree *p;
Stack s;
s.push(t);

while (!s.IsEmpty())
{
s.pop(p);
visit(p->data);
if (p->rchild != NULL) s.push(p->rchild);
if (p->lchild != NULL) s.push(p->lchild);
}
}

三。后序算法之二
void BT_PostOrderNoRec(pTreeT root)
{
stack s;
pTreeT pre=NULL;

while ((NULL != root) || !s.empty())
{
if (NULL != root)
{
s.push(root);
root = root->left;
}
else
{
root = s.top();
if (root->right!=NULL && pre!=root->right)
{
root=root->right;
}
else
{
root=pre=s.top();
visit(root);
s.pop();
root=NULL;
}
}
}

}


一个比较容易理解的后序遍历:

void PostOrder(Bitree *t)
{
TreeNode *node = NULL,*last = NULL;
Stack s;
s,Init();
s.push(t);
while(!s.IsEmpty())
{
node = s.pop();
if(last == node->left || last == node->right)//左右子树已经访问完了，该访问根节点了
{
visit(node);
last = node;
}
else if(node->left || node->right) //

左右子树未访问，当前节点入栈，左右节点入栈
{
s.push(node);
if(node->right)
s.push(node->right);
if(node->left)
s.push(node->left);
}
else //当前节点为叶节点，访问
{
visit(node);
last = node;
}
}
}