後序遍歷二叉樹的非遞歸演算法
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用#代替即可。