1、安徽省巢湖學(xué)院計(jì)算機(jī)與信息工程學(xué)院課程設(shè)計(jì)報(bào)告課程名稱 數(shù)據(jù)結(jié)構(gòu) 課題名稱 完全二叉樹操作演示 專業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 班級(jí) 10計(jì)本2班 學(xué)號(hào)10012131 姓名 聯(lián)系方式 指導(dǎo)教師 2011 年 12 月 27 目 錄1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目1.2、要求2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)2.2、所有功能模塊的流程圖3、詳細(xì)設(shè)計(jì)3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說(shuō)明3.2、算法的設(shè)計(jì)思想3.3、稀疏矩陣各種運(yùn)算的性質(zhì)變換4、調(diào)試與測(cè)試：4.1、調(diào)試方法與步驟：4.2、測(cè)試結(jié)果的分析與討論：5、時(shí)間復(fù)雜度的分析：6、源程序清單和執(zhí)行結(jié)果7、c程序設(shè)計(jì)總結(jié)8、致謝9、參考文

2、獻(xiàn)1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書1.1、題目完全二叉樹的操作演示1.2、要求（1）創(chuàng)建完全二叉樹（2）實(shí)現(xiàn)二叉樹的前序、中序和層次遍歷（3）求二叉樹的深度和葉子結(jié)點(diǎn)數(shù)（4）查找給定結(jié)點(diǎn)的雙親，祖先和左右孩子結(jié)點(diǎn)2、總體設(shè)計(jì)2.1、功能模塊設(shè)計(jì)根據(jù)課程設(shè)計(jì)題目的功能要求，各個(gè)功能模塊的組成框圖如下：建立結(jié)點(diǎn)左右孩子結(jié)束遍歷二叉樹創(chuàng)建二叉樹二叉樹的查找3、詳細(xì)設(shè)計(jì)3.1、程序中所采用的數(shù)據(jù)結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)的說(shuō)明1順序存儲(chǔ)結(jié)構(gòu)#define max_tree_size 100typedef telemtype sqbitree【max_tree_size】；sqbitree bt;用一組地址連續(xù)的存儲(chǔ)單元

3、一次自上而下，自左至又，存儲(chǔ)完全二叉樹上的節(jié)點(diǎn)元素,即將完全二叉樹上編號(hào)為i節(jié)點(diǎn)元素存儲(chǔ)在如上定義的一維數(shù)組中下標(biāo)為i1的分量中。2鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)由二叉樹的定義可知，二叉樹的節(jié)點(diǎn)由一個(gè)數(shù)據(jù)元素和分別指向其左右子樹的兩個(gè)分支構(gòu)成。表示二叉樹的結(jié)點(diǎn)至少要包含3個(gè)域：數(shù)據(jù)域，左右指針，還可增加一個(gè)指向雙親的結(jié)點(diǎn)，稱三叉鏈表。鏈表的頭指針指向二叉樹根節(jié)點(diǎn)。3.2、算法的設(shè)計(jì)思想對(duì)一棵有n個(gè)結(jié)點(diǎn)完全二叉樹的結(jié)點(diǎn)按層序編號(hào)，則對(duì)任一結(jié)點(diǎn)i,有（1）如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無(wú)雙親；如果i>1,則雙親是i/2(2)如果2i>n,則結(jié)點(diǎn)i無(wú)左孩子;否則其左孩子lchild(i)是結(jié)點(diǎn)2i。（

4、3）如果2i+1>n,則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子rchild（i）是結(jié)點(diǎn)2i+1.3.3、二叉樹的遍歷先序遍歷：（1）訪問(wèn)根節(jié)點(diǎn)（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷：（1）中序遍歷左子樹（2）訪問(wèn)根節(jié)點(diǎn)（3）中序遍歷右子樹后序遍歷：（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問(wèn)根節(jié)點(diǎn)status preordertraverse（ bitree t,status( * visit)(telemtype)）/采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)。status printelement（ telemtype）printf（e）；return ok；i

