用遞歸非遞歸兩種方法遍歷二叉樹

1、用遞歸、非遞歸兩種方法遍歷二叉樹數(shù)據(jù)結(jié)構(gòu)（雙語）項(xiàng)目文檔報(bào)告用遞歸、非遞歸兩種方法遍歷二叉樹專 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) 班 級(jí)： 指導(dǎo)教師： 姓 名： 學(xué) 號(hào)： 目 錄一、設(shè)計(jì)思想.03二、算法流程圖.04三、源代碼.06四、運(yùn)行結(jié)果.12五、遇到的問題及解決.14六、心得體會(huì).15一、設(shè)計(jì)思想1遞歸：（1）主函數(shù)main（）主程序要包括：定義的二叉樹T、建樹函數(shù)、先序遍歷函數(shù)、中序遍歷函數(shù)、后序遍歷函數(shù)。（2）建樹函數(shù)定義一個(gè)輸入的數(shù)是字符型的，當(dāng)ch為空時(shí)，T就為空值，否則的話就分配空間給T，T就指向它的結(jié)點(diǎn)，然后左指針域指向左孩子，右指針指向右孩子，若還有，繼續(xù)調(diào)用,依次循環(huán)下去，直到c

2、h遇到空時(shí)，結(jié)束。最后要返回建立的二叉樹T。（3）先序遍歷函數(shù)根據(jù)先序遍歷規(guī)則，當(dāng)T為非空時(shí)，先輸出結(jié)點(diǎn)處的數(shù)據(jù)，指針指向左、右孩子，依次進(jìn)行下去。(4) 中序遍歷函數(shù)根據(jù)中序遍歷規(guī)則，當(dāng)T為非空時(shí)，先左指針指向左孩子數(shù)據(jù)，然后輸出結(jié)點(diǎn)處的數(shù)據(jù)，再右指針指向右孩子，依次進(jìn)行下去。(5）后序遍歷函數(shù)根據(jù)后序遍歷規(guī)則，當(dāng)T為非空時(shí)，先右指針指向右孩子，然后左指針指向左孩子，最后輸出結(jié)點(diǎn)處的數(shù)據(jù)，依次進(jìn)行下去。2.非遞歸：（1）跟遞歸遍歷二叉樹的前提一樣，首先應(yīng)該創(chuàng)建一個(gè)二叉樹，同樣使用先序遞歸的方式創(chuàng)建二叉樹。（2）然后是中序，先序，后序非遞歸遍歷二叉樹。（3）中序非遞歸遍歷二叉樹的思想是：首先是

3、根節(jié)點(diǎn)壓棧，當(dāng)根節(jié)點(diǎn)的左子樹不是空的時(shí)候，左子樹壓棧。直到左子樹為空的時(shí)候，不再壓棧。將棧頂元素出棧，訪問棧頂元素，并將棧頂?shù)挠易訕溥M(jìn)棧。當(dāng)右子樹的左子樹不是空的時(shí)候，左子樹一直進(jìn)棧，直到左子樹為空，則不再進(jìn)棧。重復(fù)上面的操作，直到?？盏臅r(shí)候。(4)先序非遞歸遍歷二叉樹的思想是：首先是根節(jié)點(diǎn)進(jìn)棧，然后當(dāng)棧不為空的時(shí)候，將棧頂元素出棧，然后訪問。同時(shí)將出棧元素的右子樹進(jìn)棧，左子樹進(jìn)棧。重復(fù)上面的操作，直到棧為空。(5）后序非遞歸遍歷二叉樹的思想：首先是根節(jié)點(diǎn)進(jìn)棧，當(dāng)根節(jié)點(diǎn)的左子樹不為空的時(shí)候，左子樹進(jìn)棧，直到左為空的時(shí)候，左子樹不再進(jìn)棧。指針指向的是右子樹，當(dāng)右子樹為空的時(shí)候，直接訪問根節(jié)點(diǎn)。當(dāng)

4、右子樹不為空的時(shí)候，則右子樹的指針進(jìn)棧，當(dāng)右子樹的左子樹不為空的時(shí)候，則左也進(jìn)棧，直到左為空。重復(fù)上面的操作，直到棧為空的時(shí)候，則遍歷樹完成。 二、算法流程圖1.遞歸2.非遞歸三、源代碼1.遞歸#include stdio.h#include conio.h#include #includetypedef struct node char data; struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; /定義二叉樹類型的指針/*先序創(chuàng)建二叉樹*/int CreateBinTree(BinTree *T) char

5、ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T) printf(overflow); do ch=getchar(); if(ch= ) *T=NULL; return 0; else (*T)-data=ch; CreateBinTree(&(*T)-lchild); CreateBinTree(&(*T)-rchild); return 1; while(ch!=0);/*中序遞歸遍歷*/void InorderTransverse(BinTree s)if (s)InorderTransverse(s-lchild); printf(%c,

6、 s-data);InorderTransverse(s-rchild);/先序遞歸遍歷二叉樹void PreOrderTranverseTree(BinTree s)if (s) printf(%c, s-data);PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);/后序遞歸遍歷二叉樹void PostOrderTranverseTree(BinTree s)if (s) PreOrderTranverseTree(s-lchild);PreOrderTranverseTree(s-rchild);printf(

7、%c, s-data);/*主方法*/void main() BinTree T;printf(請(qǐng)按照先序的順序輸入要?jiǎng)?chuàng)建的樹:n);CreateBinTree(&T); /*中序序列創(chuàng)建二叉樹*/printf(中序遞歸遍歷的序列是:); InorderTransverse(T); printf(n); /先序遞歸遍歷 printf(先序遞歸遍歷的序列是:); PreOrderTranverseTree(T); printf(n); /后序遞歸遍歷 printf(后序遞歸遍歷的序列是:); PostOrderTranverseTree(T); printf(n);2.非遞歸#include s

