數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告二叉樹的遍歷

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告 設(shè)計題目：_二叉樹的遍歷_ 姓名：_王倫_ 學(xué)號：_211113206_ 專業(yè)：_物聯(lián)網(wǎng)_ 院系：_計算機科學(xué)與技術(shù)學(xué)院_ 班級：_1104_ 指導(dǎo)教師：_高秀梅_2013 年 3 月 22 日 摘要:本課程設(shè)計主要說明如何在c+編程環(huán)境下實現(xiàn)二叉樹的遍歷，遍歷方式包括：二叉樹的前序非遞歸遍歷、二叉樹的后續(xù)非遞歸遍歷。同時，此次課程設(shè)計還包括了求二叉樹每層節(jié)點數(shù)和求解任意倆點最近的共同祖先以及計算二叉樹深度的功能。英文摘要：abstract: this course design mainly shows how in c + + programming

2、environment to achieve binary tree traversal, traversal methods include: the preamble of binary tree non-recursive traversal, subsequent non-recursive traversal of binary tree. at the same time, the curriculum design includes for binary tree each layer node number and the solution of arbitrary two p

3、oints in recent common ancestor and calculating the function of the depth of a binary tree. 目 錄1、 問題描述.42、 需求分析.43、 概要設(shè)計.44、 數(shù)據(jù)結(jié)構(gòu)設(shè)計.55、 算法設(shè)計.56、 程序測試與實現(xiàn).107、 調(diào)試分析.138、 遇到的問題與解決方法.139、 心得體會.13一、問題描述問題描述：創(chuàng)建二叉樹并遍歷基本要求：1、 分別運用非遞歸的方式完成對二叉樹的先序和后序遍歷2、 輸出二叉樹的高度3、 輸出每一層的結(jié)點數(shù)4、 查找結(jié)點p 和結(jié)點q的最近共同祖先二、需求分析1 本程序的功能包

4、括建立二叉樹、前序遍歷二叉樹、后序遍歷二叉樹、求二叉樹的深度、求每層節(jié)點的個數(shù)、求任意倆個節(jié)點的共同祖先等。2 程序運行后顯現(xiàn)提示信息，等候用戶輸入07以進入相應(yīng)的操作功能。3 用戶輸入數(shù)據(jù)完畢，程序?qū)⑦\行相應(yīng)的程序并輸出運行結(jié)束。4 測試數(shù)據(jù)應(yīng)為char型數(shù)據(jù)。三、概要設(shè)計1、建立任意一個節(jié)點數(shù)不超過100二叉樹；2、前序遍歷節(jié)點1節(jié)點3節(jié)點2節(jié)點4節(jié)點53后序遍歷節(jié)點1節(jié)點3 節(jié)點2節(jié)點4 節(jié)點54、 數(shù)據(jù)結(jié)構(gòu)設(shè)計struct binode/節(jié)點聲明t data;/節(jié)點數(shù)據(jù)binode *lchild,*rchild;/二叉樹左右節(jié)點;class bitree/樹類型聲明templatef

5、riend ostream & operator(ostream & os,bitree & bt);/輸出函數(shù)public:bitree();/構(gòu)造函數(shù)bitree(void);/析構(gòu)函數(shù)binode *getroot();/返回根節(jié)點void preorder(binode *root);/前序遍歷void postorder(binode *root);/后序遍歷int depth(binode *root);/二叉樹深度void zjzx(binode *root,t q,t w);/倆點最近共同祖先void levelnum(binode *root,int hig);/每層節(jié)點個數(shù)

6、private:binode *root;/根節(jié)點binode *creat();void release(binode *root);void print(ostream & os);void println(ostream &os,binode *root,int death);5、 算法設(shè)計1、二叉樹的構(gòu)造templatebinode *bitree:creat()binode *bt;t ch;cout請輸入一個二叉樹的節(jié)點（以#作為結(jié)束標(biāo)記）ch;if(ch=#) bt=null;elsebt=new binode;bt-data=ch;bt-lchild=creat();bt-rc

7、hild=creat();return bt;templatebitree:bitree()cout請先建立一個二叉樹endl;coutendl;coutroot=creat();2、輸出函數(shù)templatevoid bitree:println(ostream & os,binode *root,int depth)if(root!=null)println(os,root-rchild,depth+1);for(int i=0;i4*(depth-1);i+)os ;os*-datalchild,depth+1);templatevoid bitree:print(ostream & os

8、)println(os,root,1);templateostream & operator(ostream & os,bitree &bt)bt.print(os);return os;3、 前序遍歷templatevoid bitree:preorder(binode *root)binode *s100;int top=-1;cout前序遍歷結(jié)果為endl;while(top!=-1 | root)while(root)coutdatalchild;if(top!=-1)root=stop-;root=root-rchild;4、 后序遍歷templatevoid bitree:post

