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

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

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

4、3）如果2i+1>n,則結點i無右孩子；否則其右孩子rchild（i）是結點2i+1.3.3、二叉樹的遍歷先序遍歷：（1）訪問根節點（2）先序遍歷左子樹（3）先序遍歷右子樹中序遍歷：（1）中序遍歷左子樹（2）訪問根節點（3）中序遍歷右子樹后序遍歷：（1）后序遍歷左子樹（2）后序遍歷右子樹（3）訪問根節點status preordertraverse（ bitree t,status( * visit)(telemtype)）/采用二叉鏈表存儲結構，visit是對數據元素操作的應用函數。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)/采用二叉樹鏈表存儲結構，visit是對數據元素操作的應用函數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)/按先序次序輸入二叉樹中的節點的值（一個字符），空格字符表示空樹，構造二叉鏈表表示的二叉樹。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、調試與測試：調試方法與步驟：（1）測試二叉樹的存儲結構是否正確（2）測試二叉樹的遍歷是否正確（3）測試二叉樹的查找是否正確（4）測試二叉樹的輸出是否正確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<<"創建的樹是："dispbttree(

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

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