數(shù)據(jù)結(jié)構(gòu) 二叉樹(shù)實(shí)驗(yàn)報(bào)告

一、需求分析：編寫(xiě)一段程序，對(duì)二叉樹(shù)進(jìn)行復(fù)合操作，包括創(chuàng)建一棵二叉樹(shù)，顯示二叉樹(shù)的樹(shù)型結(jié)構(gòu)，對(duì)創(chuàng)建的二叉樹(shù)進(jìn)行先根、中根、后根三種方式進(jìn)行遍歷，并且打印出葉子結(jié)點(diǎn)，并且可以隨時(shí)刪除我們創(chuàng)建的二叉樹(shù)，然后用循環(huán)語(yǔ)句將上述的操作封裝起來(lái)，使之能夠進(jìn)行可重復(fù)、連續(xù)的操作。輸入為a-z或者是A-Z之間的字符，用'@'字符作為結(jié)束當(dāng)前結(jié)點(diǎn)的標(biāo)識(shí)符。二、概要設(shè)計(jì)：本程序要用到的數(shù)據(jù)類(lèi)型structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;};然后定義我們需要的指針類(lèi)型typedefstructBinTreeNode*PBinTreeNode;/*定義指向二叉樹(shù)結(jié)點(diǎn)的指針類(lèi)型*/typedefPBinTreeNode*PBinTree; /*定義指向樹(shù)型結(jié)點(diǎn)的指針類(lèi)型*/程序需要用到的自定義函數(shù).創(chuàng)建一個(gè)二叉樹(shù)根節(jié)點(diǎn)PBinTreeCreate_BinTreeRoot(void).創(chuàng)建一個(gè)二叉樹(shù)的節(jié)點(diǎn)PBinTreeNodeCreate_BinTreeNode(void).創(chuàng)建一棵二叉樹(shù)PBinTreeNodeCreate_BinTree(void).用先根的方法遍歷一棵二叉樹(shù)voidpreOrder(PBinTreeNodepbnode).用中根的方法遍歷一棵二叉樹(shù)voidinOrder(PBinTreeNodepbnode).用后根的方法遍歷一棵二叉樹(shù)voidpostOrder(PBinTreeNodepbnode).打印出我們創(chuàng)建的二叉樹(shù)的樹(shù)型結(jié)構(gòu)voidoutputTree(PBinTreeNodepbnode,inttotalSpace).打印出二叉樹(shù)的葉子結(jié)點(diǎn)voidleaves(PBinTreeNodepbnode).釋放我們所申請(qǐng)的所有結(jié)點(diǎn)空間voidfreeAIINodes(PBinTreeNodepbnode).判斷我們輸入的是否是合格的字符intisalphabet(chari)2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0to}if(i==6)(freeAIINodes(*pbtree);)pbtree=Create_BinTreeRoot();outputTree(*pbtree,totalSpace);})freeAIINodes(*pbtree);getch();return0;七.圖形界面根據(jù)提示一步步進(jìn)行操作。c<"C:\ProgramFiles\MicrosoftVisualStudio\MyProjects\66\Debug\66.exe"Pleaseinputachar：APleaseinputachar：BPleaseinputachar：CPleaseinputachar：(?Pleaseinputachar：ePleaseinputachar：DPleaseinputachar：ePleaseinputachar：(?Pleaseinputachar：EPleaseinputachar：FPleaseinputachar：(?Pleaseinputachar：(?Pleaseinputachar：GPleaseinputachar：ePleaseinputachar：eDisplaythebinatreedatadirectly：GEFADBCPleasechoosethenodeyouwanttooperatewiththebinatree：1.display2?pi*eOi*deT3?in0i*deT4-postONdeT5.leaves nodes0toexit：八MC:\ProgramFiles\MicrosoftVisualStudio\MyProjects\66\Debug\66.exeuBCPleasechoosethenodeyouwanttooperatewiththebinatree：1.display2.preOrder3.inOrder4.post0i*dei*5.leaues6.freenodes0toDisplaybinatree：GEFADBCPleasechoosethenodeyouwanttooperatewiththebinatree：exit：exit：2DatainpreOrder：A B C D E F GPleasechoosethemodeyouwanttooperatewiththebinatree：0toexit：0toexit：三、詳細(xì)設(shè)計(jì)：.PBinTreeNodeCreate_BinTreeNode(void)我們定義一個(gè)指向二叉樹(shù)結(jié)點(diǎn)類(lèi)型的指針PBinTreeNode,然后，申請(qǐng)一個(gè)二叉樹(shù)結(jié)點(diǎn)大小的空間，對(duì)擺布子結(jié)點(diǎn)賦為空。.創(chuàng)建一個(gè)二叉樹(shù)根節(jié)點(diǎn)定義一個(gè)指向二叉樹(shù)結(jié)點(diǎn)的指針的指針即：BinTreeNode**pbtree,或者是：PBinTreeNode*pbtree;用于存放樹(shù)的根結(jié)點(diǎn)，同時(shí)，將我們創(chuàng)建的二叉樹(shù)的地址傳給它即：*pbtree=Create_BinTree();.創(chuàng)建一棵二叉樹(shù)首先我們定義一個(gè)DataType類(lèi)型的變量i,用于存放我們輸入的字符(即作為緩沖區(qū))，并用scanf函數(shù)去接收它，由于使用scanf函數(shù)時(shí)，會(huì)浮現(xiàn)吸收我們輸入的回車(chē)字符，并將會(huì)車(chē)作為接收的字符的情況發(fā)生，為了避免這種情況，我們用函數(shù)fflush(stdin)將緩沖區(qū)的字符全部沖掉，然后再吸收我們輸入的字符，就可以徹底避免此類(lèi)問(wèn)題的發(fā)生。我們定義我們輸入的字符是從a-z或者是A-Z,用字符@為我們結(jié)束當(dāng)前結(jié)點(diǎn)左或者右結(jié)點(diǎn)的字符，然后遞歸調(diào)用擺布子樹(shù)，此時(shí)我們將一棵二叉樹(shù)全整的創(chuàng)建出來(lái)了。.用先根的方法遍歷一棵二叉樹(shù)先訪問(wèn)根結(jié)點(diǎn)，打印出它里面的信息，然后遞歸調(diào)用左子樹(shù)和右子樹(shù)。.用中根的方法遍歷一棵二叉樹(shù)先遞歸調(diào)用左子樹(shù)，打印出里面的信息，在打印出根結(jié)點(diǎn)信息，然后遞歸調(diào)用右子樹(shù)，打印出里面的信息。.用后根的方法遍歷一棵二叉樹(shù)先遞歸調(diào)用左子樹(shù)，打印出里面的內(nèi)容，然后遞歸調(diào)用右子樹(shù)，打印出里面的內(nèi)容，然后是根結(jié)點(diǎn)的內(nèi)容。.打印出我們創(chuàng)建的二叉樹(shù)的樹(shù)型結(jié)構(gòu)先遞歸調(diào)用右子樹(shù)，如果結(jié)點(diǎn)不為空的話，空格數(shù)加5,如果為空的話，就打印出右子樹(shù)的內(nèi)容，然后遞歸調(diào)用左子樹(shù)。.打印出二叉樹(shù)的葉子結(jié)點(diǎn)如果當(dāng)前結(jié)點(diǎn)的擺布子樹(shù)都為空的話，就打印出此結(jié)點(diǎn)的信息，如果左子樹(shù)不為空的話，遞歸調(diào)用左子樹(shù)，如果右子樹(shù)不為空的話，遞歸調(diào)用右子樹(shù)。.釋放我們所申請(qǐng)的所有結(jié)點(diǎn)空間如果當(dāng)前的左子樹(shù)不為空，則遍歷左子樹(shù)，如果右子樹(shù)不為空的話，則遍歷右子樹(shù)，如果都不位空的話，分別調(diào)用擺布子樹(shù)，如果擺布都為空的話，就釋放擺布結(jié)點(diǎn)空間，并將當(dāng)前結(jié)點(diǎn)置為空。.主函數(shù)的安排：先創(chuàng)建好我們要的二叉樹(shù)，之后，我們就可以對(duì)此而二樹(shù)進(jìn)行多種操作，我們定義了6種集合操作，并對(duì)用戶輸入的信息進(jìn)行檢測(cè)，正確的提示出錯(cuò)信息，如果選擇的是我們定義的操作之一的話，對(duì)應(yīng)的我們?cè)O(shè)置出不同的case語(yǔ)句。如果我們選擇的是釋放所有的結(jié)點(diǎn)空間的話，我們需要屏蔽掉所有的菜單信息，提示用戶重新創(chuàng)建一棵二叉樹(shù)，并對(duì)它進(jìn)行重新操作。如果我們選擇退出，但是沒(méi)有選擇釋放掉所有的節(jié)點(diǎn)空間時(shí)，我們需要考慮到此類(lèi)的情形，應(yīng)調(diào)用voidfreeAIINodes(PBinTreeNodepbnode)自動(dòng)的釋放掉所有的結(jié)點(diǎn)空間，正常的退出。四、用戶使用說(shuō)明：當(dāng)用戶還沒(méi)有創(chuàng)建二叉樹(shù)時(shí)，提示用戶輸入數(shù)據(jù)：Pleaseinputchartothebinatree,@toexitcurrentnodePleaseinputachar:這時(shí)用戶用鍵盤(pán)輸入，每輸入一個(gè)字符回車(chē)一次,輸入為a-z或者是A-Z之間的字符，用字符作為結(jié)束當(dāng)前結(jié)點(diǎn)的標(biāo)識(shí)符當(dāng)用戶，創(chuàng)建了二叉樹(shù)之后，浮現(xiàn)控制菜單：Pleasechoosethemodeyouwanttooperatewiththebinatree:1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:此時(shí)用戶可以選擇操作：1.自動(dòng)的打印出樹(shù)型結(jié)構(gòu)2.先根遍歷3.中根遍歷4.后根遍歷5.打印葉子結(jié)點(diǎn)6.釋放所有結(jié)點(diǎn)空間0.退出五、測(cè)試結(jié)果：1.測(cè)試徹底二叉樹(shù)的情形：輸入（每輸入一個(gè)字符回車(chē)一次）：ABC@@D@@EF@@G@@自動(dòng)的打印出樹(shù)型結(jié)構(gòu)：Displaythebinatreedatadirectly:GEFADBC三種遍歷方式和葉子結(jié)點(diǎn)，測(cè)試如下：先根：DatainpreOrder:ABCDEFG中根：DataininOrder:CBDAFEG后根：DatainpostOrder:CDBFGEA打印葉子結(jié)點(diǎn)：Leaves:CDFG釋放所有結(jié)點(diǎn)空間:Freeallnodes:Allnodehavebeenfreedsuccessfully.自動(dòng)提示創(chuàng)建一棵新的二叉樹(shù)：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:2測(cè)試非徹底二叉樹(shù)的情形輸入（每輸入一個(gè)字符回車(chē)一次）：ABCD@@@@@自動(dòng)的打印出樹(shù)型結(jié)構(gòu)：ABCD三種遍歷方式和葉子結(jié)點(diǎn)，測(cè)試如下：先根：DatainpreOrder:ABCD中根：DataininOrder:DCBA后根：DatainpostOrder:DCBA打印葉子結(jié)點(diǎn)：Leaves:D釋放所有結(jié)點(diǎn)空間：Freeallnodes:Allnodehavebeenfreedsuccessfully.自動(dòng)提示創(chuàng)建一棵新的二叉樹(shù)：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:如果我們想結(jié)束此次的操作，退出本程序，就可以輸入0,程序自動(dòng)的釋放所有的結(jié)點(diǎn)空間:Pleasechoosethemodeyouwanttooperatewiththebinatree:1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:0Dealingwiththelastjob,tofreeallnodesAllnodehavebeenfreedsuccessfully六、附錄：include<stdio.h>#include<stdlib.h>#include<conio.h>#defineNULL0#defineDataTypechartypedefstructBinTreeNode*PBinTreeNode;typedefPBinTreeNode*PBinTree;structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;);PBinTreeNodeCreate_BinTree(void);PBinTreeCreate_BinTreeRoot(void){PBinTreepbtree;pbtree=(PBinTree)malloc(sizeof(structBinTreeNode));if(pbtree==NULL)pbtree=(PBinTree)realloc(pbtree,sizeof(structBinTreeNode));*pbtree=Create_BinTree();return(pbtree);)PBinTreeNodeCreate_BinTreeNode(void){PBinTreeNodepbnode;pbnode=(PBinTreeNode)malloc(sizeof(structBinTreeNode));if(pbnode==NULL)pbnode=(PBinTreeNode)realloc(pbnode,sizeof(structBinTreeNode));elsepbnode->llink=pbnode->rlink=(PBinTreeNode)NULL;return(pbnode);)intisalphabet(chari){if(i>=?a'&&i<=,z,||i>='N&&i<=T||i=='@')return1;elsereturn0;PBinTreeNodeCreate_BinTree(void){PBinTreeNodepbnode;DataTypei;fflush(stdin);fflush(stdin);while(!isalphabet(i))fflush(stdin);}if(i=='@')pbnode=NULL;else(pbnode=(PBinTreeNode)malloc(sizeof(structBinTreeNode));if(pbnode==NULL)(returnpbnode;}pbnode->info=i;pbnode->llink=Create_BinTree();pbnode->rlink=Create_BinTree();}returnpbnode;)voidoutputTree(PBinTreeNodepbnode,inttotalSpace){inti;if(pbnode!=NULL){totalSpace+=5;outputTree(pbnode->rlink,totalSpace);outputTree(pbnode->llink,totalSpace);)voidpreOrder(PBinTreeNodepbnode)if(pbnode==NULL)return;preOrder(pbnode->llink);preOrder(pbnode->rlink);)voidinOrder(PBinTreeNodepbnode){if(pbnode==NULL)return;inOrder(pbnode->llink);inOrder(pbnode->rlink);)voidpostOrder(PBinTreeNodepbnode){if(pbnode==NULL)return;postOrder(pbnode->llink);postOrder(pbnode->rlink);)voidleaves(PBinTreeNodepbnode)(if(pbnode->llink!=NULL&&pbnode->rlink==NULL)leaves(pbnode->llink);if(pbnode->rlink!=NULL&&pbnode->llink==NULL)leaves(pbnode->rlink);if(pbnode->llink!=NULL&&pbnode->rlink!=NULL)(leaves(pbnode->llink);leaves(pbnode->rlink);)if(pbnode->llink==NULL&&pbnode->rlink==NULL)(return;})voidfreeAIINodes(PBinTreeNodepbnode)(if(pbnode->llink!=NULL&&pbnode->rlink==NULL)freeAIINodes(pbnode->llink);if(pbn