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亳亳噫祖區蕾噫祖區蕾丘審數數丘審數數近近你你