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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目：_二叉樹(shù)的遍歷_ 姓名：_王倫_ 學(xué)號(hào)：_211113206_ 專業(yè)：_物聯(lián)網(wǎng)_ 院系：_計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院_ 班級(jí)：_1104_ 指導(dǎo)教師：_高秀梅_2013 年 3 月 22 日 摘要:本課程設(shè)計(jì)主要說(shuō)明如何在c+編程環(huán)境下實(shí)現(xiàn)二叉樹(shù)的遍歷，遍歷方式包括：二叉樹(shù)的前序非遞歸遍歷、二叉樹(shù)的后續(xù)非遞歸遍歷。同時(shí)，此次課程設(shè)計(jì)還包括了求二叉樹(shù)每層節(jié)點(diǎn)數(shù)和求解任意倆點(diǎn)最近的共同祖先以及計(jì)算二叉樹(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、 問(wèn)題描述.42、 需求分析.43、 概要設(shè)計(jì).44、 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì).55、 算法設(shè)計(jì).56、 程序測(cè)試與實(shí)現(xiàn).107、 調(diào)試分析.138、 遇到的問(wèn)題與解決方法.139、 心得體會(huì).13一、問(wèn)題描述問(wèn)題描述：創(chuàng)建二叉樹(shù)并遍歷基本要求：1、 分別運(yùn)用非遞歸的方式完成對(duì)二叉樹(shù)的先序和后序遍歷2、 輸出二叉樹(shù)的高度3、 輸出每一層的結(jié)點(diǎn)數(shù)4、 查找結(jié)點(diǎn)p 和結(jié)點(diǎn)q的最近共同祖先二、需求分析1 本程序的功能包

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

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

6、private:binode *root;/根節(jié)點(diǎn)binode *creat();void release(binode *root);void print(ostream & os);void println(ostream &os,binode *root,int death);5、 算法設(shè)計(jì)1、二叉樹(shù)的構(gòu)造templatebinode *bitree:creat()binode *bt;t ch;cout請(qǐng)輸入一個(gè)二叉樹(shù)的節(jié)點(diǎn)（以#作為結(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請(qǐng)先建立一個(gè)二叉樹(shù)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、 求二叉樹(shù)深度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é)點(diǎn)個(gè)數(shù)templatevoid bitree:l

10、evelnum(binode *root,int hig)int y=1;binode *q100;binode *s100;s0=root;if(root=null)cout此二叉樹(shù)為空二叉樹(shù)endl;elsecout此二叉樹(shù)第一層有1個(gè)節(jié)點(diǎn)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、點(diǎn)個(gè)數(shù)為p個(gè)endl;7、 求倆點(diǎn)最近的共同祖先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ù)人機(jī)交互用戶輸入最近共同祖先輸出二叉樹(shù)每層個(gè)數(shù)二叉樹(shù)深度后序遍歷前序遍歷處理并輸出結(jié)果結(jié)束六、程序測(cè)試與實(shí)現(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請(qǐng)輸入需要執(zhí)行的功能的選項(xiàng)（阿拉伯?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樹(shù)骸?的?深?度為a：阰bt.depth(root)endl;break; case 5:bt.levelnum(root,bt.depth(root); break; case 6:char q,

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