數(shù)據(jù)結(jié)構(gòu)實驗報告二叉樹的7種遍歷算法及應(yīng)用

1、哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院實驗報告課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程類型：必修實驗項目名稱：二叉樹的應(yīng)用實驗題目：二叉樹的建立、遍歷班級：計算機學(xué)院6班學(xué)號:H090311001姓名：楊瑞設(shè)計成績報告成績指導(dǎo)老師一、實驗?zāi)康恼莆斩鏄涞慕⒎椒?，遞歸和非遞歸的遍歷方法二、實驗要求及實驗環(huán)境實驗要求：以遞歸和非遞歸的方式實現(xiàn)先根，中根，后根遍歷二叉樹的算法;實現(xiàn)層次遍歷二叉樹實驗環(huán)境：GCC編譯器，GDB調(diào)試器三、設(shè)計思想（本程序中的用到的所有數(shù)據(jù)類型的定義，主程序的流程圖及各程序模塊之間的調(diào)用關(guān)系，自己擴展內(nèi)容的等）設(shè)計思想及流程圖:建立二叉樹算法思想:建立二叉樹用戶輸員卜義表形式表示的二叉

2、樹，然后妲立二叉樹；掃描輸入的字符串O若碰到C，則說明前面的是雙親節(jié)點，接下來的事孩子節(jié)點，并用標志位表示；若矗到“），則說明子樹建立結(jié)束，用標志位表示：若謹?shù)剑瑒t說明接下來的是右孩子.同樣用標志位表示；其余情況根據(jù)標志位建立節(jié)點；直到字符串掃描結(jié)束：第法思想：根據(jù)二叉樹的定義和遍歷算法的定義，很容器實現(xiàn)遞歸遍歷的算法。都是用棧實現(xiàn)；先If1訪亦并入棧左孩子，重復(fù)直到不存在左孩子：2出枝直到結(jié)點有右孩子.并把當(dāng)前指針指向其右a子。重復(fù)以上兩個步驟：中ft:1入枝左孩子，直到結(jié)點沒有左孩子：2出棧并訪問結(jié)點，如果右孩子存在，則把當(dāng)前指針指向右孩子。重復(fù)以上兩步eit:1入枝左孩子，直到結(jié)點沒有左

3、孩子：2如果棧頂元素沒有右孩子或者右孩子訪問過.則出棧并訪問；如果棧頂元素右孩子存在且沒被訪問過。則當(dāng)前指針指向其右孩子。垂復(fù)以上兩個步驟：用隊列實現(xiàn)；將根節(jié)點入隊。1出隊并輸出節(jié)點的值。2若存在左右孩子，則將其入隊。循環(huán)以上兩個步驟，直到隊列為空。算法思想：根據(jù)二殳材的定義，（二叉樹包含左右子樹和根節(jié)點）先刪除左子樹，再硼除右子樹。最后釋放根節(jié)點。仍然是遞歸實現(xiàn)。數(shù)據(jù)類型定義及宏定義：/*malloc容錯函數(shù)的宏定義*/#defineMALLOC(p,s)pmalloc(sizeof(s);if(p=NULL)fprintf(stderr,WrongMemory!n，z):exit(-1)；

4、/棧或者隊列的默認容量ttdefineMAXSIZE100/定義數(shù)據(jù)類型typedefcharDataType:定義二叉樹的結(jié)構(gòu)typedefstructBiNode*BiTree;typedefstructBiNodeDataTypedata;BiTreelchild;BiTreerchild;BiNode;函數(shù)集：voidCreate(BiTree込charstr);voidDestroy(BiTree*);voidPreOrderl(BiTree);voidPre0rder2(BiTree);voidInOrderl(BiTree):voidIn0rder2(BiTree):voidPo

