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

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

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

3、36.3測(cè)試數(shù)據(jù) .1 46.4測(cè)試結(jié)果 .157、 調(diào)試分析.178、遇到的問題及解決辦法 .179、心得體會(huì).1710、 參考文獻(xiàn) .18標(biāo)準(zhǔn)文檔1、問題描述1.1問題描述：創(chuàng)建二叉樹并遍歷基本要求：1、分別運(yùn)用非遞歸的方式完成對(duì)二義樹的先序和后序遍歷2、輸出二義樹的高度3、輸出每一層的結(jié)點(diǎn)數(shù)4、 查找結(jié)點(diǎn)P和結(jié)點(diǎn)Q的最近共同祖先2、需求分析1、本程序的功能包括二義樹的建立，二義樹的遞歸遍歷，二義樹的非遞歸遍歷，查 詢二義樹的深度，查詢每層的結(jié)點(diǎn)數(shù)，查找兩個(gè)結(jié)點(diǎn)的最近共同祖先，二義樹的打印2、程序運(yùn)行后顯現(xiàn)提示信息，等候用戶輸入06以進(jìn)入相應(yīng)的操作功能。3、用戶輸入數(shù)據(jù)完畢，程序?qū)⑤敵鲞\(yùn)行

4、結(jié)果。4、測(cè)試數(shù)據(jù)應(yīng)為字符型數(shù)據(jù)。3、概要設(shè)計(jì)3. 1創(chuàng)建二叉樹輸入數(shù)據(jù)不低丁15個(gè)，用遞歸方法建立二義樹。3.2二叉樹的非遞歸前序遍歷示意圖標(biāo)準(zhǔn)文檔圖3.2二義樹前序遍歷示意圖3.3二叉樹的后序非遞歸遍歷示意圖圖3.4二義樹后序遍歷示意圖4、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)4.1二叉樹結(jié)點(diǎn)數(shù)據(jù)類型定義為:template struct BiNode(BiNode *rchild,*lchild;/指向左右孩子的指針標(biāo)準(zhǔn)文檔T data;/結(jié)點(diǎn)數(shù)據(jù)信息；4.2二叉樹數(shù)據(jù)類型定義為：template class BiTree(template friend ostream & operator (ostre

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

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

7、 idx); /用數(shù)組創(chuàng)建二叉樹voidPreOrder(BiNode* root);前序遍歷void PostOrder(BiNode* root);后續(xù)遍歷voidLevelNum(BiNode* root);/層序遍歷voidpreorder(BiNode* root);/遞歸前序遍歷void inorder(BiNode* root); /遞歸中序遍歷void postorder(BiNode* root);遞歸后續(xù)遍歷void levelorder(BiNode*root);/層序遍歷int count(BiNode* root);計(jì)算結(jié)點(diǎn)數(shù)int depth(BiNode* roo

8、t);計(jì)算深度void display(ostream& os,BiNode* root, int dep); /打印static bool leastCommanAncestor(BiNode *root, T va, T vb, BiNode*&result, BiNode* parrent); /求最近共同祖先private :BiNode *rootptr;標(biāo)準(zhǔn)文檔;5、算法設(shè)計(jì)5.1創(chuàng)建二叉樹/實(shí)現(xiàn)外部遞歸調(diào)用void BiTree:creat()creat(rootptr);/類體內(nèi)遞歸創(chuàng)建二叉樹template void BiTree:creat(BiNode *

9、 & root) T item;cinitem;if (item= # ) root=NULL;elseroot= new BiNode; root-data=item; creat(root-lchild);creat(root-rchild);5.2非遞歸前序遍歷template void BiTree:PreOrder()PreOrder(rootptr);template void BiTree:PreOrder(BiNode* root) stack BiNode * s;while (root!=NULL|!s.empty() while (root)(coutdata;s

10、.push(root);root=root-lchild;)if (!s.empty()(root=s.top();s.pop();root=root-rchild;)標(biāo)準(zhǔn)文檔)5.3非遞歸后序遍歷template void BiTree:PostOrder()(PostOrder(rootptr);)template void BiTree:PostOrder(BiNode *root)(stackBiNode* s; /定義棧，節(jié)點(diǎn)類型為TreeNode BiNode *p = root;BiNode *pre = NULL; /pre表示最近一次訪問的結(jié)點(diǎn)while (p|!s.empt

11、y()(/沿著左孩子方向走到最左下。while (p)(s.push(p);p = p-lchild;)/get the top element of the stackp = s.top();/如果敬有右孩子或者其右孩子剛剛被訪問過if (p-rchild= NULL| p-rchild = pre)(/visit this element and then pop itcout data;s.pop();pre = p;p = NULL;) else(p = p-rchild;) /end of while(p | st.size()!=0)5.4求二叉樹的高度template int B

12、iTree:depth() (return depth(rootptr);)template int BiTree:depth(BiNode *root)(int rdep,ldep;標(biāo)準(zhǔn)文檔if (root=NULL) return 0;else(ldep=depth(root-lchild);rdep=depth(root-rchild);return (rdepldep?rdep:ldep)+1;)5.5求二叉樹每一層的結(jié)點(diǎn)數(shù)template void BiTree:LevelNum() (LevelNum(rootptr);)template void BiTree:LevelNum(

13、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)(cout 第level 層有l(wèi)ast-first 個(gè)結(jié)點(diǎn)”endl;level+;last=rear;first=front;標(biāo)準(zhǔn)文檔5

14、.6求兩節(jié)點(diǎn)最近共同祖先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-rchild!= NULL) &(root-rchild-data = n1 | root-rchild-dat

15、a = 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 data rchild, n1, n2);5.7算法流程圖標(biāo)準(zhǔn)文檔6、程序測(cè)試與實(shí)現(xiàn)6.

16、1函數(shù)之間的調(diào)用關(guān)系標(biāo)準(zhǔn)文檔cout tt# cout tt# coutx;switch (x)(case 1:(cout 請(qǐng)輸入二叉樹的前序遍歷：endl;cout (以#作為分支結(jié)尾，例如：A B # # C # # ) endl; Tree.creat();coutTree;coutendl; break ;case 2:(6.2主程序void main()BiTree Tree(1);while (1)(cout tt歡迎使用本系統(tǒng)！ ！endl;cout tt# endl;cout tt#endl;cout tt#1-創(chuàng)建一顆二叉樹并顯示endl;cout tt#2-遍歷二叉樹end

17、l;cout tt#3-查詢二叉樹的深度和結(jié)點(diǎn)數(shù)endl;cout tt#4-查詢每層結(jié)點(diǎn)數(shù)endl;cout tt#5-查找兩節(jié)點(diǎn)橋口Q勺最近共同祖先endl;cout tt#6-退出endl;endl;endl;標(biāo)準(zhǔn)文檔coutendl;cout 前序遍歷為：”；Tree.PreOrder();coutendl;cout 中序遍歷為：；Tree.inorder();coutendl;cout ”后序遍歷為：”；Tree.PostOrder();coutendl;cout 層序遍歷為：”；Tree.levelorder();coutendl;coutendl; break ;case 3:

18、(cout樹的深度為：Tree.depth()endl;cout樹的結(jié)點(diǎn)數(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; break ;case 6: return ; break ;default : cout請(qǐng)輸入正確的選擇！ ！ 層啟層1212 3 3 4 4 5 5請(qǐng) WWW 弟ttttttttttttttttttttttttttttttUtttttttttttttttttttttttttttttttttttttttttttttttttt4tttttt1創(chuàng)建一顆二叉樹并顯示2 -痕后_曳松二叉優(yōu)的尊度和結(jié)點(diǎn)數(shù) 備層皓點(diǎn)致ftttft4一萱詢母房結(jié)點(diǎn)教G一查找兩節(jié)點(diǎn)p和Q的最近共同祖先6-退.出蚣蟹選擇: 削入F數(shù) 以Q數(shù)祥最ifI口心：信息:標(biāo)準(zhǔn)文檔7、調(diào)試分析創(chuàng)建