二叉樹(shù)基本操作演示程序的設(shè)計(jì)與實(shí)現(xiàn)

1、二叉樹(shù)基本操作演示程序的設(shè)計(jì)與實(shí)現(xiàn)2012級(jí)電器信息類X班 （姓名） （學(xué)號(hào)）注意：文檔以word格式提供，文件名起名規(guī)則：學(xué)號(hào)+姓名+實(shí)驗(yàn)報(bào)告名稱一、需求分析1、創(chuàng)建二叉樹(shù)。按照用戶需要的二叉樹(shù)，構(gòu)建二叉樹(shù)。2、將創(chuàng)建的二叉樹(shù)，以樹(shù)狀形式輸出。3、分別以先序、中序、后序三種方式遍歷訪問(wèn)二叉樹(shù)。4、輸出二叉樹(shù)的葉子結(jié)點(diǎn)及葉子結(jié)點(diǎn)的個(gè)數(shù)。5、輸出二叉樹(shù)的高度。6、將創(chuàng)建的二叉樹(shù)，以括號(hào)形式輸出。二、概要設(shè)計(jì)為了實(shí)現(xiàn)以上功能，可以從三個(gè)方面著手設(shè)計(jì)。1、主界面設(shè)計(jì)為了實(shí)現(xiàn)二叉樹(shù)相關(guān)操作功能的管理，設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單子程序以鏈接系統(tǒng)的各項(xiàng)子功能，方便用戶使用本程序。本系統(tǒng)主控菜單運(yùn)行界

2、面如圖1所示。首先請(qǐng)輸入二叉樹(shù)結(jié)點(diǎn)序列：請(qǐng)按菜單提示操作： -歡迎使用二叉樹(shù)基本操作程序- 菜單選擇 1. 樹(shù)狀輸出二叉樹(shù) 2. 先序遍歷二叉樹(shù) 3. 中序遍歷二叉樹(shù) 4. 后序遍歷二叉樹(shù) 5. 輸出葉子結(jié)點(diǎn) 6. 輸出葉子結(jié)點(diǎn)個(gè)數(shù) 7. 輸出二叉樹(shù)的深度 8. 括號(hào)形式輸出二叉樹(shù)9. 退出 -圖1 二叉樹(shù)基本操作程序主菜單2、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本程序采用二叉鏈?zhǔn)酱鎯?chǔ)類型(BiTNode)存儲(chǔ)二叉樹(shù)的結(jié)點(diǎn)信息。二叉樹(shù)的鏈表中的結(jié)點(diǎn)至少包含3個(gè)域：數(shù)據(jù)域(data)、左孩子指針域(lchild)、右孩子指針域(rchild)。3、系統(tǒng)功能設(shè)計(jì)本程序除了完成二叉樹(shù)的創(chuàng)建功能外還設(shè)置了9個(gè)子功能菜單。由于

3、這9個(gè)子功能都是建立在二叉樹(shù)的構(gòu)造上的，所以二叉樹(shù)的創(chuàng)建由主函數(shù)main()實(shí)現(xiàn)。9個(gè)子功能的設(shè)計(jì)描述如下：樹(shù)狀輸出二叉樹(shù)。樹(shù)狀輸出二叉樹(shù)由函數(shù)TranslevelPrint()實(shí)現(xiàn)。當(dāng)用戶選擇此功能時(shí)，系統(tǒng)即以樹(shù)狀的形式輸出用戶所創(chuàng)建的二叉樹(shù)。先序遍歷二叉樹(shù)。由函數(shù)Preorder()實(shí)現(xiàn)。該功能按照先序遍歷訪問(wèn)二叉樹(shù)的方法輸出先序序列。中序遍歷二叉樹(shù)。由函數(shù)Inorder()實(shí)現(xiàn)。該功能按照中序遍歷訪問(wèn)二叉樹(shù)的方法輸出中序序列。后序遍歷二叉樹(shù)。由函數(shù)Postorder()實(shí)現(xiàn)。該功能按照后序遍歷訪問(wèn)二叉樹(shù)的方法輸出后序序列。輸出葉子結(jié)點(diǎn)。該功能采用先序遍歷二叉樹(shù)的方法依次輸出葉子結(jié)點(diǎn)。由函

