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

1、實(shí)用文檔南京理 工大學(xué)課程設(shè)計報告者作相蒙蒙學(xué) 號：054913221001教學(xué)占八、:蘇州市職業(yè)大學(xué)專業(yè):機(jī)電一體化題目:二叉樹的遍歷指導(dǎo)者：尚鮮蓮評閱者：2014 年4 月南京理工大學(xué)課程設(shè)計報告評語綜合成績：指導(dǎo)者評語:指導(dǎo)者（簽字）:年 月 日課程設(shè)計報告摘要摘要：本文主要說明如何實(shí)現(xiàn)二叉樹的遍歷。此次二叉樹的遍歷基于二叉樹的二 叉鏈表存儲結(jié)構(gòu)。遍歷方式包括：前序遍歷，中序遍歷，后續(xù)遍歷，層序遍歷。 其中前序遍歷和后續(xù)遍歷采用非遞歸算法實(shí)現(xiàn)。編程環(huán)境為VC+除了遍歷操作外，還增加了求二叉樹的深度，總結(jié)點(diǎn)數(shù)，每層結(jié)點(diǎn)數(shù)，以及最近共同祖先（LCA 問題的算法。關(guān)鍵詞：二叉樹遍歷二叉樹遍歷目

2、錄1問題描述 51.1問題描述：創(chuàng)建二叉樹并遍歷 52、需求分析53、概要設(shè)計53.1 .創(chuàng)建二叉樹 53.2二叉樹的非遞歸前序遍歷示意圖 53.3二叉樹的后序非遞歸遍歷示意圖 64、數(shù)據(jù)結(jié)構(gòu)設(shè)計64.1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義 64.2二叉樹數(shù)據(jù)類型定義 75、算法設(shè)計85.1創(chuàng)建二叉樹85.2非遞歸前序遍歷85.3非遞歸后序遍歷95.4求二叉樹的高度105.5求二叉樹每一層的結(jié)點(diǎn)數(shù) 105.6求兩節(jié)點(diǎn)最近共同祖先 115.7算法流程圖126、程序測試與調(diào)試126.1函數(shù)之間的調(diào)用關(guān)系 126.2主程序 136.3測試數(shù)據(jù) 146.4測試結(jié)果157、調(diào)試分析17&遇到的問題及解決辦法

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