5、f (t)if (vistit(t->data) if (preordertraverse(t->lchild,visit) if (preordertraverse(t->rchild,visit) return ok;return error;else return ok; status inordertravserse(bitree t,status (*visit)(telemtype)/采用二叉樹鏈表存儲(chǔ)結(jié)構(gòu)，visit是對(duì)數(shù)據(jù)元素操作的應(yīng)用函數(shù)initstack(s); push (s,t);while (!stackempty(s)while(gettop(s,

6、p) &&p)push(s,p->lchild);pop(s,p);if (!stackempty(s)pop(s,p); if (!visit(p->data) return error;push(s,p->rchild);return ok;status createbitree(bitree &t)/按先序次序輸入二叉樹中的節(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹，構(gòu)造二叉鏈表表示的二叉樹。scnaf（&ch）;if (ch =)t=null;elseif (!(t=(bitnode * )malloc(sizeof(bitnode) ex

7、it(overflow);t->data=ch;createbitree(t->lchild);createbitree(t->rchild);return ok;4、調(diào)試與測(cè)試：調(diào)試方法與步驟：（1）測(cè)試二叉樹的存儲(chǔ)結(jié)構(gòu)是否正確（2）測(cè)試二叉樹的遍歷是否正確（3）測(cè)試二叉樹的查找是否正確（4）測(cè)試二叉樹的輸出是否正確6、源程序清單#include <iostream.h>#define null 0#define maxsize 100typedef struct nodechar data; struct node *lch; struct node *rch

8、;btnode;int count = 0;void creatbttree(btnode *&t,char *s)btnode *stmaxsize,*p=null;int top=-1,k,j=0; char ch; t=null;ch=sj;while(ch!='0')switch(ch)case '(':top+; sttop=p; k=1; break; case ')':top-; break;case ',':k=2; break;default:p=new btnode;p->data=ch;p-&g

9、t;lch=null;p->rch=null;if(t=null)t=p;elseswitch(k)case 1:sttop->lch=p;break;case 2:sttop->rch=p; break;j+；ch=sj;void dispbttree(btnode *t)if(t!=null)cout<<t->data;if(t->lch!=null)|(t->rch!=null)cout<<'(' dispbttree(t->lch);if(t->rch!=null)cout<<'

10、,'dispbttree(t->rch)；cout<<')'btnode *findnode(btnode *t,char x)btnode *p=null；if(t=null)return null;else if(t->data=x)return t;elsep=findnode(t->lch,x);if(p!=null)return p;else return findnode(t->rch,x);void preorder (btnode *t)if(t!=null)cout << t ->data <

11、< ' 'preorder (t->lch);preorder (t->rch);void inorder (btnode *t)if(t!=null)preorder (t->lch);cout << t ->data << ' 'preorder (t->rch);void postorder (btnode *t)if(t!=null)preorder (t->lch);preorder (t->rch);cout << t ->data << '

12、 'int btnodedepth (btnode *t)int lchildh, rchildh;if (t = null)return 0;elselchildh = btnodedepth (t->lch);rchildh = btnodedepth (t->rch);return (lchildh > rchildh) ? (lchildh + 1) : (rchildh + 1); int countnode (btnode *t)int num;if (t = null)num = 0;else num = 1 + countnode (t->lch

13、) + countnode (t->rch)；return (num);void countleaf (btnode *t)if (t != null)if (t->lch = null && t->rch = null)count +;countleaf (t->lch);countleaf (t->rch);void main()char x；btnode *t=null,*p=null;creatbttree(t,"a(b(,d),c)");cout<<"創(chuàng)建的樹是："dispbttree(

14、t);cout<<endl;cout<<"請(qǐng)輸入要查找的結(jié)點(diǎn)："<<endl;cin>>x;p=findnode(t,x);if(p=null)cout<<"不存在！"<<endl;elseif(p->lch=null)cout<<"沒(méi)有左孩子！"<<endl;else cout<<"左孩子是："<<p->lch->data<<endl;if(p->rch=nu

15、ll)cout<<"沒(méi)有右孩子！"<<endl;else cout<<"右孩子是："<<p->rch->data<<endl;cout << "按先序遍歷樹為："preorder (t);cout << endl;cout << "按中序遍歷樹為："inorder (t);cout << endl;cout << "按后序遍歷樹為："postorder (t);cout << endl;cout << "節(jié)點(diǎn)總數(shù)為："cout << countnode (t) << endl;cout << "葉子節(jié)點(diǎn)個(gè)數(shù)為："countleaf(t);cout << count << endl;cout << "這棵樹的深度為："cout << btnodedepth