二叉樹的遍歷課程設(shè)計(C++)含源代碼

1、 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題二叉樹的遍歷名學(xué)號專業(yè)院系班級計算機科學(xué)與技術(shù)計算機科學(xué)與技術(shù)1002指導(dǎo)教師2012年3月1日摘要：本文主要說明如何實現(xiàn)二叉樹的遍歷。此次二叉樹的遍歷基于二叉樹的二叉鏈表存儲結(jié)構(gòu)。遍歷方式包括：前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷。其中前序遍歷和后續(xù)遍歷采用非遞歸算法實現(xiàn)。編程環(huán)境為VC+，除了遍歷操作外，還增加了求二叉樹的深度，總結(jié)點數(shù)，每層結(jié)點數(shù)，以及最近共同祖先（LCA）問題的算法。關(guān)鍵字：二叉樹遍歷非遞歸C+LCAAbstract:Thispapermainlydescribeshowtoimplementbinarytreetraversal.Theb

2、inarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC+,inadditiontotraversaloperation,alsoincreasedfors

3、olvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC+LCATOC o 1-5 h z HYPERLINK l bookmark8 一、問題描述4問題描述：創(chuàng)建二叉樹并遍歷4基本要求：4 HYPERLINK l bookmark10 二、需求分析4三、概要設(shè)計4 HYPERLINK l bookmark12 1創(chuàng)建二叉樹4 HYPERLINK l b

4、ookmark14 2二叉樹的非遞歸前序遍歷示意圖43二叉樹的后序非遞歸遍歷示意圖5數(shù)據(jù)結(jié)構(gòu)設(shè)計 HYPERLINK l bookmark18 1二叉樹結(jié)點數(shù)據(jù)類型定義為：5 HYPERLINK l bookmark20 2二叉樹數(shù)據(jù)類型定義為：5 HYPERLINK l bookmark22 五、算法設(shè)計61、創(chuàng)建二叉樹6 HYPERLINK l bookmark24 2、非遞歸前序遍歷7 HYPERLINK l bookmark26 3、非遞歸后序遍歷7 HYPERLINK l bookmark28 4、求二叉樹的高度8 HYPERLINK l bookmark30 5、求二叉樹每一層的結(jié)

5、點數(shù)9 HYPERLINK l bookmark32 6、求兩節(jié)點最近共同祖先9 HYPERLINK l bookmark34 6、算法流程圖1011六、程序測試與實現(xiàn) HYPERLINK l bookmark38 1、函數(shù)之間的調(diào)用關(guān)系11 HYPERLINK l bookmark40 2、主程序11 HYPERLINK l bookmark42 3、測試數(shù)據(jù)13 HYPERLINK l bookmark44 4、測試結(jié)果13 HYPERLINK l bookmark48 七、調(diào)試分析14 HYPERLINK l bookmark50 八、遇到的問題及解決辦法15 HYPERLINK l b

6、ookmark52 九、心得體會15 HYPERLINK l bookmark54 十、參考文獻15一、問題描述問題描述：創(chuàng)建二叉樹并遍歷基本要求：1、分別運用非遞歸的方式完成對二叉樹的先序和后序遍歷2、輸出二叉樹的高度3、輸出每一層的結(jié)點數(shù)4、查找結(jié)點P和結(jié)點Q的最近共同祖先二、需求分析本程序的功能包括二叉樹的建立，二叉樹的遞歸遍歷，二叉樹的非遞歸遍歷，查詢二叉樹的深度，查詢每層的結(jié)點數(shù)，查找兩個結(jié)點的最近共同祖先，二叉樹的打印。程序運行后顯現(xiàn)提示信息，等候用戶輸入06以進入相應(yīng)的操作功能。用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\行結(jié)果。測試數(shù)據(jù)應(yīng)為字符型數(shù)據(jù)。概要設(shè)計1創(chuàng)建二叉樹輸入數(shù)據(jù)不低于15個