4、數(shù)Preorderleaf()實(shí)現(xiàn)。輸出葉子結(jié)點(diǎn)個(gè)數(shù)。該功能計(jì)算并輸出二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)，由LeafCount()實(shí)現(xiàn)。采用遞歸算法計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)，算法思想是：當(dāng)二叉樹(shù)為空樹(shù)時(shí)，葉子結(jié)點(diǎn)總數(shù)為0；當(dāng)二叉樹(shù)只有1個(gè)結(jié)點(diǎn)時(shí)，葉子結(jié)點(diǎn)總數(shù)為1；否則，葉子結(jié)點(diǎn)個(gè)數(shù)等于左右子樹(shù)葉子結(jié)點(diǎn)數(shù)之和。輸出二叉樹(shù)的深度。該功能輸出二叉樹(shù)的深度，由函數(shù)PostorderDepth()實(shí)現(xiàn)，采用后序遍歷的遞歸算法求二叉樹(shù)的深度。括號(hào)形式輸出二叉樹(shù)。以括號(hào)形式輸出二叉樹(shù)由函數(shù)，由函數(shù)output()實(shí)現(xiàn)。當(dāng)用戶選擇此功能時(shí)，系統(tǒng)即以括號(hào)形式輸出二叉樹(shù)。退出。由exit(0)函數(shù)實(shí)現(xiàn)。三、模塊設(shè)計(jì)1、模塊

5、設(shè)計(jì)本程序包含三個(gè)模塊，主程序模塊、建立二叉樹(shù)模塊和工作區(qū)選擇模塊。其調(diào)用關(guān)系如圖2所示。主程序模塊建立二叉樹(shù)模塊工作區(qū)選擇模塊圖2 模塊調(diào)用示意圖2、系統(tǒng)子程序用功能設(shè)計(jì)本系統(tǒng)共設(shè)置12個(gè)子程序，各子程序的函數(shù)名及功能說(shuō)明如下：void CreateBiTree(BiTree &T) /先序建立二叉樹(shù)void TranslevelPrint(BiTree T) /樹(shù)形打印二叉樹(shù)void Visit(char ch) /輸出結(jié)點(diǎn)void Preorder(BiTree T) /先序遍歷二叉樹(shù)void Inorder(BiTree T) /中序遍歷二叉樹(shù)void Postorder(Bi

6、Tree T) /后序遍歷二叉樹(shù)void PreorderLeaf(BiTree T) /輸出葉子結(jié)點(diǎn)int LeafCount(BiTree T) /輸出葉子結(jié)點(diǎn)的個(gè)數(shù)int PostorderDepth(BiTree T) /輸出二叉樹(shù)的深度void output(BiTree T) /以括號(hào)形式輸出二叉樹(shù)void mainwork() /主工作函數(shù)，操作區(qū)用戶界面void main() /主函數(shù)。創(chuàng)建二叉樹(shù)，調(diào)用工作區(qū)模塊函數(shù)3、函數(shù)主要調(diào)用關(guān)系圖本系統(tǒng)12個(gè)子程序之間的主要調(diào)用關(guān)系如圖3所示。圖中數(shù)字是各函數(shù)的編號(hào)。圖3系統(tǒng)函數(shù)調(diào)用關(guān)系圖四、詳細(xì)設(shè)計(jì)1、數(shù)據(jù)類型定義typedef st

7、ruct BiTNode /定義二叉樹(shù)結(jié)點(diǎn)結(jié)構(gòu) char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;2、系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)主函數(shù)模塊主函數(shù)。創(chuàng)建二叉樹(shù)，調(diào)用工作區(qū)模塊函數(shù)。void main() cout<<"首先請(qǐng)輸入二叉樹(shù)結(jié)點(diǎn)序列： n" CreateBiTree(T); cout<<"請(qǐng)按菜單提示操作：n" mainwork();建立二叉樹(shù)模塊void CreateBiTree(BiTree &T)/先序建立二叉樹(shù) char ch; cin>&

8、gt;ch; if(ch='#') T=NULL; else T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); 用戶工作區(qū)模塊主工作函數(shù)，操作區(qū)用戶界面設(shè)計(jì)。void mainwork() int yourchoice; cout<<"n-歡迎使用二叉樹(shù)基本操作程序-n" cout<<"n 菜單選擇 nn" cout<<" 1. 樹(shù)狀輸出二叉樹(shù) 2. 先序遍歷二叉樹(shù) n&q

