后序遍历二叉树的非递归算法
1. 设一棵二叉树的中序遍历结果为DBEAFC,前序遍历的结果为ABDECF,则后序遍历结果为
综述：依据前序遍历序列可确定根结点为A；再依据中序巧御腊遍历序列可知其左子树由DBE构成，右子树为FC；又由左子树的前序遍历序列可知其根结点为B，由中序遍历序列可知其左子树为D，右子拆厅树由E构成。同理推算FC的排列顺序，在草稿纸上画出树的结构，得出答案为:DEBFCA。
编程：
编程是编定程序的中文简称，就是让计算机代码解决某个问题，对某个计算体系规定一定的运算方式，使计算体系按照该计算方式运行，并最终得到相应结果的过程。为了使计算机孝滑能够理解人的意图，人类就必须将需解决的问题的思路、方法和手段通过计算机能够理解的形式告诉计算机，使得计算机能够根据人的指令一步一步去工作，完成某种特定的任务。
2. c++ 采用二叉链表作存储结构，实现二叉树非递归后序遍历算法
链接存储的二叉树类型和结构定义如下:
typedef
struct
bnode
{
ElemType
data;
struct
bnode
*lchild,
*rchild;
}
btree;
后序遍历
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));
}
3. 后序遍历（ 用递归和非递归的方法一起都要）
我们的数据结构实验也是这题，需要我把我的实验报告给你参考下么！
我这里就只发这部分的代码。
Status PreOrderTraverse(BiTree T)
{
//先序遍历二叉树T的递归算法
if (T)
{
printf("%d ",T->data);
if(T->lchild) PreOrderTraverse(T->lchild);
if(T->rchild) PreOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status PreOrder(BiTree T)
{
//先序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
if(T)
{
printf("%d ",T->data);
push(T);
T=T->lchild;
}
else
{
T=(BiTree)pop();
T=T->rchild;
}
}
}
Status InOrderTraverse(BiTree T)
{
//中序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) InOrderTraverse(T->lchild);
printf("%d ",T->data);
if (T->rchild) InOrderTraverse(T->rchild);
return FALSE;
}
else return OK;
}
Status InOrder(BiTree T)
{
//中序遍历二叉树T的非递归算法
while(!(T==NULL&&top==NULL))
{
while(T)
{
push(T);
T=T->lchild;
}
T=(BiTree)pop();
printf("%d ",T->data);
T=T->rchild;
}
}
Status PostOrderTraverse(BiTree T)
{
//后序遍历二叉树T的递归算法
if (T)
{
if (T->lchild) PostOrderTraverse(T->lchild);
if (T->rchild) PostOrderTraverse(T->rchild);
printf("%d ",T->data);
return FALSE;
}
else return OK;
}
Status PostOrder(BiTree T)
{
//后序遍历二叉树T的递归算法
unsigned sign;//记录结点从栈中弹出的次数
while(!(T==NULL&&top==NULL))
{
if(T)
{
push(T);//第一次遇到结点T时压入其指针
push(1);//置标志为1
T=T->lchild;
}
else
{
while(top)
{
sign=pop();
T=(BiTree)pop();
if(1==sign)//表示走过T的左子树
{
push(T);
push(2);
T=T->rchild;
break;
}
else
{
if(2==sign)//表示T的左右子树都已走过
{
printf("%d ",T->data);
T=NULL;
}
}
}
}
}
}
另外,团IDC网上有许多产品团购,便宜有口碑
4. 二叉树的遍历非递归算法中应注意哪些问题
先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T
!=
NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空指灶握。
问题：如何用栈来保存信息，使得在先序遍历过左子树后唯庆，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T->data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T->data后，将T->rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T->rchild，出栈，遍历以该指针为根的子树。
【算法1】
void
PreOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
基于方法一，流程图如右，当型循环辩帆
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)){
while
(
T
!=
NULL
){
Visit(T->data)
;
Push(S,T);
T
=
T->lchild;
}
if(
!StackEmpty(S)
){
Pop(S,T);
T
=
T->rchild;
}
}
}
【算法2】
void
PreOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
基于方法二，流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Visit(T->data);
Push(S,
T->rchild);
T
=
T->lchild;
}
if
(
!StackEmpty(S)
){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T->data，再中序遍历T的右子树。
【算法】
void
InOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Push(S,T);
T
=
T->lchild;
}
if(
!StackEmpty(S)
){
Pop(S,
T);
Visit(T->data);
T
=
T->rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。
typedef
struct
stackElement{
Bitree
data;
char
tag;
}stackElemType;
【算法】
void
PostOrder(BiTree
T,
Status
(
*Visit
)
(ElemType
e))
{
//
流程图如右，当型循环
InitStack(S);
while
(
T!=NULL
||
!StackEmpty(S)
){
while
(
T
!=
NULL
){
Push(S,T,0);
T
=
T->lchild;
}
while
(
!StackEmpty(S)
&&
GetTopTag(S)==1){
Pop(S,
T);
Visit(T->data);
}
if
(
!StackEmpty(S)
){
SetTopTag(S,
1);
//
设置栈顶标记
T
=
GetTopPointer(S);
//
取栈顶保存的指针
T
=
T->rchild;
}else
break;
}
}
5. 2、假设二叉树采用链接存储方式存储，编写一个二叉树后序遍历的非递归算法。
假设二叉树采用链接方式存储厅猛，编写一个对二叉树进行扮弊桥中序遍历的递归和卜手非递归后序遍历： var root,i,t,tl,tr,n:byte; depth,l,r:array[1..100]
6. 【高手快来】不用栈实现二叉树的后序非递归（C）
以下是我写的二叉树的头文件,有你想要的(不失一般性,我用的是模板).里面有非递归后序遍历.栈和队列的头文件也在.用main()举了一个例子,自己看吧.
//****************BiTree.h
#ifndefB_I_T_R_E_E
#defineB_I_T_R_E_E
#include<iostream>
//#include<conio.h>
#include"腊源stack.h"
#include"Lqueue.h"
usingnamespacestd;
template<classTElemType>
structBiTNode{
TElemTypedata;
BiTNode<TElemType>*lchild,*rchild;
};
template<classTElemType>
classBiTree
{
public:
voidCreateBiTree(BiTNode<TElemType>*&T);
voidPreOrderTraverse(BiTNode<TElemType>*T);
voidInOrderTraverse(BiTNode<TElemType>*T);
voidPostOrderTraverse(BiTNode<TElemType>*T);
voidLevelOrderTraverse(BiTNode<TElemType>卖局耐*T);
};
template<classTElemType>
voidBiTree<TElemType>::CreateBiTree(BiTNode<TElemType>*&T)
{
TElemTypech;
cout<<"请中春输入数据(-1表示空(非字符型)):"<<endl;
cin>>ch;
if(ch==-1)T=NULL;
else
{
if(!(T=(BiTNode<TElemType>*)malloc(sizeof(BiTNode<TElemType>))))exit(0);
T->data=ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
}
template<classTElemType>
//递归先序遍历
voidBiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType>*T)
{
if(T)
{
cout<<T->data<<endl;
PreOrderTraverse(T->lchild);
PreOrderTraverse(T->rchild);
}
}//PreOrderTraverse
/*非递归先序遍历
voidBiTree<TElemType>::PreOrderTraverse(BiTNode<TElemType>*T)
{
BiTNode<TElemType>*p=T;
stack<BiTNode<TElemType>*>S;
S.InitStack();
while(p||!S.StackEmpty())
{
if(p)
{
S.Push(p);
cout<<p->data<<endl;
p=p->lchild;
}
else
{
S.Pop(p);
p=p->rchild;
}
}
S.DestroyStack();
}*/
//递归中序遍历
template<classTElemType>
voidBiTree<TElemType>::InOrderTraverse(BiTNode<TElemType>*T)
{
if(T)
{
InOrderTraverse(T->lchild);
cout<<T->data<<endl;
InOrderTraverse(T->rchild);
}
}
//非递归中序遍历
/*voidBiTree<TElemType>::InOrderTraverse(BiTNode<TElemType>*T)
{
BiTNode<TElemType>*p=T;
stack<BiTNode<TElemType>*>S;
S.InitStack();
while(p||!S.StackEmpty())
{
if(p)
{
S.Push(p);
p=p->lchild;
}
else
{
S.Pop(p);
cout<<p->data<<endl;
p=p->rchild;
}
}
S.DestroyStack();
}*/
//递归后序遍历
template<classTElemType>
voidBiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType>*T)
{
if(T)
{
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
cout<<T->data<<endl;
}
}
//非递归后序遍历
/*voidBiTree<TElemType>::PostOrderTraverse(BiTNode<TElemType>*T)
{
BiTNode<TElemType>*p=T;
BiTNode<TElemType>*q=NULL;
stack<BiTNode<TElemType>*>S;
S.InitStack();
S.Push(p);
p=p->lchild;
while(!S.StackEmpty())
{
if(p)
{S.Push(p);p=p->lchild;}
else
{
S.GetTop(p);
p=p->rchild;
if(!p)
{
S.Pop(p);
cout<<p->data<<endl;
S.GetTop(q);
while(q&&p==q->rchild)
{
S.Pop(p);
cout<<p->data<<endl;
S.GetTop(q);
//if(q==NULL)break;
}
if(q)
{
S.GetTop(q);
p=q->rchild;
}
}
}
}
S.DestroyStack();
}*/
//非递归层次遍历
template<classTElemType>
voidBiTree<TElemType>::LevelOrderTraverse(BiTNode<TElemType>*T)
{
Lqueue<BiTNode<TElemType>*>que;
que.InitQueue();
if(T)que.EnQueue(T);
while(!que.QueueEmpty())
{
que.GetHead(T);
if(T->lchild)que.EnQueue(T->lchild);
if(T->rchild)que.EnQueue(T->rchild);
que.DeQueue(T);
cout<<T->data<<endl;
}
que.DestroyQueue();
}
#endif
//**************BiTree.h
//****Lqueue.h
#ifndef_LQUEUE_H
#define_LQUEUE_H
#defineMAXQSIZE100
typedefintStatus;
template<classQElemType>
classLqueue
{
public:
voidInitQueue();
voidDestroyQueue();
voidClearQueue();
StatusQueueEmpty();
StatusQueueLength();
voidGetHead(QElemType&e);
voidEnQueue(QElemTypee);
voidDeQueue(QElemType&e);
private:
structSqQueue
{
QElemType*base;
intfront;
intrear;
};
SqQueueQ;
};
//********Lqueue.cpp********
template<classQElemType>
voidLqueue<QElemType>::InitQueue()
{
Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));
if(!Q.base)exit(0);
Q.front=Q.rear=0;
}
template<classQElemType>
voidLqueue<QElemType>::DestroyQueue()
{
free(Q.base);
}
template<classQElemType>
voidLqueue<QElemType>::ClearQueue()
{
Q.front=Q.rear=0;
}
template<classQElemType>
StatusLqueue<QElemType>::QueueEmpty()
{
if(Q.front==Q.rear)return1;
return0;
}
template<classQElemType>
StatusLqueue<QElemType>::QueueLength()
{
return(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}
template<classQElemType>
voidLqueue<QElemType>::GetHead(QElemType&e)
{
if(Q.front==Q.rear)e=NULL;
else
{
e=Q.base[Q.front];
}
}
template<classQElemType>
voidLqueue<QElemType>::EnQueue(QElemTypee)
{
if((Q.rear+1)%MAXQSIZE==Q.front)cout<<"ERROR"<<endl;
else
{
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXQSIZE;
}
}
template<classQElemType>
voidLqueue<QElemType>::DeQueue(QElemType&e)
{
if(Q.front==Q.rear)cout<<"ERROR"<<endl;
else
{
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXQSIZE;
}
}
//******************Lqueue.cpp***************
#endif//*****Lqueue.h********
//*****stack.h
#ifndef_STACK_H
#define_STACK_H
#defineSTACK_INIT_SIZE100
#defineSTACKINCREMENT10
typedefintStatus;
template<classQElemType>
classstack
{
public:
voidInitStack();
voidDestroyStack();
voidClearStack();
StatusStackEmpty();
StatusStackLength();
voidGetTop(QElemType&e);
voidPush(QElemTypee);
voidPop(QElemType&e);
private:
structSqStack{
QElemType*base;
QElemType*top;
intstacksize;
}S;
};
//******stack.cpp------
template<classQElemType>
voidstack<QElemType>::InitStack()
{
S.base=(QElemType*)malloc(STACK_INIT_SIZE*sizeof(QElemType));
if(!S.base)exit(0);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
}
template<classQElemType>
voidstack<QElemType>::DestroyStack()
{
free(S.base);
}
template<classQElemType>
voidstack<QElemType>::ClearStack()
{
S.top=S.base;
}
template<classQElemType>
Statusstack<QElemType>::StackEmpty()
{
if(S.top==S.base)return1;
elsereturn0;
}
template<classQElemType>
Statusstack<QElemType>::StackLength()
{
return(S.top-S.base);
}
template<classQElemType>
voidstack<QElemType>::GetTop(QElemType&e)
{
if(S.top!=S.base)
e=*(S.top-1);
elsee=NULL;
}
template<classQElemType>
voidstack<QElemType>::Push(QElemTypee)
{
if(S.top-S.base>=S.stacksize)
{
S.base=(QElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(QElemType));
if(!S.base)exit(0);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
}
template<classQElemType>
voidstack<QElemType>::Pop(QElemType&e)
{
if(S.top==S.base)e=NULL;
else
e=*--S.top;
}
//**********stack.cpp
#endif//stack.h****
//#include<iostream>
#include"BiTree.h"
//#include"stack.h"
//#include"Lqueue.h"
//usingnamespacestd;
intmain()
{
BiTree<int>tree;
BiTNode<int>*T=NULL;
tree.CreateBiTree(T);
tree.InOrderTraverse(T);
tree.PreOrderTraverse(T);
tree.PostOrderTraverse(T);
tree.LevelOrderTraverse(T);
return0;
}
新建3个头文件stack.h,Lqueue.h,BiTree.h
分别将各个头文件的内容拷到相应的地方.
新建C++Sourcefile
将main函数的内容拷入cpp文件.
运行时如输入1,2,4,-1,-1,5,-1,-1,3,-1,-1
相应的遍历结果会出现.
7. 二叉树的遍历算法
这里有二叉树先序、中序、后序三种遍历的非递归算法，此三个算法可视为标准算法。
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
8. c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等
#include<stdlib.h> // atoi()，exit()
#include<math.h> // 数学函数头文件，包括floor()，ceil()，abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果：构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树，如无左子树，则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树，如无右子树，则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1
// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数
// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树：\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树：\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树：\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
9. 后序遍历是什么
对于题图为后序遍历为：DECBA。
后序遍历（LRD）是二叉树遍历的一种，也叫做后根遍历、后序周游，可记做左右根。后序遍历有递归算法和非递核塌陆归算法两种。
后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、衫弊右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：
若二叉树为空则结束返回，
否则：
（1）后序遍历左子树
（2）后序遍历右子树（3）访问根结点
如右图所示二改顷叉树
后序遍历结果：DEBFCA
已知前序遍历和中序遍历，就能确定后序遍历。
10. 求二叉树的非递归后序遍历的c语言代码
#include<iostream>
#include<stdio.h>
#define N 10
using namespace std;
char *a;
typedef struct NODE{
char data;
struct NODE *lch, *rch,*parent;
} *BINTREE,Node;
void visit(char data){
printf("%5c",data);
}
void preorder(BINTREE T){ // 先根序周游
BINTREE stack[50];
BINTREE p;
p=T;
int s=0;
if(p==NULL)return;
while(1)
{ visit(p->data);
while(p->lch!=NULL) {
stack[++s]=p;
p=p->lch;
visit(p->data); }
// cout<<" "扮正<<s;
while(1)
{ if((p=p->rch)!=NULL)
break;
if(s==0)
return;
p=stack[s--];
}
}
}
void inorder(BINTREE T)//中根序周游
{
Node *stack[100];
int top=0;
stack[0]=T;
while(top>0 ||stack[top]!=NULL)
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
}
if(top>0)
{
printf("%5c",stack[--top]->data );
stack[top]=stack[top]->rch ;
}
}
}
void posorder1(BINTREE T)//后根序周游
{
Node *stack[100];
int top=0;
int tag[100];
tag[0]=0;
stack[0]=T;
do
{
while(stack[top]!=NULL)
{
stack[++top]=stack[top]->lch ;
tag[top]=0;
}
while(tag[top-1]==1)
printf("%5c",stack[--top]->data );
if(top>0)
{
stack[top]=stack[top-1]->rch ;
tag[top-1]=1;
tag[top]=0;
}
} while(top!=0);
}
BINTREE Create(){//先根序树的建立
BINTREE T;
char ch;
cin>>ch;
cout<<" ch="<<ch<<endl;
if(ch=='#')
T=NULL;
else{
if(!(T=(BINTREE )malloc(sizeof(Node))))
printf("Error!");
T->data=ch;
T->缺缺裤lch=Create();
T->rch=Create();
}
return T;
}
void main(){
freopen("D:\\input.txt","r",stdin);
BINTREE T;
T=Create();
cout<<伏简"先根序遍历 ";
preorder(T);
cout<<endl;
cout<<"中根序遍历 ";
inorder(T);
cout<<endl;
cout<<"后根序遍历 ";
posorder1(T);
cout<<endl;
cout<<endl;
}
在D盘建立一个input.txt的文件，输入数的内容，输入顺序为先序根遍历的顺序，叶子节点的left和right用#代替即可。