7、，用遞歸方法建立二叉樹。2二叉樹的非遞歸前序遍歷示意圖圖3.2二叉樹前序遍歷示意圖3二叉樹的后序非遞歸遍歷示意圖圖3.4二叉樹后序遍歷示意圖四、數(shù)據(jù)結(jié)構(gòu)設(shè)計二叉樹結(jié)點數(shù)據(jù)類型定義為：templatetypenameTstructBiNodeBiNodeT*rchild,*lchild;/指向左右孩子的指針Tdata;/結(jié)點數(shù)據(jù)信息;二叉樹數(shù)據(jù)類型定義為：templatetypenameTclassBiTreetemplatetypenameTfriendostream&operator(ostream&os,BiTreeT&bt);public:BiTreeO;/無參構(gòu)造函數(shù)BiTree(in

8、tm);/有參空構(gòu)造函數(shù)BiTree(Tary,intnum,Tnone);/有參構(gòu)造函數(shù)BiTree();/析構(gòu)函數(shù)voidpreorder();/遞歸前序遍歷voidinorder();/遞歸中序遍歷voidpostorder();/遞歸后續(xù)遍歷voidlevelorder();/層序遍歷intcount();/計算二叉樹的結(jié)點數(shù)intdepth();/計算二叉樹的深度voiddisplay(ostream&os);/打印二叉樹，有層次voidLevelNum();/計算每一層結(jié)點數(shù)voidPreOrder();/非遞歸前序遍歷voidPostOrder();/非遞歸后序遍歷voidcre