9、uot; cout<<" 3. 中序遍歷二叉樹(shù) 4. 后序遍歷二叉樹(shù) n" cout<<" 5. 輸出葉子結(jié)點(diǎn) 6. 輸出葉子結(jié)點(diǎn)個(gè)數(shù) n" cout<<" 7. 輸出二叉樹(shù)的深度 8. 括號(hào)形式輸出二叉樹(shù) n" cout<<" 9. 退出 n" cout<<"n-n" cout<<"請(qǐng)輸入你的選擇： " cin>>yourchoice; while(!(yourchoice=1|yourch

10、oice=2|yourchoice=4|yourchoice=5| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) cout<<"輸入不正確，請(qǐng)重新輸入n" cin>>yourchoice; while(1) switch(yourchoice) case 1:cout<<"樹(shù)的形狀為：" TranslevelPrint(T);break; case 2:cout<<"先序遍歷為：" Preorder(T);break; case

11、 3:cout<<"中序遍歷為：" Inorder(T);break; case 4:cout<<"后序遍歷為：" Postorder(T);break; case 5:cout<<"葉子結(jié)點(diǎn)為：" PreorderLeaf(T);break; case 6:cout<<"葉子結(jié)點(diǎn)個(gè)數(shù)為："<<LeafCount(T);break; case 7:cout<<"二叉樹(shù)的深度為："<<PostorderDepth(

12、T);break; case 8:cout<<"括號(hào)形式輸出二叉樹(shù)為:"output(T);break; case 9:system("cls"); exit(0); break; default: break; cout<<"n按任意鍵繼續(xù)：" getch(); system("cls"); cout<<"n-歡迎使用二叉樹(shù)基本操作程序-n" cout<<"n 菜單選擇 nn" cout<<" 1. 樹(shù)狀

13、輸出二叉樹(shù) 2. 先序遍歷二叉樹(shù) n" cout<<" 3. 中序遍歷二叉樹(shù) 4. 后序遍歷二叉樹(shù) n" cout<<" 5. 輸出葉子結(jié)點(diǎn) 6. 輸出葉子結(jié)點(diǎn)個(gè)數(shù) n" cout<<" 7. 輸出二叉樹(shù)的深度 8. 括號(hào)形式輸出二叉樹(shù) n" cout<<" 9. 退出 n" cout<<"n-n" cout<<"請(qǐng)輸入你的選擇： " cin>>yourchoice; /endwhi

14、le(1)/endmainwork五、測(cè)試結(jié)果根據(jù)先根結(jié)點(diǎn)，按照從上到下，從左到右的次序依次先根遍歷的方法，分別輸入二叉樹(shù)的結(jié)點(diǎn)序列（#號(hào)表示該結(jié)點(diǎn)為空）。例如，輸入“ABD#E#CH#”，程序運(yùn)行得到如圖1所示的開(kāi)始界面。各子功能測(cè)試運(yùn)行結(jié)果如下。1、樹(shù)狀輸出二叉樹(shù)在主菜單下，用戶輸入1并回車，運(yùn)行結(jié)果如圖4所示。 圖4 按樹(shù)形輸出所創(chuàng)建的二叉樹(shù)2、先序遍歷二叉樹(shù)在主菜單下，用戶輸入2并回車，運(yùn)行結(jié)果如圖5所示。圖5 輸出二叉樹(shù)的先序遍歷序列3、中序遍歷二叉樹(shù)在主菜單下，用戶輸入3并回車，運(yùn)行結(jié)果如圖6所示。4、后序遍歷二叉樹(shù)在主菜單下，用戶輸入4并回車，運(yùn)行結(jié)果如圖7所示。 圖6 輸出二叉

15、樹(shù)的中序遍歷序列 圖7 輸出二叉樹(shù)的后序遍歷序列5、輸出葉子結(jié)點(diǎn)在主菜單下，用戶輸入5并回車，運(yùn)行結(jié)果如圖8所示。6、輸出葉子結(jié)點(diǎn)個(gè)數(shù)在主菜單下，用戶輸入6并回車，運(yùn)行結(jié)果如圖9所示。 圖8 輸出二叉樹(shù)的葉子結(jié)點(diǎn) 圖9輸出二叉樹(shù)的葉子結(jié)點(diǎn)個(gè)數(shù)7、輸出二叉樹(shù)的深度在主菜單下，用戶輸入7并回車，運(yùn)行結(jié)果如圖10所示。8、括號(hào)形式輸出二叉樹(shù)在主菜單下，用戶輸入8并回車，運(yùn)行結(jié)果如圖11所示。 圖10 輸出二叉樹(shù)的深度 圖11 以括號(hào)形式輸出二叉樹(shù)9、退出在主菜單下，用戶輸入9并回車，即退出“二叉樹(shù)基本操作程序”。六、用戶使用說(shuō)明1、本程序執(zhí)行文件為“二叉樹(shù)的基本操作演示.exe”。2、進(jìn)入本程序后，

16、首先按照提示輸入二叉樹(shù)的結(jié)點(diǎn)，如按下列次序順序讀入字符ABD#E#CH#。 3、隨即顯示系統(tǒng)主菜單界面，用戶可在該界面下輸入各功能前對(duì)應(yīng)的數(shù)字并按回車，執(zhí)行相應(yīng)命令。七、實(shí)驗(yàn)體會(huì)（略）八、源程序清單/二叉樹(shù)基本操作演示程序的設(shè)計(jì)與實(shí)現(xiàn)/二叉樹(shù)的基本操作演示.CPP#include <iostream.h>#include "stdlib.h"#include "conio.h"#include "math.h"#define MaxSize 100#define NLAYER 4typedef struct BiTNode

17、 char data; struct BiTNode *lchild,*rchild;BiTNode,*BiTree;BiTree T;/1.建立二叉樹(shù)void CreateBiTree(BiTree &T)/先序建立二叉樹(shù) char ch; cin>>ch; if(ch='#') T=NULL; else T=new BiTNode; T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); /2.樹(shù)形打印二叉樹(shù)void TranslevelPrint(BiTree T)