8、tdio.h#include conio.h#include #include typedef struct node char data; struct node *lchild, *rchild;BinTnode;typedef BinTnode * BinTree; /定義二叉樹類型的指針typedef struct BinTree data100; int top;SeqStack;void initStack(SeqStack *S) S-top =-1;void Push(SeqStack *S,BinTree x) if(S-top=100-1) printf(the stack

9、 is overflow); else S-top=S-top+1; S-dataS-top=x; int Pop(SeqStack *S,BinTree *p) if(S-top=-1) printf(the stack is underflow); return 0; else *p=S-dataS-top; -S-top; return 1; int EmptyStack(SeqStack S) if(S.top=-1) return 1; else return 0; /* 棧不空的情況*/ int GetTop(SeqStack S,BinTree *p) if(S.top=-1)

10、printf(the stack is empty); return 0; else *p=S.dataS.top; return 1; char visit(BinTree p)return (*p).data;/*創(chuàng)建二叉樹*/int CreateBinTree(BinTree *T) char ch; *T=(BinTree)malloc(sizeof(BinTnode); if(!*T) printf(overflow); else do ch=getchar(); if(ch!= ) *T=NULL; return 0; else (*T)-data=ch; CreateBinTre

11、e(&(*T)-lchild); CreateBinTree(&(*T)-rchild); return 1; while(ch!=0); /*中序非遞歸遍歷*/void InorderTransverse(BinTree T) SeqStack S; BinTree p; initStack(&S);/初始化棧 printf(中序非遞歸序列是:); Push(&S,T); /根指針進(jìn)棧 T為指向二叉樹的指針 while(!EmptyStack(S) /棧不是空的情況 while(GetTop(S,&p) & p) Push(&S,p-lchild); /gettop得到的結(jié)果也必須是一棵子樹

12、才行 ,進(jìn)棧應(yīng)該進(jìn)的是樹根的指針 Pop(&S,&p); if(!EmptyStack(S) /printf(%c,visit(p); Pop(&S,&p); printf(%c,visit(p); Push(&S,p-rchild); /*先序非遞歸遍歷*/void PreorderTransverse(BinTree T) SeqStack S; BinTree p; initStack(&S);/初始化棧 Push(&S,T); /根指針進(jìn)棧 T為指向二叉樹的指針 printf(先序非遞歸序列是:); while(!EmptyStack(S) Pop(&S,&p); /根節(jié)點(diǎn)出棧 if(

13、p!=NULL) printf(%c,visit(p); Push(&S,p-rchild); Push(&S,p-lchild);/*后序非遞歸遍歷*/void PostorderTransverse(BinTree T) SeqStack S; BinTree p,q; initStack(&S);/初始化棧 p=T; printf(后序非遞歸序列是:); while(p |!EmptyStack(S) /跳出while循環(huán)的原因是因?yàn)樽笞訕浠蛘哂易訕錇榭樟?if(p!=q) while(p!=NULL) Push(&S,p); if(p-lchild!=NULL) p=p-lchild;

14、 else p=p-rchild; if(EmptyStack(S) break; GetTop(S,&q); if(q-rchild=p) /進(jìn)棧的是右子樹 Pop(&S,&p); printf(%c,visit(p); p=q; else p=q-rchild; /*主方法*/void main() BinTree T;printf(請(qǐng)按照先序的順序輸入創(chuàng)建的樹:n);/*創(chuàng)建樹*/ CreateBinTree(&T);/中序非遞歸遍歷 InorderTransverse(T); printf(n); /先序非遞歸遍歷 PreorderTransverse(T); printf(n); /后序非遞歸遍歷 PostorderTransverse(T);四、運(yùn)行結(jié)果1.遞歸輸入結(jié)果2.非遞歸輸入結(jié)果五、遇到的問題及解決經(jīng)過一個(gè)星期的寫代碼，我遇到了很多問題，并一一解決了，比如：1. 創(chuàng)建二叉樹時(shí)：void createBiTree(BiTNode *T)和void createBiTree(BiTNode *&T)沒分清楚區(qū)別。后來查找資料找到void createBiTree(BiTNode *T)是將結(jié)點(diǎn)的指針（地址）傳遞到函數(shù)中進(jìn)行處理void createBiTree(BiTNode *&T是將結(jié)點(diǎn)指針的引用傳遞到函數(shù)處理。才理解清楚。2. 在寫非遞歸算法時(shí)，一直邏輯混