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

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

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

4、/棧或者隊(duì)列的默認(rèn)容量ttdefineMAXSIZE100/定義數(shù)據(jù)類型typedefcharDataType:定義二叉樹(shù)的結(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):四、測(cè)試結(jié)果測(cè)試用例：二叉樹(shù)(A(B(D,E(H,I),C(F,G)二叉因薙辛完乎.trntt遞歸遍歷如下ttmm厲先根序歹廠ABDEHICFG呻根序列DBHEIAFCG井后根序列：DHIEBFGGA歸胖非遞歸遍歷如下*#先根序列：ABDEHICFG中根序列：DBHEIAFCG井后根序列：DHIEBFGCA旳曲層次遍歷如下mnmABCDEFGHI二叉樹(shù)刪除完畢.Processreturned0Pressanykeytocontinue.executiontime:0-059s五、

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

7、fineMAXSIZE100/定義數(shù)據(jù)類型typedefcharDataType;/定義二叉樹(shù)的結(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請(qǐng)以廣義表的形式輸入二叉樹(shù):iT);/建立二叉樹(shù)并且默認(rèn)初始化BiTreeBT;Create(&BT,“(A(B(D,E(H,I),C(F,G)”);printfC匸叉樹(shù)建立完畢.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);/銷毀二叉樹(shù)printf(“二叉樹(shù)刪除完畢.n”)；Destiov(&BT);retiun0;/用廣義表的形式輸入二叉樹(shù)，井且建立二叉樹(shù)voidCreate(BiTree*BT,chai*sti)charch;BiTr

10、eestackMAXSIZE;定義棧，用于存放指向二叉樹(shù)中結(jié)點(diǎn)的指針inttop=0;intflagjc;BiTreep;*BT=NULL.k=0;ch=strk;while(ch!=while(ch!=t)如果字符串沒(méi)有結(jié)束while(ch!=while(ch!=t)如果字符串沒(méi)有結(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、一個(gè)結(jié)點(diǎn)，表示是根結(jié)點(diǎn)*BT=p;elseswitch(flag)case1:stacktop-lcliild=p;break;case2:stacktop-rchild=p;break;ch=str卄k;/銷毀二叉樹(shù)，用遞歸的方法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)訪問(wèn)并入棧左孩子，重復(fù)直到不存在左孩子；while(p!=NULL)piiiitf(H%ct,p-data);stacktop+=p;p=plcliild;出棧直到結(jié)點(diǎn)有右孩子，并把當(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é)點(diǎn)沒(méi)有左孩子;while(p!=NULL)stacktop+=p;p=p-lcliild;出棧并訪問(wèn)結(jié)點(diǎn)，如果右孩子存在，則把當(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é)點(diǎn)沒(méi)有左孩子；xvhile(p!=NULL)stacktop+=p;p=plchild;/如果棧頂元素沒(méi)有右孩子或者右孩子訪問(wèn)過(guò)，則出棧并訪問(wèn)；/如果棧頂元素右孩子存在且沒(méi)被訪問(wèn)過(guò)。則當(dāng)前指針指向其右孩子。重復(fù)以上;if(top0)p=stacktop-l;if(p-rcliild=NULL|p-rcliild=q)printfT%cPpdata);top-；q=p；p=NULL;elsep=pXchild;/層次遍歷，用隊(duì)列即可voidLevel(BiTreeBT)/定