一、需求分析：編寫一段程序，對二叉樹進行復(fù)合操作，包括創(chuàng)建一棵二叉樹，顯示二叉樹的樹型結(jié)構(gòu)，對創(chuàng)建的二叉樹進行先根、中根、后根三種方式進行遍歷，并且打印出葉子結(jié)點，并且可以隨時刪除我們創(chuàng)建的二叉樹，然后用循環(huán)語句將上述的操作封裝起來，使之能夠進行可重復(fù)、連續(xù)的操作。輸入為a-z或者是A-Z之間的字符，用'@'字符作為結(jié)束當(dāng)前結(jié)點的標(biāo)識符。二、概要設(shè)計：本程序要用到的數(shù)據(jù)類型structBinTreeNode{DataTypeinfo;PBinTreeNodellink;PBinTreeNoderlink;};然后定義我們需要的指針類型typedefstructBinTreeNode*PBinTreeNode;/*定義指向二叉樹結(jié)點的指針類型*/typedefPBinTreeNode*PBinTree; /*定義指向樹型結(jié)點的指針類型*/程序需要用到的自定義函數(shù).創(chuàng)建一個二叉樹根節(jié)點PBinTreeCreate_BinTreeRoot(void).創(chuàng)建一個二叉樹的節(jié)點PBinTreeNodeCreate_BinTreeNode(void).創(chuàng)建一棵二叉樹PBinTreeNodeCreate_BinTree(void).用先根的方法遍歷一棵二叉樹voidpreOrder(PBinTreeNodepbnode).用中根的方法遍歷一棵二叉樹voidinOrder(PBinTreeNodepbnode).用后根的方法遍歷一棵二叉樹voidpostOrder(PBinTreeNodepbnode).打印出我們創(chuàng)建的二叉樹的樹型結(jié)構(gòu)voidoutputTree(PBinTreeNodepbnode,inttotalSpace).打印出二叉樹的葉子結(jié)點voidleaves(PBinTreeNodepbnode).釋放我們所申請的所有結(jié)點空間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ù)提示一步步進行操作。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è)計：.PBinTreeNodeCreate_BinTreeNode(void)我們定義一個指向二叉樹結(jié)點類型的指針PBinTreeNode,然后，申請一個二叉樹結(jié)點大小的空間，對擺布子結(jié)點賦為空。.創(chuàng)建一個二叉樹根節(jié)點定義一個指向二叉樹結(jié)點的指針的指針即：BinTreeNode**pbtree,或者是：PBinTreeNode*pbtree;用于存放樹的根結(jié)點，同時，將我們創(chuàng)建的二叉樹的地址傳給它即：*pbtree=Create_BinTree();.創(chuàng)建一棵二叉樹首先我們定義一個DataType類型的變量i,用于存放我們輸入的字符(即作為緩沖區(qū))，并用scanf函數(shù)去接收它，由于使用scanf函數(shù)時，會浮現(xiàn)吸收我們輸入的回車字符，并將會車作為接收的字符的情況發(fā)生，為了避免這種情況，我們用函數(shù)fflush(stdin)將緩沖區(qū)的字符全部沖掉，然后再吸收我們輸入的字符，就可以徹底避免此類問題的發(fā)生。我們定義我們輸入的字符是從a-z或者是A-Z,用字符@為我們結(jié)束當(dāng)前結(jié)點左或者右結(jié)點的字符，然后遞歸調(diào)用擺布子樹，此時我們將一棵二叉樹全整的創(chuàng)建出來了。.用先根的方法遍歷一棵二叉樹先訪問根結(jié)點，打印出它里面的信息，然后遞歸調(diào)用左子樹和右子樹。.用中根的方法遍歷一棵二叉樹先遞歸調(diào)用左子樹，打印出里面的信息，在打印出根結(jié)點信息，然后遞歸調(diào)用右子樹，打印出里面的信息。.用后根的方法遍歷一棵二叉樹先遞歸調(diào)用左子樹，打印出里面的內(nèi)容，然后遞歸調(diào)用右子樹，打印出里面的內(nèi)容，然后是根結(jié)點的內(nèi)容。.打印出我們創(chuàng)建的二叉樹的樹型結(jié)構(gòu)先遞歸調(diào)用右子樹，如果結(jié)點不為空的話，空格數(shù)加5,如果為空的話，就打印出右子樹的內(nèi)容，然后遞歸調(diào)用左子樹。.打印出二叉樹的葉子結(jié)點如果當(dāng)前結(jié)點的擺布子樹都為空的話，就打印出此結(jié)點的信息，如果左子樹不為空的話，遞歸調(diào)用左子樹，如果右子樹不為空的話，遞歸調(diào)用右子樹。.釋放我們所申請的所有結(jié)點空間如果當(dāng)前的左子樹不為空，則遍歷左子樹，如果右子樹不為空的話，則遍歷右子樹，如果都不位空的話，分別調(diào)用擺布子樹，如果擺布都為空的話，就釋放擺布結(jié)點空間，并將當(dāng)前結(jié)點置為空。.主函數(shù)的安排：先創(chuàng)建好我們要的二叉樹，之后，我們就可以對此而二樹進行多種操作，我們定義了6種集合操作，并對用戶輸入的信息進行檢測，正確的提示出錯信息，如果選擇的是我們定義的操作之一的話，對應(yīng)的我們設(shè)置出不同的case語句。如果我們選擇的是釋放所有的結(jié)點空間的話，我們需要屏蔽掉所有的菜單信息，提示用戶重新創(chuàng)建一棵二叉樹，并對它進行重新操作。如果我們選擇退出，但是沒有選擇釋放掉所有的節(jié)點空間時，我們需要考慮到此類的情形，應(yīng)調(diào)用voidfreeAIINodes(PBinTreeNodepbnode)自動的釋放掉所有的結(jié)點空間，正常的退出。四、用戶使用說明：當(dāng)用戶還沒有創(chuàng)建二叉樹時，提示用戶輸入數(shù)據(jù)：Pleaseinputchartothebinatree,@toexitcurrentnodePleaseinputachar:這時用戶用鍵盤輸入，每輸入一個字符回車一次,輸入為a-z或者是A-Z之間的字符，用字符作為結(jié)束當(dāng)前結(jié)點的標(biāo)識符當(dāng)用戶，創(chuàng)建了二叉樹之后，浮現(xiàn)控制菜單：Pleasechoosethemodeyouwanttooperatewiththebinatree:1.display2.preOrder3.inOrder4.postOrder5.leaves6.freenodes0toexit:此時用戶可以選擇操作：1.自動的打印出樹型結(jié)構(gòu)2.先根遍歷3.中根遍歷4.后根遍歷5.打印葉子結(jié)點6.釋放所有結(jié)點空間0.退出五、測試結(jié)果：1.測試徹底二叉樹的情形：輸入（每輸入一個字符回車一次）：ABC@@D@@EF@@G@@自動的打印出樹型結(jié)構(gòu)：Displaythebinatreedatadirectly:GEFADBC三種遍歷方式和葉子結(jié)點，測試如下：先根：DatainpreOrder:ABCDEFG中根：DataininOrder:CBDAFEG后根：DatainpostOrder:CDBFGEA打印葉子結(jié)點：Leaves:CDFG釋放所有結(jié)點空間:Freeallnodes:Allnodehavebeenfreedsuccessfully.自動提示創(chuàng)建一棵新的二叉樹：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:2測試非徹底二叉樹的情形輸入（每輸入一個字符回車一次）：ABCD@@@@@自動的打印出樹型結(jié)構(gòu)：ABCD三種遍歷方式和葉子結(jié)點，測試如下：先根：DatainpreOrder:ABCD中根：DataininOrder:DCBA后根：DatainpostOrder:DCBA打印葉子結(jié)點：Leaves:D釋放所有結(jié)點空間：Freeallnodes:Allnodehavebeenfreedsuccessfully.自動提示創(chuàng)建一棵新的二叉樹：Nowcreatinganewbinatree...Pleaseinputchartothebinatree,@toexitcurrentnode:Pleaseinputachar:如果我們想結(jié)束此次的操作，退出本程序，就可以輸入0,程序自動的釋放所有的結(jié)點空間: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