實驗三? 二叉樹遍歷（遞歸算法和非遞歸算法）
一．實驗?zāi)康?/b>
1.掌握二叉樹的存儲結(jié)構(gòu)與基本操作
2.掌握二叉樹的遍歷算法
二．實驗要求與內(nèi)容
1. 建立二叉樹，采用遞歸的方式完成前炒刁、中琴儿、后三種遍歷立宜。（建立二叉樹的算法參考課本P174）
2. 建立二叉樹腻豌，采用非遞歸的方式完成前、中儡炼、后三種遍歷响牛。
三．實驗步驟
1．?dāng)?shù)據(jù)結(jié)構(gòu)
遞歸算法只需要定義一個結(jié)構(gòu)體儲存各個節(jié)點信息玷禽，而非遞歸算法需要多定義一個棧來儲存遍歷時的信息赫段。在非遞歸算法的后序遍歷中還需要創(chuàng)建一個一維數(shù)組用來做標(biāo)識結(jié)點的左右子樹樹否都遍歷過。詳細(xì)解釋請看附錄中結(jié)合代碼的解釋矢赁。
2．算法設(shè)計
遞歸算法根據(jù)不同的遍歷方式采取不同遞歸調(diào)用遍歷順序即可糯笙。
非遞歸算法
前序遍歷的核心思想：當(dāng)node所指的結(jié)點不為空時，訪問該結(jié)點即輸出該結(jié)點的信息并將該結(jié)點所在的鏈接點的地址進棧撩银，然后再將node指向該結(jié)點的左子樹给涕；當(dāng)node所指的結(jié)點為空時，則從棧中退出棧頂元素給node额获，然后將該node指向該結(jié)點的右孩子結(jié)點够庙。重復(fù)上述過程，直至node為NULL抄邀，并且棧也為空耘眨，遍歷結(jié)束。
中序遍歷的核心思想：當(dāng)node所指的結(jié)點不為空時撤摸，則將該結(jié)點所在的鏈接點的地址進棧，然后再將node指向該結(jié)點的左子樹褒纲；當(dāng)node所指的結(jié)點為空時准夷，則從棧中退出棧頂元素給node，訪問該結(jié)點即輸出該結(jié)點的信息莺掠，然后將該node指向該結(jié)點的右孩子結(jié)點衫嵌。重復(fù)上述過程，直至node為NULL彻秆，并且棧也為空楔绞，遍歷結(jié)束。
后序遍歷的核心思想：當(dāng)node指向某一個結(jié)點時唇兑，不能馬上對它進行訪問酒朵，而要先遍歷它的左子樹，因而要將該結(jié)點的地址進棧扎附，當(dāng)其左子樹遍歷完畢以后蔫耽，再次搜索要該結(jié)點時（該結(jié)點的地址通過退棧得到），還不能對它進行訪問留夜，還需要遍歷它的右子樹匙铡，所以，將該結(jié)點的地址再一次進棧碍粥。只有該結(jié)點的右子樹被遍歷以后回到該結(jié)點鳖眼，才訪問該結(jié)點，為了標(biāo)明某結(jié)點是否可以被訪問嚼摩，引入一個標(biāo)志變量標(biāo)明钦讳。
3．程序
void bulidtree(bitree &T)//二叉樹的建立（按照前序遍歷建立二叉樹）
{
? ? char c;
? ? cin>>c;
? ? if(c=='#')//判斷該節(jié)點是否存在
? ? ? ? T =NULL;
? ? else
? ? {
? ? ? ? T=new bitreenode;
? ? ? ? T->date=c;
? ? ? ? bulidtree(T->left);//建立左子樹
? ? ? ? bulidtree(T->right);//建立右子樹
? ? }
}
//中序后序的遞歸算法類似于前序只改變了輸出位置
void front(bitree T)//前序遍歷二叉樹
{
? ? if(T!=NULL)
? ? {
? ? ? ? cout<<T->date<<" ";
? ? ? ? front(T->left);
? ? ? ? front(T->right);
? ? }
}
//非遞歸前序遍歷矿瘦，中序遍歷類似于前序遍歷
void front1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL||!empty(s.top)){//當(dāng)結(jié)點為空并且棧也為空時退出
? ? ? ? ? ? while(node!=NULL){//當(dāng)結(jié)點不為空時輸出該結(jié)點并將該結(jié)點壓入棧并遍歷左子樹
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){//結(jié)點為NULL但是棧不為空
? ? ? ? ? ? ? ? node=pop(&s);//彈出棧頂元素并賦給node
? ? ? ? ? ? ? ? node=node->right;//遍歷結(jié)點的右子樹
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
//后序遍歷
?void back1(bitree T){
?int b[20];
?if(T){
?Stack s;
?init(s.top);
?bitree node =T;
?while(node!=NULL || !empty(s.top)){
?while(node!=NULL){
?push(&s,node);//第一次進棧
?b[s.top]=0;
?node=node->left;
?}
?node=pop(&s);
?int flag=b[s.top+1];
?if(flag==0){? //說明只進過一次
?push(&s,node);//第二次進棧
?b[s.top]=1;
?node=node->right;
?}
?else{? ? //已經(jīng)進過兩次棧，說明左右子樹都已經(jīng)遍歷過了
?printf("%c ",node->date);
?node=NULL;
?}
?}
?}
?}
4．程序調(diào)試
測試數(shù)據(jù)蜂厅、程序運行結(jié)果截圖?
四．結(jié)果與體會
該實驗的難點在于非遞歸算法的設(shè)計匪凡，剛開始的時候沒有想法，后面參考書上的方法發(fā)現(xiàn)可以用while或則do..while在一定程度上代替遞歸算法實現(xiàn)相同的目的掘猿，比如遞歸實現(xiàn)找到最左子樹可以用while(node->left!=NULL)實現(xiàn)病游。
五．源程序
另附
#include<iostream>
using namespace std;
typedef struct node{
? ? node *left;
? ? node *right;
? ? char date;
}bitreenode,*bitree;
typedef struct {
? ? bitree stack[100];
? ? int top;
}Stack;
void init(int &top){
? ? top=-1;
}
int full(int top){
? ? return top==99;
}
int empty(int top){
? ? return top==-1;
}
int push(Stack *s,bitree a){
? ? int top1=s->top;
? ? if(a==NULL)
? ? ? ? return 0;
? ? else
? ? {
? ? ? ? s->top++;
? ? ? ? s->stack[++top1]=a;
? ? ? ? return 1;
? ? }
}
bitree pop(Stack *s){
? ? int top1=s->top;
? ? if (top1!=-1){
? ? ? ? s->top--;
? ? ? ? return s->stack[s->top+1];
? ? }
? ? else
? ? ? ? return NULL;
}
void bulidtree(bitree &T)//二叉樹的建立（按照前序遍歷建立二叉樹）
{
? ? char c;
? ? cin>>c;
? ? if(c=='#')//判斷該節(jié)點是否存在
? ? ? ? T =NULL;
? ? else
? ? {
? ? ? ? T=new bitreenode;
? ? ? ? T->date=c;
? ? ? ? bulidtree(T->left);//建立左子樹
? ? ? ? bulidtree(T->right);//建立右子樹
? ? }
}
void front(bitree T)//前序遍歷二叉樹
{
? ? if(T!=NULL)
? ? {
? ? ? ? cout<<T->date<<" ";
? ? ? ? front(T->left);
? ? ? ? front(T->right);
? ? }
}
void mid(bitree T)//中序遍歷二叉樹
{
? ? if(T!=NULL)
? ? {
? ? ? ? mid(T->left);
? ? ? ? cout<<T->date<<" ";
? ? ? ? mid(T->right);
? ? }
}
void back(bitree T)//后序遍歷二叉樹
{
? ? if(T!=NULL)
? ? {
? ? ? ? back(T->left);
? ? ? ? back(T->right);
? ? ? ? cout<<T->date<<" ";
? ? }
}
//非遞歸前序遍歷
void front1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL||!empty(s.top)){//當(dāng)結(jié)點為空并且棧也為空時退出
? ? ? ? ? ? while(node!=NULL){//當(dāng)結(jié)點不為空時輸出該結(jié)點并將該結(jié)點壓入棧并遍歷左子樹
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){//結(jié)點為NULL但是棧不為空
? ? ? ? ? ? ? ? node=pop(&s);//彈出棧頂元素并賦給node
? ? ? ? ? ? ? ? node=node->right;//遍歷結(jié)點的右子樹
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
//中序遍歷
void mid1(bitree T){
? ? if(T){
? ? ? ? Stack s;
? ? ? ? init(s.top);
? ? ? ? bitree node =T;
? ? ? ? while(node!=NULL || !empty(s.top)){
? ? ? ? ? ? while(node!=NULL){
? ? ? ? ? ? ? ? push(&s,node);
? ? ? ? ? ? ? ? node=node->left;
? ? ? ? ? ? }
? ? ? ? ? ? if(!empty(s.top)){
? ? ? ? ? ? ? ? node=pop(&s);
? ? ? ? ? ? ? ? printf("%c ",node->date);
? ? ? ? ? ? ? ? node=node->right;
? ? ? ? ? ? }
? ? ? ? }
? ? }
}
?//后序遍歷
?void back1(bitree T){
?int b[20];
?if(T){
?Stack s;
?init(s.top);
?bitree node =T;
?while(node!=NULL || !empty(s.top)){
?while(node!=NULL){
?push(&s,node);//第一次進棧
?b[s.top]=0;
?node=node->left;
?}
?node=pop(&s);
?int flag=b[s.top+1];
?if(flag==0){? //說明只進過一次
?push(&s,node);//第二次進棧
?b[s.top]=1;
?node=node->right;
?}
?else{? ? //已經(jīng)進過兩次棧，說明左右子樹都已經(jīng)遍歷過了
?printf("%c ",node->date);
?node=NULL;
?}
?}
?}
?}
int main()
{
? ? bitree T;
? ? cout<<"開始建立二叉樹"<<endl;
? ? cout<<"請按照前序遍歷輸入二叉樹信息"<<endl;
? ? bulidtree(T);
? ? cout<<"二叉樹創(chuàng)建成功"<<endl;
? ? cout<<"遞歸方式"<<endl;
? ? cout<<"前序遍歷: ";
? ? front(T);
? ? cout<<endl;
? ? cout<<"中序遍歷: ";
? ? mid(T);
? ? cout<<endl;
? ? cout<<"后續(xù)遍歷: ";
? ? back(T);
? ? cout<<endl;
? ? cout<<"非遞歸方式: "<<endl;
? ? cout<<"前序遍歷: ";
? ? front1(T);
? ? cout<<endl;
? ? cout<<"中序遍歷: ";
? ? mid1(T);
? ? cout<<endl;
? ? cout<<"后續(xù)遍歷: ";
? ? back1(T);
? ? cout<<endl;
? ? return 0;
?}
