二叉樹的遍歷課程設計C++含源代碼_第1頁
二叉樹的遍歷課程設計C++含源代碼_第2頁
二叉樹的遍歷課程設計C++含源代碼_第3頁
二叉樹的遍歷課程設計C++含源代碼_第4頁
二叉樹的遍歷課程設計C++含源代碼_第5頁
免費預覽已結束,剩余11頁可下載查看

下載本文檔

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

文檔簡介

1、數據結構課程設計報告設計題目:二叉樹的遍歷姓名:陳雷學號:211001047專業:計算機科學與技術院系:計算機科學與技術班級:1002指導教師:吳克力2012 年 3 月 1 日摘要: 本文主要說明如何實現二叉樹的遍歷。此次二叉樹的遍歷基于二叉樹的二叉鏈表存儲結構。遍歷方式包括:前序遍歷,中序遍歷,后續遍歷,層序遍歷。其中前序遍歷和后續遍歷采用非遞歸算法實現。編程環境為 VC+除了遍歷操作外,還增加了求二叉樹的深度,總結點數,每層結點數,以及最近共同祖先(LCQ 問題的算法。關鍵字:二叉樹遍歷非遞歸 C+LCAAbstract:Thispapermainlydescribeshowtoimpl

2、ementbinarytreetraversal.Thebinarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC+,inadditiontotravers

3、aloperation,alsoincreasedforsolvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC+LCA目錄、問題描述 4.4.問題描述:創建二叉樹并遍歷 4基本要求:4二、需求分析 4.4.三、概要設計 4.4.1 . .創建二叉樹 42 . .二叉樹的非遞歸前序遍歷示意圖 43 .二叉樹的后序非遞歸遍歷示意圖 5四、數據結構設計 5

4、.5.1.1.二叉樹結點數據類型定義為:52.2.二叉樹數據類型定義為:5五、算法設計 6.6.1 1、創建二叉樹 62 2、非遞歸前序遍歷 73 3、非遞歸后序遍歷 74 4、求二叉樹的高度 85、求二叉樹每一層的結點數 96、求兩節點最近共同祖先 96 6、算法流程圖 10六、程序測試與實現 1.11.11 1、函數之間的調用關系 112 2、主程序 113 3、測試數據 134 4、測試結果 13七、調試分析 1414八、遇到的問題及解決辦法 1515九、心得體會 1515十、參考文獻 1515一、問題描述問題描述:創建二叉樹并遍歷基本要求:1、分別運用非遞歸的方式完成對二叉樹的先序和后

5、序遍歷2、輸出二叉樹的高度3、輸出每一層的結點數4、查找結點 P 和結點 Q 的最近共同祖先二、需求分析1 .本程序的功能包括二叉樹的建立,二叉樹的遞歸遍歷,二叉樹的非遞歸遍歷,查詢二叉樹的深度,查詢每層的結點數,查找兩個結點的最近共同祖先,二叉樹的打印。2 .程序運行后顯現提示信息,等候用戶輸入 06 以進入相應的操作功能。3 .用戶輸入數據完畢,程序將輸出運行結果。4 .測試數據應為字符型數據。三、概要設計1 1 . .創建二叉樹輸入數據不低于 15 個,用遞歸方法建立二叉樹。2 2 . .二叉樹的非遞歸前序遍歷示意圖圖 3.23.2 二叉樹前序遍歷示意圖3 3 . .二叉樹的后序非遞歸遍

6、歷示意圖圖 3.43.4 二叉樹后序遍歷示意圖四、數據結構設計1 1 . .二叉樹結點數據類型定義為:templatestructBiNode(BiNode*rchild,*lchild;/指向左右孩子的指針Tdata;/結點數據信息;2 2 . .二叉樹數據類型定義為:templateclassBiTree(templatefriendostream&operator(ostream&os,BiTree&bt);public:BiTree();/無參構造函數BiTree(intm);/有參空構造函數BiTree(Tary,intnum,Tnone);/有參構造函數Bi

7、Tree();/析構函數voidpreorder();/遞歸前序遍歷voidinorder();/遞歸中序遍歷voidpostorder();/遞歸后續遍歷voidlevelorder();/層序遍歷 intcount();/計算二叉樹的結點數intdepth();/計算二叉樹的深度voiddisplay(ostream&os);打印二叉樹,有層次voidLevelNum();/計算每一層結點數voidPreOrder();/非遞歸前序遍歷voidPostOrder();/非遞歸后序遍歷voidcreat();/創建二叉樹TleastCommanAncestor(Tva,Tvb);/求

8、樹中任意兩結點最近共同祖先 protected:/以下函數供上面函數調用/對應相同功能voidcreat(BiNode*&root);創建voidrelease(BiNode*&root);/刪除BiNode*Build(Tary,intnum,Tnone,intidx);用數組創建二叉樹voidPreOrder(BiNode*root);/前序遍歷voidPostOrder(BiNode*root);后續遍歷voidLevelNum(BiNode*root);/層序遍歷voidpreorder(BiNode*root);/遞歸前序遍歷voidinorder(BiNode*ro

9、ot);遞歸中序遍歷voidpostorder(BiNode*root);/遞歸后續遍歷voidlevelorder(BiNode*root);/層序遍歷intcount(BiNode*root);計算結點數intdepth(BiNode*root);計算深度voiddisplay(ostream&os,BiNode*root,intdep);打印staticboolleastCommanAncestor(BiNode*root,Tva,Tvb,BiNode*&result,BiNode*parrent);/求最近共同祖先 private:BiNode*rootptr;);五、

10、算法設計1、創建二叉樹/實現外部遞歸調用voidBiTree:creat()(creat(rootptr);)/類體內遞歸創建二叉樹templatevoidBiTree:creat(BiNode*&root)(Titem;cinitem;if(item=#)root=NULL;else(root=newBiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非遞歸前序遍歷templatevoidBiTree:PreOrder()PreOrder(rootptr);templatevoidBiTree:PreOrder(

11、BiNode*root)stackBiNode*s;while(root!=NULL|!s.empty()while(root)coutdata;s.push(root);root=root-lchild;if(!s.empty()root=s.top();s.pop();root=root-rchild;3、非遞歸后序遍歷templatevoidBiTree:PostOrder()PostOrder(rootptr);templatevoidBiTree:PostOrder(BiNode*root)stackBiNode*s;/定義棧,節點類型為 TreeNodeBiNode*p=root;

12、BiNode*pre=NULL;/pre 表示最近一次訪問的結點while(p|!s.empty()(/沿著左孩子方向走到最左下。while(p)(s.push(p);p=p-lchild;)/getthetopelementofthestackp=s.top();/如果 p 沒有右孩子或者其右孩子剛剛被訪問過 if(p-rchild=NULL|p-rchild=pre)(/visitthiselementandthenpopitcoutdata;s.pop();pre=p;p=NULL;)else(p=p-rchild;)/endofwhile(p|st.size()!=0)4、求二叉樹的高

13、度templateintBiTree:depth()(returndepth(rootptr);templateintBiTree:depth(BiNode*root)(intrdep,ldep;if(root=NULL)return0;else(ldep=depth(root-lchild);rdep=depth(root-rchild);return(rdepldep?rdep:ldep)+1;5 5、求二叉樹每一層的結點數templatevoidBiTree:LevelNum()(LevelNum(rootptr);templatevoidBiTree:LevelNum(BiNode*r

14、oot)(queueBiNode*q;intfront,rear,first,last,level;front=rear=first=0;last=level=1;if(root)(q.push(root);rear+;while(frontlchild)(q.push(root-lchild);rear+;if(root-rchild)(q.push(root-rchild);rear+;if(front=last)(cout第level層有last-first個結點 level+;last=rear;first=front;6 6、求兩節點最近共同祖先templateTBiTree:lea

15、stCommanAncestor(Tn1,Tn2)returnleastCommanAncestor(rootptr,n1,n2);templateTBiTree:leastCommanAncestor(BiNode*root,Tn1,Tn2)if(root=NULL|root-data=n1|root-data=n2)return-1;rchild!=NULL)&(root-rchild-data=n1|root-rchild-data=n2)returnroot-data;if(root-lchild!=NULL)&(root-lchild-data=n1|root-lch

16、ild-data=n2)returnroot-data;if(root-datan1&root-datadata;if(root-datan1&root-datan2)returnleastCommanAncestor(root-lchild,n1,n2);if(root-datadatarchild,n1,n2);6、算法流程圖六、程序測試與實現1、函數之間的調用關系2、主程序voidmain()(BiTreeTree(1);while(1)couttt 歡迎使用本系統!endl;couttt#endl;couttt#endl;couttt#1-創建一顆二叉樹并顯示#endl

17、;couttt#2-遍歷二叉樹#endl;couttt#3-查詢二叉樹的深度和結點數#endl;couttt#4-查詢每層結點數#endl;couttt#5-查找兩節點評 DQ 的最近共同祖先#endl;couttt#6-退出#endl;couttt#endl;couttt#endl;coutx;switch(x)case1:cout請輸入二叉樹的前序遍歷:endl;cout(以#作為分支結尾,例如:AB#C#)endl;Tree.creat();coutTree;coutendl;break;case2:coutendl;cout前序遍歷為:;Tree.PreOrder();coutendl

18、;cout中序遍歷為:;Tree.inorder();coutendl;cout后序遍歷為:;Tree.PostOrder();coutendl;cout層序遍歷為:;Tree.levelorder();coutendl;coutendl;break;case3:cout樹的深度為:Tree.depth()endl;cout樹的結點數:Tree.count()endl;coutendl;break;case4:Tree.LevelNum();break;case5:charch1,ch2;coutch1;coutch2;coutch1和ch2的最近共同祖先是Tree.leastCommanAn

19、cestor(ch1,ch2)endl;break;case6:return;break;default:cout請輸入正確的選擇!endl;break;3、測試數據AB#CD#E#FGH#K#4、測試結果歡迎使用本系統I工一創健二顆二叉樹并顯示#2r通歷二叉科 tt3魯詢二黑詞的深度和結點數#4查詢每層結點致#5查找兩 T 點F和Q的最近共同祖先#6退出#正入你的選擇.1二叉樹的前序遍歷:區+公土#主叱例如士ABNttCttNJ歡迎使用本系統!ttttIttttttttttfttttttHttttWtttttt#Itittttt1創建一顆二叉樹并顯示2遍歷一艮呀m查詢二叉時的深度和結點數4查

20、詢每層結點教tt一查找兩節點P和。的最近共同祖先#”一退出ttuttttflnttttttnitttiittUftNNUftitNtttttttinuttiiflUttHtiuttttMtttt2-nut為為為為為為歷歷為為歷歷歷歷歷歷遍遍遍遍遍遍遍遍ABCDEFGHKBDCAEHGKFDCBHKGFEAnBRCFDGHK歡迎使用本系統!I1一創建一顆二叉樹并顯示2遍歷二X村m警詢二復國的尊度和結點數4一查詢每層菇點皺5善戰商節點P而Q的最近共同祖先6退出ftntttfffttttttnunnttftttttttnnttnnnnnunHttttnnttnnttffntttt請施入他的選擇,3和的饞度為:5樹的碓點數;?歡迎使用本系統!ttNMtttttlttttnUttNnttttntttttlttttMttttNttttNtltttttlUttNttttNttttIttti一創建一顆二叉樹并顯示2一遍歷二叉樹5查找兩節點P和Q的最近共同祖先6痕出ntt請輸入你的選擇:量工層有1個結點一之小結點塞2層有急層有;2個結點篁4層有2個結點第5層有2個結點ttitntt* *- -m-lm-l亳亳噫祖區蕾噫祖區蕾丘審數數丘審數數近近你你

溫馨提示

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

評論

0/150

提交評論