1、數據結構課程設計報告設計題目： 二叉樹的遍歷 姓 名： 陳 雷 學 號： 專 業(yè)： 計算機科學與技術 院 系： 計算機科學與技術 班 級： 1002 指導教師： 吳克力 2012年 3 月 1日 摘要：本文主要說明如何實現二叉樹的遍歷。此次二叉樹的遍歷基于二叉樹的二叉鏈表存儲結構。遍歷方式包括：前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷。其中前序遍歷和后續(xù)遍歷采用非遞歸算法實現。編程環(huán)境為VC+，除了遍歷操作外，還增加了求二叉樹的深度，總結點數，每層結點數，以及最近共同祖先（LCA）問題的算法。關鍵字：二叉樹 遍歷 非遞歸 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三、概要設計41創(chuàng)建二叉樹42二叉樹的非遞歸前序遍歷示意圖43二叉樹的后序非遞歸遍歷示意圖5四、數據結構設計51二叉樹結點數據類型定義為：52二叉樹數據類型定義為：5五、算法設計61、創(chuàng)建二叉樹62、非遞歸前序遍歷73、非遞歸后序遍歷74、求二叉樹的高度85、求二叉樹每一層的結點數96、求兩節(jié)點最近共同祖先96、算法流程圖10六、程序測試與實現111、函數之間的調用關系112、主程序113、測試數據134、測試結果13七、調試分析14八、遇到的問題及解決辦法15九、心得體會15十、參考文獻15一、問題描述問題描述：創(chuàng)建二叉樹并遍歷基本要求：1、 分別

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

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

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

8、祖先protected:/以下函數供上面函數調用/對應相同功能void creat(BiNode * &root);/創(chuàng)建void release(BiNode* &root);/刪除BiNode * Build(T ary,int num,T none,int idx);/用數組創(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);/計算結點數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;五、算法設計1、創(chuàng)建二叉樹/實現外部遞歸調用void BiTree:creat()creat(rootptr);/類體內遞歸創(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表示最近一次訪問的結點 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、求二叉樹每一層的結點

14、數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個結點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、算法流程圖程序初始化用戶交互用戶輸入選擇求共同祖先求每層結點數求深度遍歷二叉樹創(chuàng)建二叉樹結束處理并輸出結果六、程序測試與實現1、函數之間的調用關系main()每層結點數求LCA求節(jié)點數深度遍歷創(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-查詢二叉樹的深度和結點數 # endl;couttt# 4-查詢每層結點數 # endl;couttt# 5-查找兩節(jié)點P和Q的最近共同祖先 # endl;couttt# 6-退出 # endl;couttt# # endl;couttt# endl;coutx;switch(x)case 1:cout請輸入二叉樹的前序遍歷：endl;cout（以#作為分支結尾，例如：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樹的結點數：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