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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告設(shè)計題目： 二叉樹的遍歷 姓 名： 陳 雷 學(xué) 號： 專 業(yè)： 計算機(jī)科學(xué)與技術(shù) 院 系： 計算機(jī)科學(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+ LCA Abstract: This paper mainly de

2、scribes how to implement binary tree traversal. The binary tree traversal is based on binary tree binary storage structure. Traversal method includes: preorder traversal,inorder traversal, postorder traversal, levelorder traversal. The former preorder traversal and postorder use of non - recursive a

3、lgorithm. Programming environment is VC + +, in addition to traversal operation, also increased for solving the binary tree depth 、 summary points and each layer of nodes, as well as the most recent common ancestor ( LCA ) algorithm.Keywords: binary tree traversal non-recursive C+ LCA目 錄一、問題描述4問題描述：

4、創(chuàng)建二叉樹并遍歷4基本要求：4二、需求分析4三、概要設(shè)計41創(chuàng)建二叉樹42二叉樹的非遞歸前序遍歷示意圖43二叉樹的后序非遞歸遍歷示意圖5四、數(shù)據(jù)結(jié)構(gòu)設(shè)計51二叉樹結(jié)點數(shù)據(jù)類型定義為：52二叉樹數(shù)據(jù)類型定義為：5五、算法設(shè)計61、創(chuàng)建二叉樹62、非遞歸前序遍歷73、非遞歸后序遍歷74、求二叉樹的高度85、求二叉樹每一層的結(jié)點數(shù)96、求兩節(jié)點最近共同祖先96、算法流程圖10六、程序測試與實現(xiàn)111、函數(shù)之間的調(diào)用關(guān)系112、主程序113、測試數(shù)據(jù)134、測試結(jié)果13七、調(diào)試分析14八、遇到的問題及解決辦法15九、心得體會15十、參考文獻(xiàn)15一、問題描述問題描述：創(chuàng)建二叉樹并遍歷基本要求：1、 分別

5、運用非遞歸的方式完成對二叉樹的先序和后序遍歷2、 輸出二叉樹的高度3、 輸出每一層的結(jié)點數(shù)4、 查找結(jié)點P 和結(jié)點Q的最近共同祖先二、需求分析1 本程序的功能包括二叉樹的建立，二叉樹的遞歸遍歷，二叉樹的非遞歸遍歷，查詢二叉樹的深度，查詢每層的結(jié)點數(shù)，查找兩個結(jié)點的最近共同祖先，二叉樹的打印。2 程序運行后顯現(xiàn)提示信息，等候用戶輸入06以進(jìn)入相應(yīng)的操作功能。3 用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\行結(jié)果。4 測試數(shù)據(jù)應(yīng)為字符型數(shù)據(jù)。三、概要設(shè)計1創(chuàng)建二叉樹輸入數(shù)據(jù)不低于15個，用遞歸方法建立二叉樹。2二叉樹的非遞歸前序遍歷示意圖圖3.2二叉樹前序遍歷示意圖3二叉樹的后序非遞歸遍歷示意圖圖3.4二叉樹后

6、序遍歷示意圖四、數(shù)據(jù)結(jié)構(gòu)設(shè)計1 二叉樹結(jié)點數(shù)據(jù)類型定義為：template structBiNodeBiNode *rchild,*lchild;/指向左右孩子的指針T data; /結(jié)點數(shù)據(jù)信息;2 二叉樹數(shù)據(jù)類型定義為：template class BiTreetemplate friend ostream & operator (ostream &os ,BiTree &bt);public:BiTree();/無參構(gòu)造函數(shù)BiTree(int m);/有參空構(gòu)造函數(shù)BiTree(T ary,int num,T none);/有參構(gòu)造函數(shù)BiTree();/析構(gòu)函數(shù)void preord

7、er();/遞歸前序遍歷void inorder();/遞歸中序遍歷void postorder();/遞歸后續(xù)遍歷void levelorder();/層序遍歷int count();/計算二叉樹的結(jié)點數(shù)int depth();/計算二叉樹的深度void display(ostream &os);/打印二叉樹，有層次void LevelNum();/計算每一層結(jié)點數(shù)void PreOrder();/非遞歸前序遍歷void PostOrder();/非遞歸后序遍歷void creat();/創(chuàng)建二叉樹T leastCommanAncestor(T va, T vb);/求樹中任意兩結(jié)點最近共同

8、祖先protected:/以下函數(shù)供上面函數(shù)調(diào)用/對應(yīng)相同功能void creat(BiNode * &root);/創(chuàng)建void release(BiNode* &root);/刪除BiNode * Build(T ary,int num,T none,int idx);/用數(shù)組創(chuàng)建二叉樹void PreOrder(BiNode* root);/前序遍歷void PostOrder(BiNode* root);/后續(xù)遍歷void LevelNum(BiNode* root);/層序遍歷void preorder(BiNode* root);/遞歸前序遍歷void inorder(BiNode

9、* root);/遞歸中序遍歷void postorder(BiNode* root);/遞歸后續(xù)遍歷void levelorder(BiNode*root);/層序遍歷int count(BiNode* root);/計算結(jié)點數(shù)int depth(BiNode* root);/計算深度void display(ostream& os,BiNode* root,int dep);/打印static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode *&result, BiNode* parrent);/求最近共同祖先privat

