二叉樹的基本操作

1、浙江大學城市學院實驗報告課程名稱 數據結構基礎 實驗項目名稱 實驗十 二叉樹的基本操作 學生姓名 吳奇 專業(yè)班級 信管1204 學號 31201403 實驗成績 指導老師（簽名 ） 日期 一. 實驗目的和要求1、掌握二叉樹的鏈式存儲結構。2、掌握在二叉鏈表上的二叉樹操作的實現原理與方法。3、進一步掌握遞歸算法的設計方法。二. 實驗內容1、按照下面二叉樹二叉鏈表的存儲表示，編寫頭文件binary_tree.h，實現二叉鏈表的定義與基本操作實現函數；編寫主函數文件test4_1.cpp，驗證頭文件中各個操作。二叉樹二叉鏈表存儲表示如下：struct BTreeNode ElemType data;

2、 / 結點值域 BTreeNode *lchild , *rchild ; / 定義左右孩子指針 ;基本操作如下：void InitBTree( BTreeNode *&BT ); /初始化二叉樹BT void CreateBTree( BTreeNode *&BT, char *a ); /根據字符串a所給出的廣義表表示的二叉樹建立二叉鏈表存儲結構 int EmptyBTree( BTreeNode *BT); /檢查二叉樹BT是否為空，空返回1，否則返回0 int DepthBTree( BTreeNode *BT);/求二叉樹BT的深度并返回該值 int FindBTree( BTree

3、Node *BT, ElemType x); /查找二叉樹BT中值為x的結點，若查找成功返回1，否則返回0 void PreOrder( BTreeNode *BT);/先序遍歷二叉樹BTvoid InOrder( BTreeNode *BT);/中序遍歷二叉樹BTvoid PostOrder( BTreeNode *BT); /后序遍歷二叉樹BT void PrintBTree( BTreeNode *BT ); /輸出二叉樹BT void ClearBTree( BTreeNode *&BT ); /清除二叉樹BT2、選做：實現以下說明的操作函數，要求把函數添加到頭文件binary_tre

4、e.h中，并在主函數文件test4_1.cpp中添加相應語句進行測試。void LevelOrder( BTreeNode *BT )/二叉樹的層序遍歷int Get_Sub_Depth( BTreeNode *T , ElemType x)/求二叉樹中以元素值為x的結點為根的子樹的深度3、填寫實驗報告，實驗報告文件取名為report10.doc。4、上傳實驗報告文件report10.doc 、源程序文件test4_1.cpp及binary_tree.h到Ftp服務器上自己的文件夾下。三. 函數的功能說明及算法思路 struct BtreeNode elemtype data; /結點值域 B

5、treeNode *lchild; /定義左孩子指針BtreeNode *rchild; /定義右孩子指針;struct lnode /定義隊列結點結構用于二叉樹層遍歷BtreeNode *data1;lnode *next;struct Queue /定義隊列首尾指針lnode *front;lnode *back;void initQueue(Queue &Q) /初始化隊列Q.front=Q.back=NULL;void insertQueue(Queue &Q,BtreeNode *item) /元素入隊列l(wèi)node *newptr=new lnode;newptr-data1=ite

6、m;newptr-next=NULL;if(Q.back=NULL)Q.front=Q.back=newptr;elseQ.back=Q.back-next=newptr;BtreeNode *deleteQueue(Queue &Q) /隊首元素出隊列BtreeNode *temp=Q.front-data1;lnode *p=Q.front;Q.front=p-next;if(Q.front=NULL)Q.back=NULL;delete p;return temp;bool emptyQueue(Queue Q) /判斷隊列是否為空return Q.front=NULL;void ini

7、tBtree(BtreeNode *&BT) /二叉樹的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /創(chuàng)建二叉樹elemtype ch;ch=getchar();if(ch=$) /判斷是不是結束標志BT=NULL;elseBT=new BtreeNode; /創(chuàng)建結點BT-data=ch; /賦值insertBtree(BT-lchild); /左子葉遞歸insertBtree(BT-rchild); /右子葉遞歸bool emptyBtree(BtreeNode *BT) /判斷二叉樹是否為空return BT=NULL;int depthBtr