9、at();/創(chuàng)建二叉樹TleastCommanAncestor(Tva,Tvb);/求樹中任意兩結(jié)點最近共同祖先protected:/以下函數(shù)供上面函數(shù)調(diào)用/對應(yīng)相同功能voidcreat(BiNode*&root);/創(chuàng)建voidrelease(BiNode*&root);/刪除BiNode*Build(Tary,intnum,Tnone,intidx);/用數(shù)組創(chuàng)建二叉樹voidPreOrder(BiNodeT*root);/前序遍歷voidPostOrder(BiNodeT*root);/后續(xù)遍歷voidLevelNum(BiNodeT*root);/層序遍歷voidpreorder(B

10、iNodeT*root);/遞歸前序遍歷voidinorder(BiNodeT*root);/遞歸中序遍歷voidpostorder(BiNodeT*root);/遞歸后續(xù)遍歷voidlevelorder(BiNodeT*root);/層序遍歷intcount(BiNodeT*root);/計算結(jié)點數(shù)intdepth(BiNodeT*root);/計算深度voiddisplay(ostream&os,BiNodeT*root,intdep);/打印staticboolleastCommanAncestor(BiNodeT*root,Tva,Tvb,BiNodeT*&result,BiNodeT

11、*parrent);/求最近共同祖先private:BiNodeT*rootptr;五、算法設(shè)計1、創(chuàng)建二叉樹/實現(xiàn)外部遞歸調(diào)用voidBiTreeT:creat()creat(rootptr);/類體內(nèi)遞歸創(chuàng)建二叉樹templatetypenameTvoidBiTreeT:creat(BiNodeT*&root)Titem;cinitem;if(item=#)root=NULL;elseroot=newBiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非遞歸前序遍歷templatevoidBiTree:PreOrder

12、()PreOrder(rootptr);templatevoidBiTree:PreOrder(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

13、)stackBiNodeT*s;/定義棧，節(jié)點類型為TreeNodeBiNode*p=root;BiNode*pre=NULL;/pre表示最近一次訪問的結(jié)點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;elsep=p-rchil

14、d;/endofwhile(p|st.size()!=0)4、求二叉樹的高度templateintBiTree:depth()returndepth(rootptr);templateintBiTree:depth(BiNode*root)intrdep,ldep;if(root=NULL)return0;elseldep=depth(root-lchild);rdep=depth(root-rchild);return(rdepldep?rdep:ldep)+1;5、求二叉樹每一層的結(jié)點數(shù)templatevoidBiTree:LevelNum()LevelNum(rootptr);templ

15、atevoidBiTree:LevelNum(BiNode*root)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層有l(wèi)ast-first個結(jié)點endl;level+;last=rear;first=front;6、求

16、兩節(jié)點最近共同祖先templateTBiTree:leastCommanAncestor(Tn1,Tn2)returnleastCommanAncestor(rootptr,n1,n2);templateTBiTree:leastCommanAncestor(BiNode*root,Tn1,Tn2)if(root=NULL|root-data=n1|root-data=n2)return-1;if(root-rchild!=NULL)&(root-rchild-data=n1|root-rchild-data=n2)returnroot-data;if(root-lchild!=NULL)&(

17、root-lchild-data=n1|root-lchild-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、算法流程圖六、程序測試與實現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系2、主程序voidmain()BiTreeTree(1);while(1)couttt歡迎使用本系統(tǒng)！endl;couttt#endl;couttt#endl;couttt

18、#1-創(chuàng)建一顆二叉樹并顯示#endl;couttt#2-遍歷二叉樹#endl;couttt#3-查詢二叉樹的深度和結(jié)點數(shù)#endl;couttt#4-查詢每層結(jié)點數(shù)#endl;couttt#5-查找兩節(jié)點P和Q的最近共同祖先#endl;couttt#6-退出#endl;couttt#endl;couttt#x；switch(x)case1:cout請輸入二叉樹的前序遍歷：endl;cout(以#作為分支結(jié)尾，例如：AB#C#)endl;Tree.creat();coutTree;coutendl;break;case2:coutendl;cout前序遍歷為：；Tree.PreOrder();c

19、outendl;cout中序遍歷為：；Tree.inorder();coutendl;cout后序遍歷為：；Tree.PostOrder();coutendl；cout層序遍歷為：；Tree.levelorder()；coutendl；coutendl；break；case3:cout樹的深度為：Treedepth()endl;coutch1；cout請輸入Q數(shù)據(jù)信息：；cinch2；coutchl和ch2的最近共同祖先是Tree.leastCommanAncestor(ch1,ch2)endl；break；case6:return；break；default:cout請輸入正確的選擇endl

20、；break；3、測試數(shù)據(jù)ab#cd#e#fgh#k#4、測試結(jié)果歡迎使用本系統(tǒng)！TOC o 1-5 h z#fl-創(chuàng)建一顓二叉樹開顯示A-遍歷二叉秋查詞二叉吠的滾展和結(jié)氐數(shù)4_杳荷每豆古占舉了查品蕎節(jié)點P粘的最近共辰祖先右-退曲H#fl請新入你的選擇：1詭輸入二叉惻貳前底遍歷：了就排作為分支結(jié)尾，例如：AB#C#)FK*G歡迎使用本系統(tǒng)！TOC o 1-5 h z丄-劃建一顆二殳樹并顯示#-區(qū)歷二叉內(nèi)#3查詢二叉討的探度和結(jié)點數(shù)tt4-車詢魚尼蛤點藪U弓-查找兩節(jié)點p和Q的最近共司祖先#-退出B為為詢?yōu)楸楸樵嵄樾蚯爸泻髮诱堓斎肽愕倪x擇：2ABCDEFGHKBDCAEHGKFDCBHKGFEAABECFEGHK歡獨使用本系統(tǒng)！nnnnnnnnnnnttnnffnnnffnnttnnniinnttnnnnnnttnffnnTOC o 1-5 h z創(chuàng)建顆二叉樹并顯示#A-遍歷二叉桝#2查詢二貝詞的渓度和結(jié)點數(shù)it-查詢笹層結(jié)點數(shù)_#吐-杳找兩節(jié)點P和。的最訴共同祖托#石-退由#擇59遠；的為數(shù)你度點入塞制的請窗歡迎使用本系統(tǒng)II-創(chuàng)建題二叉樹并顯示-；匾歷二叉眉查詢-馬擁的探度和結(jié)點數(shù)4一一杳i句事貝2吉占*&蠶屋聶宰責(zé)需;的最近共同