10、e:BiNode *rootptr;五、算法設(shè)計1、創(chuàng)建二叉樹/實現(xiàn)外部遞歸調(diào)用void BiTree:creat()creat(rootptr);/類體內(nèi)遞歸創(chuàng)建二叉樹template void BiTree:creat(BiNode * & root)T item;cinitem;if(item=#) root=NULL;elseroot=new BiNode;root-data=item;creat(root-lchild);creat(root-rchild);2、非遞歸前序遍歷template void BiTree:PreOrder()PreOrder(rootptr);templ

11、ate void BiTree:PreOrder(BiNode* root)stack BiNode * 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、非遞歸后序遍歷template void BiTree:PostOrder()PostOrder(rootptr);template void BiTree:PostOrder(BiNode *root) stackBiNode*

12、 s;/定義棧，節(jié)點類型為TreeNode BiNode *p = root; BiNode *pre = NULL;/pre表示最近一次訪問的結(jié)點 while(p|!s.empty() /沿著左孩子方向走到最左下。 while(p) s.push(p); p = p-lchild; /get the top element of the stack p = s.top(); /如果p沒有右孩子或者其右孩子剛剛被訪問過 if(p-rchild= NULL| p-rchild = pre) /visit this element and then pop it cout data; s.pop(

13、); pre = p; p = NULL; else p = p-rchild; /end of while(p | st.size()!=0)4、求二叉樹的高度template int BiTree:depth()return depth(rootptr);template int BiTree:depth(BiNode *root)int rdep,ldep;if(root=NULL)return 0;else ldep=depth(root-lchild);rdep=depth(root-rchild);return (rdepldep?rdep:ldep)+1;5、求二叉樹每一層的結(jié)點

14、數(shù)template void BiTree:LevelNum()LevelNum(rootptr);template void BiTree:LevelNum(BiNode * root)queue BiNode * q;int front,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

15、)cout第level層有l(wèi)ast-first個結(jié)點endl;level+;last=rear;first=front;6、求兩節(jié)點最近共同祖先template T BiTree:leastCommanAncestor(T n1, T n2)return leastCommanAncestor(rootptr,n1,n2);template T BiTree:leastCommanAncestor(BiNode * root, T n1, T n2) if(root = NULL | root-data = n1 | root-data = n2) return -1; if(root-rch

16、ild!= NULL) & (root-rchild-data = n1 | root-rchild-data = n2) return root-data; if(root-lchild != NULL) & (root-lchild-data = n1 | root-lchild-data = n2) return root-data; if(root-data n1 & root-data data; if(root-data n1 & root-data n2) return leastCommanAncestor(root-lchild, n1, n2); if(root-data

17、data rchild, n1, n2); 6、算法流程圖程序初始化用戶交互用戶輸入選擇求共同祖先求每層結(jié)點數(shù)求深度遍歷二叉樹創(chuàng)建二叉樹結(jié)束處理并輸出結(jié)果六、程序測試與實現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系main()每層結(jié)點數(shù)求LCA求節(jié)點數(shù)深度遍歷創(chuàng)建LCA()Levelnum()Creat()Count()Depth()Inorder()Postorder()Preorder()2、主程序void main()BiTree Tree(1);while(1)couttt 歡迎使用本系統(tǒng)！ endl;couttt# endl;couttt# # endl;couttt# 1-創(chuàng)建一顆二叉樹并顯示 # e

18、ndl;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# endl;coutx;switch(x)case 1:cout請輸入二叉樹的前序遍歷：endl;cout（以#作為分支結(jié)尾，例如：A B # # C # #）endl;Tree.creat();coutTree;coutendl; break;case 2:coutendl;cout

19、前序遍歷為：;Tree.PreOrder();coutendl;cout中序遍歷為：;Tree.inorder();coutendl;cout后序遍歷為：;Tree.PostOrder();coutendl;cout層序遍歷為：;Tree.levelorder();coutendl;coutendl; break;case 3: cout樹的深度為：Tree.depth()endl;cout樹的結(jié)點數(shù)：Tree.count()endl;coutendl;break;case 4:Tree.LevelNum(); break;case 5:char ch1,ch2;coutch1;coutch2;coutch1和ch2的最近共同祖先是Tree.leastCommanAncestor(ch1, ch2)endl; brea