5、stOrderl(BiTree);voidPost0rder2(BiTree);voidLevel(BiTree):四、測試結(jié)果測試用例：二叉樹(A(B(D,E(H,I),C(F,G)二叉因薙辛完乎.trntt遞歸遍歷如下ttmm厲先根序歹廠ABDEHICFG呻根序列DBHEIAFCG井后根序列：DHIEBFGGA歸胖非遞歸遍歷如下*#先根序列：ABDEHICFG中根序列：DBHEIAFCG井后根序列：DHIEBFGCA旳曲層次遍歷如下mnmABCDEFGHI二叉樹刪除完畢.Processreturned0Pressanykeytocontinue.executiontime:0-059s五、

6、系統(tǒng)不足與經(jīng)驗體會系統(tǒng)不足：算法效率不是非常高，有待改善經(jīng)驗體會：1棧的用法非常靈活,有的時候不需要定義棧的數(shù)據(jù)類型。只需要用到棧的思想;2遞歸算法都可以用棧和循環(huán)來代替六、附錄：源代碼(帶注釋)/*I數(shù)據(jù)結(jié)構(gòu)實驗二：二叉樹的各種遍歷算法計算機學(xué)院班楊瑞學(xué)號：H0903110012010-12-1320:04:37*/彳includeinclude彳include/*malloc容錯函數(shù)的宏定義*/defineMALLOC(p,s)p=inalloc(sizeof(s);if(p=NULL)fpiintf(stdeiT/WrongMemory!n”);exit(-l);?；蛘哧犃械哪J容量de

7、fineMAXSIZE100/定義數(shù)據(jù)類型typedefcharDataType;/定義二叉樹的結(jié)構(gòu)typedefstrnctBiNode*BiTree;typedefstrnctBiNodeDataTypedata;BiTreelchild;BiTreerchild;BiNode;voidCreate(BiTreejcharsti);voidDestioy(BHYee*);voidPreOrder1(BiTree);voidPreOrder2(BiTree);voidInOrderl(BiTree);voidInOrder2(BiTree);voidPostOrder1(BiTree);vo

8、idPostOrder2(BiTree);voidLevel(BiTree);intmaiii()/printf(H請以廣義表的形式輸入二叉樹:iT);/建立二叉樹并且默認初始化BiTreeBT;Create(&BT,“(A(B(D,E(H,I),C(F,G)”);printfC匸叉樹建立完畢.n“)；/以下為遞歸遍歷printf(歸遍歷如下#;printfC#先根序列：8”)；PieOrderl(BT);printf(nnn);printf(n#中根序列：nM);IiiOrderl(BT);printf(nnn);printfC*#后根序列：8”)；PostOrder1(BT);printf

9、(nnn);printfC1#非遞歸遍歷如下#printfC#先根序列：8”)；PieOrder2(BT);printf(nnn);printf(n#中根序列：nM);IiiOrder2(BT);printf(nnn);printfC*#后根序列：8”)；PostOrder2(BT);printf(nnn);printfC1#層次遍歷如下Level(BT);printsHnM);/銷毀二叉樹printf(“二叉樹刪除完畢.n”)；Destiov(&BT);retiun0;/用廣義表的形式輸入二叉樹，井且建立二叉樹voidCreate(BiTree*BT,chai*sti)charch;BiTr

10、eestackMAXSIZE;定義棧，用于存放指向二叉樹中結(jié)點的指針inttop=0;intflagjc;BiTreep;*BT=NULL.k=0;ch=strk;while(ch!=while(ch!=t)如果字符串沒有結(jié)束while(ch!=while(ch!=t)如果字符串沒有結(jié)束switch(ch)casef:stack卄top=p;flag=l;break;casey：top;break;caseT：flag=2;break;default:MALLOC(p,BiNode);pdata=ch;p-lcliild=NULL;p-rcliild=NULL;if(*BT=NULL)如果是第

11、一個結(jié)點，表示是根結(jié)點*BT=p;elseswitch(flag)case1:stacktop-lcliild=p;break;case2:stacktop-rchild=p;break;ch=str卄k;/銷毀二叉樹，用遞歸的方法voidDestroy(BHYee*BT)Destroy(&(*BT)-lchild);if(*BT)-rcliild)Destioy(&(*BT)-rchild);free(*BT);*BT=NULL;/先根遍歷，遞歸的方法voidPreOrder1(BiTreeBT)iRBT)priiitf(M%cfBT-data);PreOrderl(BT-lchild);P

12、reOrderl(BT-rchild);/中根遍歷，遞歸的方法voidInOrderl(BiTreeBT)iRBT)IiiOrder1(BT-lchild);printf(M%ctH,BT-data);IiiOrder1(BT-rchild);/后根遍歷，遞歸的方法voidPostOrderl(BiTreeBT)iRBT)PostOrderl(BT-lchild);PostOrderl(BT-rchild);printf(M%ctH,BT-data);/先根遍歷，非遞歸的方法voidPreOrder2(BiTreeBT)/定義并且初始化棧BiTreestackMAXSIZE;inttop=0;

13、BiTreep=BT;while(!(p=NULL&top=0)訪問并入棧左孩子，重復(fù)直到不存在左孩子；while(p!=NULL)piiiitf(H%ct,p-data);stacktop+=p;p=plcliild;出棧直到結(jié)點有右孩子，并把當(dāng)前指針指向其右孩子。重復(fù)以上;if(top0)p=stack-top;while(p-rchild=NULL)if(top0)p=stack-top;elsebreak;p=pTchild;中根遍歷，非遞歸的方法voidInOrder2(BiTreeBT)BiTreestackMAXSIZE;inttop=0;BiTreep=BT;while(!(p

14、=NULL&top=0)/入棧左孩子，直到結(jié)點沒有左孩子;while(p!=NULL)stacktop+=p;p=p-lcliild;出棧并訪問結(jié)點，如果右孩子存在，則把當(dāng)前指針指向右孩子。重復(fù)以上兩步;if(top0)p=stack-top;piiiitf(H%ct,p-data);while(p-rchild=NULL)while(p-rchild=NULL)if(top0)p=stack-top;printf(H%ctH,p-data);elsebreak;p=p-rcliild;/后根遍歷，非遞歸的方法voidPostOrder2(BiTreeBT)BiTreestackMAXSIZE

15、;inttop=0;BiTreep=BT;BiTreeq=NULL;while(!(p=NULL&top=0)/入棧左孩子，直到結(jié)點沒有左孩子；xvhile(p!=NULL)stacktop+=p;p=plchild;/如果棧頂元素沒有右孩子或者右孩子訪問過，則出棧并訪問；/如果棧頂元素右孩子存在且沒被訪問過。則當(dāng)前指針指向其右孩子。重復(fù)以上;if(top0)p=stacktop-l;if(p-rcliild=NULL|p-rcliild=q)printfT%cPpdata);top-；q=p；p=NULL;elsep=pXchild;/層次遍歷，用隊列即可voidLevel(BiTreeBT)/定