8、ee(BtreeNode *BT) /求二叉樹的深度if(emptyBtree(BT) return 0;elseint dep1=depthBtree(BT-lchild); /左子葉遞歸int dep2=depthBtree(BT-rchild); /右子葉遞歸return dep1dep2?dep1+1:dep2+1; /判斷哪個子葉的深度最大 /樹的深度為左右子葉的最大深度加上1void preorder(BtreeNode *BT) /前序遍歷if(!emptyBtree(BT)coutdatalchild); /左子葉遞歸preorder(BT-rchild); /右子葉遞歸voi

9、d midorder(BtreeNode *BT) /中序遍歷if(!emptyBtree(BT)midorder(BT-lchild); /左子葉遞歸coutdatarchild); /右子葉遞歸void laterorder(BtreeNode *BT) /后序遍歷if(!emptyBtree(BT)laterorder(BT-lchild); /左子葉遞歸laterorder(BT-rchild); /右子葉遞歸coutdatadata=x) /找到，返回truereturn true;elseif(findBtree(BT-lchild,x) /左子葉遞歸查找return true;i

10、f(findBtree(BT-rchild,x) /右子葉遞歸查找return true;return false;void levelorder(BtreeNode *BT) /按層遍歷二叉樹Queue queue; /用于存放二叉樹結點的隊列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉樹不為空，根節(jié)點入隊insertQueue(queue,BT);while(!emptyQueue(queue) /當隊列不為空時，隊首元素出隊列P=deleteQueue(queue);coutdatalchild!=NULL) /當左右子葉不為空

11、時，遞歸insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉樹中以元素值為x的結點為根的子樹的深度int m,n;if(!emptyBtree(BT) /二叉樹非空if(BT-data=x) /找到，返回其深度return depthBtree(BT);elsem=Get_Sub_Depth(BT-lchild,x); /左右子葉遞歸，返回深度n=Get_Sub_Depth(BT-rchild,x);ret

12、urn mn?m:n;elsereturn 0;void printBtree(BtreeNode *BT,int n) /打印二叉樹 int i;if(emptyBtree(BT) /二叉樹為空，返回return;printBtree(BT-rchild,n+1); /先遞歸輸出右子樹for(i=0;in;i+) cout ; /前導空格，表示層次cout-;coutdata; /結點的值coutlchild,n+1); /再遞歸輸出右子樹void PrintBtree(BtreeNode *BT) /二叉樹的廣義表打印if(!emptyBtree(BT)coutdata;if(!empty

13、Btree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild);coutdata1=item;newptr-next=NULL;if(Q.back=NULL)Q.front=Q.back=newptr;elseQ.back=Q.back-next=newptr;BtreeNode *deleteQueue(Queue &Q) /隊首元素出隊列BtreeNode *temp=Q.front-data1;lnode *p=Q.front;Q.front=p-next;if(Q.front

14、=NULL)Q.back=NULL;delete p;return temp;bool emptyQueue(Queue Q) /判斷隊列是否為空return Q.front=NULL;void initBtree(BtreeNode *&BT) /二叉樹的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /創(chuàng)建二叉樹elemtype ch;ch=getchar();if(ch=$) /判斷是不是結束標志BT=NULL;elseBT=new BtreeNode; /創(chuàng)建結點BT-data=ch; /賦值insertBtree(BT-lchild); /左子

15、葉遞歸insertBtree(BT-rchild); /右子葉遞歸bool emptyBtree(BtreeNode *BT) /判斷二叉樹是否為空return BT=NULL;int depthBtree(BtreeNode *BT) /求二叉樹的深度if(emptyBtree(BT) return 0;elseint dep1=depthBtree(BT-lchild); /左子葉遞歸int dep2=depthBtree(BT-rchild); /右子葉遞歸return dep1dep2?dep1+1:dep2+1; /判斷哪個子葉的深度最大 /樹的深度為左右子葉的最大深度加上1void

16、 preorder(BtreeNode *BT) /前序遍歷if(!emptyBtree(BT)coutdatalchild); /左子葉遞歸preorder(BT-rchild); /右子葉遞歸void midorder(BtreeNode *BT) /中序遍歷if(!emptyBtree(BT)midorder(BT-lchild); /左子葉遞歸coutdatarchild); /右子葉遞歸void laterorder(BtreeNode *BT) /后序遍歷if(!emptyBtree(BT)laterorder(BT-lchild); /左子葉遞歸laterorder(BT-rch

17、ild); /右子葉遞歸coutdatadata=x) /找到，返回truereturn true;elseif(findBtree(BT-lchild,x) /左子葉遞歸查找return true;if(findBtree(BT-rchild,x) /右子葉遞歸查找return true;return false;void levelorder(BtreeNode *BT) /按層遍歷二叉樹Queue queue; /用于存放二叉樹結點的隊列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉樹不為空，根節(jié)點入隊insertQueue(qu

18、eue,BT);while(!emptyQueue(queue) /當隊列不為空時，隊首元素出隊列P=deleteQueue(queue);coutdatalchild!=NULL) /當左右子葉不為空時，遞歸insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉樹中以元素值為x的結點為根的子樹的深度int m,n;if(!emptyBtree(BT) /二叉樹非空if(BT-data=x) /找到，返回其深

19、度return depthBtree(BT);elsem=Get_Sub_Depth(BT-lchild,x); /左右子葉遞歸，返回深度n=Get_Sub_Depth(BT-rchild,x);return mn?m:n;elsereturn 0;void printBtree(BtreeNode *BT,int n) /打印二叉樹 int i;if(emptyBtree(BT) /二叉樹為空，返回return;printBtree(BT-rchild,n+1); /先遞歸輸出右子樹for(i=0;in;i+) cout ; /前導空格，表示層次cout-;coutdata; /結點的值coutlchild,n+1); /再遞歸輸出右子樹void PrintBtree(BtreeNode *BT) /二叉樹的廣義表打印if(!emptyBtree(BT)coutdata;if(!emptyBtree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild)