二叉樹的基本操作

1、浙江大學(xué)城市學(xué)院實(shí)驗(yàn)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ) 實(shí)驗(yàn)項(xiàng)目名稱 實(shí)驗(yàn)十 二叉樹的基本操作 學(xué)生姓名 吳奇 專業(yè)班級(jí) 信管1204 學(xué)號(hào) 31201403 實(shí)驗(yàn)成績(jī) 指導(dǎo)老師（簽名 ） 日期 一. 實(shí)驗(yàn)?zāi)康暮鸵?、掌握二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2、掌握在二叉鏈表上的二叉樹操作的實(shí)現(xiàn)原理與方法。3、進(jìn)一步掌握遞歸算法的設(shè)計(jì)方法。二. 實(shí)驗(yàn)內(nèi)容1、按照下面二叉樹二叉鏈表的存儲(chǔ)表示，編寫頭文件binary_tree.h，實(shí)現(xiàn)二叉鏈表的定義與基本操作實(shí)現(xiàn)函數(shù)；編寫主函數(shù)文件test4_1.cpp，驗(yàn)證頭文件中各個(gè)操作。二叉樹二叉鏈表存儲(chǔ)表示如下：struct BTreeNode ElemType data;

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

3、Node *BT, ElemType x); /查找二叉樹BT中值為x的結(jié)點(diǎn)，若查找成功返回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、選做：實(shí)現(xiàn)以下說明的操作函數(shù)，要求把函數(shù)添加到頭文件binary_tre

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

5、treeNode *lchild; /定義左孩子指針BtreeNode *rchild; /定義右孩子指針;struct lnode /定義隊(duì)列結(jié)點(diǎn)結(jié)構(gòu)用于二叉樹層遍歷BtreeNode *data1;lnode *next;struct Queue /定義隊(duì)列首尾指針lnode *front;lnode *back;void initQueue(Queue &Q) /初始化隊(duì)列Q.front=Q.back=NULL;void insertQueue(Queue &Q,BtreeNode *item) /元素入隊(duì)列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) /隊(duì)首元素出隊(duì)列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) /判斷隊(duì)列是否為空return Q.front=NULL;void ini

7、tBtree(BtreeNode *&BT) /二叉樹的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /創(chuàng)建二叉樹elemtype ch;ch=getchar();if(ch=$) /判斷是不是結(jié)束標(biāo)志BT=NULL;elseBT=new BtreeNode; /創(chuàng)建結(jié)點(diǎn)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; /判斷哪個(gè)子葉的深度最大 /樹的深度為左右子葉的最大深度加上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; /用于存放二叉樹結(jié)點(diǎn)的隊(duì)列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉樹不為空，根節(jié)點(diǎn)入隊(duì)insertQueue(queue,BT);while(!emptyQueue(queue) /當(dāng)隊(duì)列不為空時(shí)，隊(duì)首元素出隊(duì)列P=deleteQueue(queue);coutdatalchild!=NULL) /當(dāng)左右子葉不為空

11、時(shí)，遞歸insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度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 ; /前導(dǎo)空格，表示層次cout-;coutdata; /結(jié)點(diǎn)的值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) /隊(duì)首元素出隊(duì)列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) /判斷隊(duì)列是否為空return Q.front=NULL;void initBtree(BtreeNode *&BT) /二叉樹的初始化BT=NULL;void insertBtree(BtreeNode *&BT) /創(chuàng)建二叉樹elemtype ch;ch=getchar();if(ch=$) /判斷是不是結(jié)束標(biāo)志BT=NULL;elseBT=new BtreeNode; /創(chuàng)建結(jié)點(diǎn)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; /判斷哪個(gè)子葉的深度最大 /樹的深度為左右子葉的最大深度加上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; /用于存放二叉樹結(jié)點(diǎn)的隊(duì)列initQueue(queue);BtreeNode *P;if(!emptyBtree(BT) /二叉樹不為空，根節(jié)點(diǎn)入隊(duì)insertQueue(qu

18、eue,BT);while(!emptyQueue(queue) /當(dāng)隊(duì)列不為空時(shí)，隊(duì)首元素出隊(duì)列P=deleteQueue(queue);coutdatalchild!=NULL) /當(dāng)左右子葉不為空時(shí)，遞歸insertQueue(queue,P-lchild);if(P-rchild!=NULL)insertQueue(queue,P-rchild);int Get_Sub_Depth(BtreeNode *BT,elemtype x)/求二叉樹中以元素值為x的結(jié)點(diǎn)為根的子樹的深度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 ; /前導(dǎo)空格，表示層次cout-;coutdata; /結(jié)點(diǎn)的值coutlchild,n+1); /再遞歸輸出右子樹void PrintBtree(BtreeNode *BT) /二叉樹的廣義表打印if(!emptyBtree(BT)coutdata;if(!emptyBtree(BT-lchild)|!emptyBtree(BT-rchild)coutlchild);if(!emptyBtree(BT-rchild)coutrchild)