二叉樹的基本操作_第1頁
二叉樹的基本操作_第2頁
二叉樹的基本操作_第3頁
二叉樹的基本操作_第4頁
二叉樹的基本操作_第5頁
已閱讀5頁,還剩6頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

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)

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論