9、order(binode *root)binode *s100;int top=-1;cout后序遍歷結(jié)果為lchild;if(top!=-1)root=stop-;coutdatarchild;5、 求二叉樹深度templateint bitree:depth(binode *root)int high,hl,hr;if(root=null) return 0;elsehl=depth(root-lchild);hr=depth(root-rchild);high=(hlhr)?(hl+1):(hr+1);return high;6、 求每層節(jié)點個數(shù)templatevoid bitree:l

10、evelnum(binode *root,int hig)int y=1;binode *q100;binode *s100;s0=root;if(root=null)cout此二叉樹為空二叉樹endl;elsecout此二叉樹第一層有1個節(jié)點endl;while(yhig)int k=-1,m=0,j,x,i,p=0;for(i=0;ilchild;if(qk!=null) p+;k+;qk=si-rchild;if(qk!=null) p+;if(p=0) break;elsej=k;i=-1;for(x=0;xj;x+)if(qx!=null)i+;si=qx;y+;cout第“y層的節(jié)

11、點個數(shù)為p個endl;7、 求倆點最近的共同祖先templatevoid bitree:zjzx(binode *root,t q,t w)binode *s100;int top=-1;while(top!=-1 | root)while(root)s+top=root;root=root-lchild;if(top!=-1)root=stop-;binode *m100,*t;int g=0,h=0;t=root;int top=-1;while(top!=-1 | t)while(t)if(t-data=q)g=1;if(t-data=w)w=1;if(g=1 & w=1)coutdat

12、alchild;if(top!=-1)t=mtop-;t=t-rchild;root=root-rchild;初始化程序3、 算法流程圖構(gòu)建二叉樹人機交互用戶輸入最近共同祖先輸出二叉樹每層個數(shù)二叉樹深度后序遍歷前序遍歷處理并輸出結(jié)果結(jié)束六、程序測試與實現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系 main caidandepthpostorderpostorderlevelnum zjzxpostorderpostorderpostorderpostorderpostorderpostorderpreorder2、主程序 int main()int xuanxiang;bitree bt;binode* root

13、=bt.getroot();caidan();while(1)cout請輸入需要執(zhí)行的功能的選項（阿拉伯?dāng)?shù)字）xuanxiang;switch(xuanxiang)case 1:coutbtendl;break; case 2:bt.preorder(root);coutendl;break; case 3:bt.postorder(root);coutendl;break; case 4:cout樹骸?的?深?度為a：阰bt.depth(root)endl;break; case 5:bt.levelnum(root,bt.depth(root); break; case 6:char q,

14、w;cout請?輸?入?需要癮查找的?兩?個?變?量?q;cinw;coutq和w最?近的?共2同?祖?先是?：阰 ;bt.zjzx(root,q,w);break; case 7: cout退?出?程序成功|！?endl; return 0; 3、 測試數(shù)據(jù)1 2 # 5 # 3 4 #4、 測試結(jié)果1、創(chuàng)建二叉樹2、 輸出二叉樹3、 前序遍歷4、 后序遍歷5、 求二叉樹深度6、 求任意倆點最近的共同祖先7、 退出程序7、 調(diào)試分析 通過前序遍歷的方式創(chuàng)建一個二叉樹，通過非遞歸的方式前序遍歷和后序遍歷此二叉樹，調(diào)試結(jié)果正確；用遞歸的方式求解二叉樹深度，調(diào)試結(jié)果正確；調(diào)用levelnum（）求解每層的節(jié)點個數(shù)；調(diào)用zjzx（）求解任意倆點最近的共同祖先；八、遇到的問題及解決辦法1、在實現(xiàn)求解二叉樹每層的節(jié)點個數(shù)時，生成總是出現(xiàn)“=”或“”等符號無用的出錯提示，后來經(jīng)過同學(xué)的提示才知道自己的錯誤在將for循環(huán)中的語句順序?qū)戝e了，應(yīng)該先比較再+而不是先+再比較；2、在求解最近的共同祖先時，求得的結(jié)果總是是根節(jié)點，后來對照課本重新檢查時發(fā)現(xiàn)自己在沒