4、2二叉樹的非遞歸前序遍歷示意圖圖3.2二叉樹前序遍歷示意圖3.3二叉樹的后序非遞歸遍歷示意圖4、數(shù)據(jù)結(jié)構(gòu)設(shè)計4.1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義為:template < type name T> struct BiNodeBiNode<T> *rchild,*lchild;指向左右孩子的指針T data;/結(jié)點(diǎn)數(shù)據(jù)信息；4.2二叉樹數(shù)據(jù)類型定義為：template < type name T>class BiTreetemplate <type name T>friend ostream & operator <<(ostream &

5、amp;os ,BiTree<T> &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 preorder(); /遞歸前序遍歷void inorder();/遞歸中序遍歷void postorder(); /遞歸后續(xù)遍歷void levelorder(); / 層序遍歷int count();II計算二叉樹的結(jié)點(diǎn)數(shù)int depth();II計算二叉樹的深度void display(ostream &am

6、p;os); II 打印二叉樹，有層次void LevelNum(); II計算每一層結(jié)點(diǎn)數(shù)void PreOrder(); II非遞歸前序遍歷void PostOrder(); II非遞歸后序遍歷void creat(); II 創(chuàng)建二叉樹T leastCommanAncestor(T va, T vb);II求樹中任意兩結(jié)點(diǎn)最近共同祖先protected :II以下函數(shù)供上面函數(shù)調(diào)用II對應(yīng)相同功能void creat(BiNode <T>* &root);II 創(chuàng)建void release(BiNode<T>* &root);II 刪除BiNode

7、<T> * Build(T ary, int num,T none, int idx); II 用數(shù)組創(chuàng)建二叉樹 voidPreOrder(BiNode<T>* root);II前序遍歷void PostOrder(BiNode<T>* root); II 后續(xù)遍歷 voidLevelNum(BiNode<T>* root);II層序遍歷voidpreorder(BiNode<T>* root);II遞歸前序遍歷void inorder(BiNode<T>* root); II 遞歸中序遍歷 void postorder(

8、BiNode<T>* root);II 遞歸后續(xù)遍歷void levelorder(BiNode<T>*root);II 層序遍歷int count(BiNode<T>* root);II 計算結(jié)點(diǎn)數(shù)int depth(BiNode<T>* root);II 計算深度void display(ostream& os,BiNode<T>* root,int dep); II 打印static bool leastCommanAncestor(BiNode<T> *root, T va, T vb, BiNode<

9、;T>*&result, BiNode<T>* parrent); / 求最近共同祖先 private :BiNode<T> *rootptr;5、算法設(shè)計5.1創(chuàng)建二叉樹/實(shí)現(xiàn)外部遞歸調(diào)用void BiTree<T>:creat()creat(rootptr);/類體內(nèi)遞歸創(chuàng)建二叉樹template < typename T>void BiTree<T>:creat(BiNode<T> * & root) T item;cin>>item;if (item= # ) root=NULL;

10、elseroot= new BiNode<T> root->data=item; creat(root->lchild); creat(root->rchild);5.2非遞歸前序遍歷template < typename T>void BiTree<T>:PreOrder()PreOrder(rootptr);template < typename T>void BiTree<T>:PreOrder(BiNode<T>* root) stack <BiNode<T> *> s;w

11、hile (root!=NULL|!s.empty()while (root)cout<vroot->data;s.push(root); root=root->lchild;if (!s.empty()root=s.top();s.pop();root=root->rchild;5.3非遞歸后序遍歷template < typename T>void BiTree<T>:PostOrder()PostOrder(rootptr);template < typename T>void BiTree<T>:PostOrder

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

13、= NULL| p->rchild = pre)/visit this element and then pop itcout <<p->data;s.pop();pre = p;p = NULL;elsep = p->rchild; /end of while(p | st.size()!=0)5.4求二叉樹的高度template < typename T>int BiTree<T>:depth()return depth(rootptr);template < typename T>int BiTree<T>:d

14、epth(BiNode<T> *root)int rdep,ldep;if (root=NULL)return 0;elseldep=depth(root->lchild); rdep=depth(root->rchild);return (rdep>ldep?rdep:ldep)+1;5.5求二叉樹每一層的結(jié)點(diǎn)數(shù)template < typename T>void BiTree<T>:LevelNum()LevelNum(rootptr);template < typename T>void BiTree<T>:L

15、evelNum(BiNode<T> * root)queue <BiNode<T> *> q;int front,rear,first,last,level;front=rear=first=0;last=level=1;if (root)q.push(root);rear+;while (frontvrear)root=q.front();q.pop()；front+;if (root->lchild)q.push(root->lchild);rear+;if (root->rchild)q.push(root->rchild);r

16、ear+;if (front=last)cout<< "第"vvlevelvv "層有"wlast-firstw"個結(jié)點(diǎn)"<<endl;level+;last=rear;first=front;5.6求兩節(jié)點(diǎn)最近共同祖先template v typename T>T BiTreevT>:leastCommanAncestor(T n1, T n2)return leastCommanAncestor(rootptr,n1,n2);template v typename T>T BiTreevT

17、>:leastCommanAncestor(BiNodevT> * root, T n1, T n2) if (root = NULL | root->data = n1 | root->data = n2) return -1;if (root->rchild!= NULL) &&(root->rchild->data = n1 | root->rchild->data = n2) return root->data;if (root->lchild != NULL) &&(root->l

18、child->data = n1 | root->lchild->data = n2) return root->data;if (root->data > n1 && root->data < n2)return root->data;if (root->data > n1 && root->data > n2)return leastCommanAncestor(root->lchild, n1, n2); if (root->data < n1 &&am

19、p; root->data < n2)return leastCommanAncestor(root->rchild, n1, n2);5.7算法流程圖6、程序測試與實(shí)現(xiàn)6.1函數(shù)之間的調(diào)用關(guān)系創(chuàng)建遍歷求節(jié)點(diǎn)數(shù)深度每層結(jié)點(diǎn)數(shù)求LCACreat()Depth()LCA()Preorder()Ino rder()LJPostorder()LJ6.2主程序void main()BiTreev char > Tree(1);while (1)coutvv "tt歡迎使用本系統(tǒng)！vvendl;coutvv "tt# " vvendl;coutvv &

20、quot;tt#vvendl;coutvv "tt#1-創(chuàng)建一顆二叉樹并顯示vvendl;coutvv "tt#2-遍歷二叉樹vvendl;coutvv "tt#3-查詢二叉樹的深度和結(jié)點(diǎn)數(shù)vvendl;coutvv "tt#4-查詢每層結(jié)點(diǎn)數(shù)vvendl;coutvv "tt#5-查找兩節(jié)點(diǎn)P和Q的最近共同祖先vvendl;coutvv "tt#6-退出vvendl;vvendl;vvendl;coutvv "tt# coutvv "tt# " coutvv "請輸入你的選擇: int x;c

21、in»x;switch (x)case 1:coutvv "請輸入二叉樹的前序遍歷："vvendl;coutvv "(以#作為分支結(jié)尾，例如：A B # # C # # )"vvendl;Tree.creat();coutvvTree;coutvvendl; break ;case 2:coutvvendl;coutvv "前序遍歷為：”；Tree.PreOrder();coutvvendl;cout< v"中序遍歷為："；Tree.inorder();coutvvendl;coutvv "后序遍歷

22、為：”；Tree.PostOrder();coutvvendl;coutvv "層序遍歷為：”；Tree .l evelorder();coutvvendl;coutvvendl; break ;case 3: coutvv "樹的深度為："vvTree.depth()vvendl; coutvv "樹的結(jié)點(diǎn)數(shù)："vvTree.count()vvendl; coutvvendl; break;case 4:Tree.LevelNum(); break ;case 5:char ch1,ch2;coutvv "請輸入P數(shù)據(jù)信息：&quo

23、t;；cin»ch1;coutvv "請輸入C數(shù)據(jù)信息：”；cin»ch2;"vvTree .l eastCommanAncestor(ch1,coutvvchlvv"和"vvch2vv"的最近共同祖先是ch2)vvendl; break ;case 6: return ; break ;default : coutvv "請輸入正確的選擇！ ！ "vvendl; break ; 6.3測試數(shù)據(jù)AB#CD#E#FGH#K#6.4測試結(jié)果歡迎使用本系統(tǒng)I !1- -創(chuàng)建一顆二叉樹并顯示2- m叉兩3一-查i

24、i每層緒點(diǎn)數(shù)ft弓-查找兩芳點(diǎn)p和Q的最近共同祖先.#的深度劑結(jié)點(diǎn)數(shù)入你的選怡1入二叉樹的前序遍歷：| （以林屜坷夯支結(jié)周 Mn： ABoc#*）AEttCDttttttEttFGHttttKtttttt*-F歡迎使用本系統(tǒng)I !ft1 一創(chuàng)建一顆二叉樹并顯示#«2遍歷二支樹# 3-承二叉硯的探度和結(jié)點(diǎn)數(shù)«tt百一查詢每層給點(diǎn)藪# 5-查找兩節(jié)點(diǎn)P和啲最近共同祖先#tt退岀ttuitnNtttttttinitttNnuttHMttAttMnttttiinttttNMUttNnttttttMtttt請輸入你的選擇 2為為為為 歷歷歷歷 遍遍遍遍 前中后層ABCDEFGHK B

25、DCAEHGKF DCBHKGFEA nBECFDGHJC歡迎使用本系統(tǒng)I IttHttttttNtttttlttttNttttHttttttttttttNttttHttttNttttNttttttNttttMtttttti-6'B二顆二叉樹并顯示玄一遍歷二叉護(hù)ts查詢二叉討的琛度和結(jié)點(diǎn)數(shù)4一査詢每層鉛點(diǎn)藪5 查找兩節(jié)點(diǎn)P和Q的最近共同祖先6 iRtHtt#tt請樹入坐的選擇* 3 度為：§ 關(guān)的密點(diǎn)數(shù)；?Itttft0fttttt tttt#1-lJ建一顆二叉樹并顯示2 -通歷_支茯''二叉洞的稀度和結(jié)點(diǎn)數(shù) 癥層拮點(diǎn)域G的請11Ftttttttt4歡迎使用本系統(tǒng)！ttttflttttMUttNttttNnttHNttttNttttNtttt