18、/本算法實(shí)現(xiàn)二叉樹(shù)按層打印 struct node BiTree vecMaxSize; /存放樹(shù)結(jié)點(diǎn) int layerMaxSize; /結(jié)點(diǎn)所在的層 int locateMaxSize; /打印結(jié)點(diǎn)的位置int front,rear; q; /定義隊(duì)列q int i,j=1,k=0,nLocate; q.front=q.rear=0; /初始化隊(duì)列q隊(duì)頭、隊(duì)尾 cout<<"n " q.vecq.rear=T; /二叉樹(shù)的根結(jié)點(diǎn)入隊(duì) q.layerq.rear=1; q.locateq.rear=20; q.rear=q.rear+1; while(q.f

19、ront<q.rear) T=q.vecq.front; i=q.layerq.front; nLocate=q.locateq.front; if(j<i) /進(jìn)層打印時(shí)換行 cout<<"nn" j=j+1; k=0; while(k+<nLocate) cout<<" "while(k+<nLocate-1) cout<<" " /結(jié)點(diǎn)深度控制橫向位置cout<<T->data;q.front=q.front+1;if(T->lchild!=NU

20、LL) /存在左子樹(shù)，將左子樹(shù)的根結(jié)點(diǎn)入隊(duì)列 q.vecq.rear=T->lchild; q.layerq.rear=i+1; q.locateq.rear=int(nLocate-pow(2,NLAYER-i-1); q.rear=q.rear+1;if(T->rchild!=NULL) /存在右子樹(shù)，將右子樹(shù)的根結(jié)點(diǎn)入隊(duì)列 q.vecq.rear=T->rchild; q.layerq.rear=i+1; q.locateq.rear=int(nLocate+pow(2,NLAYER-i-1); q.rear=q.rear+1; /3.輸出結(jié)點(diǎn)void Visit(ch

21、ar ch) cout<<ch;/4.先序遍歷二叉樹(shù)void Preorder(BiTree T)/先序遍歷二叉樹(shù)，T為指向二叉樹(shù)（或某一子樹(shù)）根結(jié)點(diǎn)的指針 if(T!=NULL) Visit(T->data); /訪問(wèn)根結(jié)點(diǎn) Preorder(T->lchild); /先序遍歷左子樹(shù) Preorder(T->rchild); /先序遍歷右子樹(shù) /5.中序遍歷二叉樹(shù)void Inorder(BiTree T)/中序遍歷二叉樹(shù)，T為指向二叉樹(shù)（或某一子樹(shù)）根結(jié)點(diǎn)的指針 if(T!=NULL) Inorder(T->lchild); /中序遍歷左子樹(shù) Visit

22、(T->data); /訪問(wèn)根結(jié)點(diǎn) Inorder(T->rchild); /中序遍歷右子樹(shù) /6.后序遍歷二叉樹(shù)void Postorder(BiTree T)/后序遍歷二叉樹(shù)，T為指向二叉樹(shù)（或某一子樹(shù)）根結(jié)點(diǎn)的指針 if(T!=NULL) Postorder(T->lchild); /后序遍歷左子樹(shù) Postorder(T->rchild); /后序遍歷右子樹(shù) Visit(T->data); /訪問(wèn)根結(jié)點(diǎn) /7.輸出葉子結(jié)點(diǎn)void PreorderLeaf(BiTree T)/先序遍歷二叉樹(shù)并輸出葉子結(jié)點(diǎn)，T為指向二叉樹(shù)根結(jié)點(diǎn)的指針 if(T!=NULL)

23、 if(T->lchild=NULL&&T->rchild=NULL) Visit(T->data); /訪問(wèn)根結(jié)點(diǎn) PreorderLeaf(T->lchild); /先序遍歷左子樹(shù) PreorderLeaf(T->rchild); /先序遍歷右子樹(shù) /8.輸出葉子結(jié)點(diǎn)的個(gè)數(shù)int LeafCount(BiTree T) int LeafNum; if(T=NULL) LeafNum=0; else if(T->lchild=NULL)&&(T->rchild=NULL) LeafNum=1; else LeafNum

24、=LeafCount(T->lchild)+LeafCount(T->rchild); return LeafNum;/9.輸出二叉樹(shù)的深度int PostorderDepth(BiTree T) /后序遍歷求二叉樹(shù)深度的遞歸算法 int hl,hr,max; if(T!=NULL) hl=PostorderDepth(T->lchild); /求左子樹(shù)的深度 hr=PostorderDepth(T->rchild); /求右子樹(shù)的深度 max=hl>hr?hl:hr; /得到左右子樹(shù)深度較大者 return (max+1); /返回樹(shù)的深度 else retur

25、n 0; /空樹(shù)返回0/10. 以括號(hào)形式輸出二叉樹(shù)void output(BiTree T) if(T!=NULL) cout<<T->data; if(T->lchild!=NULL|T->rchild!=NULL) cout<<"(" output(T->lchild); if(T->rchild!=NULL) cout<<"," output(T->rchild); cout<<")" /11.主工作函數(shù)，操作區(qū)用戶界面void mainwor

26、k() int yourchoice; cout<<"n-歡迎使用二叉樹(shù)基本操作程序-n" cout<<"n 菜單選擇 nn" cout<<" 1. 樹(shù)狀輸出二叉樹(shù) 2. 先序遍歷二叉樹(shù) n" cout<<" 3. 中序遍歷二叉樹(shù) 4. 后序遍歷二叉樹(shù) n" cout<<" 5. 輸出葉子結(jié)點(diǎn) 6. 輸出葉子結(jié)點(diǎn)個(gè)數(shù) n" cout<<" 7. 輸出二叉樹(shù)的深度 8. 括號(hào)形式輸出二叉樹(shù) n" cout&

27、lt;<" 9. 退出 n" cout<<"n-n" cout<<"請(qǐng)輸入你的選擇： " cin>>yourchoice; while(!(yourchoice=1|yourchoice=2|yourchoice=4|yourchoice=5| yourchoice=6|yourchoice=7|yourchoice=8|yourchoice=9) cout<<"輸入不正確，請(qǐng)重新輸入n" cin>>yourchoice; while(1) switch(yourchoice) case 1:cout<<"樹(shù)的形狀為：" TranslevelPrint(T);break; case 2:cout<<"先序遍歷為：" Preorder(T);break; case 3:cout<<"中序遍歷為：" Inorder(T);break; case 4:cout<<"后序遍歷為：" Postorder(T);break; ca