建立二叉樹(shù)-并對(duì)樹(shù)進(jìn)行操作數(shù)據(jù)結(jié)構(gòu)課程設(shè)

1、建立二叉樹(shù)-并對(duì)樹(shù)進(jìn)行操作數(shù) 據(jù)結(jié)構(gòu)課程設(shè)課題名：建立二叉樹(shù)，并對(duì)樹(shù)進(jìn)行操作系別:信息與計(jì)算科學(xué)系年級(jí):2009級(jí)專業(yè)：數(shù)學(xué)與應(yīng)用數(shù)學(xué)班級(jí)：一班學(xué)號(hào):2009031116、2009031112、2009123123 2009031102、2009031110姓名:唐永橋、楊文升、李兵、陳丕權(quán)、范慶勇指導(dǎo)老師:李學(xué)勇2011-5-10目錄摘 要錯(cuò)誤!未定義書(shū)簽。1、 引言 錯(cuò)誤!未定義書(shū)簽。1.1設(shè)計(jì)目標(biāo)5.1.2相關(guān)知識(shí)5.2、總體設(shè)計(jì).102.1主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 102.2模塊的劃分及其功能103、詳細(xì)設(shè)計(jì).1.13.1存儲(chǔ)結(jié)構(gòu)的建立由scanf ()函數(shù)實(shí)現(xiàn) 1 13.2重要函數(shù)123

2、.3程序相關(guān)分析123.4結(jié)構(gòu)體和全局變量定義123.5程序清單134、測(cè)試數(shù)據(jù)及結(jié)果分析1.95、總結(jié) 錯(cuò)誤!未定義書(shū)簽。6、參考文獻(xiàn)22數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)，嚴(yán)蔚敏，清華大學(xué)出版社，2003. 2231、運(yùn)行環(huán)境、開(kāi)發(fā)工具運(yùn)行環(huán)境：VC+ 6.0開(kāi)發(fā)工具：電腦2、需求分析2.1 設(shè)計(jì)目標(biāo)二叉樹(shù)是形象的說(shuō)既樹(shù)中每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支，它是一個(gè)重要的數(shù) 據(jù)類型?？梢赃\(yùn)用于建立家譜，公司所有的員工的職位圖，以及各種事物的分 類和各種機(jī)構(gòu)的職位圖表。二叉樹(shù)是通過(guò)建立一個(gè)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，達(dá)到能夠?qū)崿F(xiàn)前序遍歷，中序遍歷， 后序遍歷。以及能夠從輸入的數(shù)據(jù)中得知二叉樹(shù)的葉子節(jié)點(diǎn)的個(gè)數(shù)，二叉樹(shù)的 深度。在此

3、，二叉樹(shù)的每一個(gè)結(jié)點(diǎn)中必須包括：值域，左指針域，右指針域。2.2 相關(guān)知識(shí)1、 status CreateBiTree(BiTree *T)/ 先序創(chuàng)建二叉樹(shù)TelemType ch;scanf("%c",&ch);if(ch=ENDFLAG) *T=NULL;else if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)printf("nOut of space.");getch();exit(0);(*T)->data=ch; / 生成根結(jié)點(diǎn)CreateBiTree(&(*T)->lchild

4、);/左子樹(shù)CreateBiTree(&(*T)->rchild);/右子樹(shù)return OK;TelemType 的作用是輸入 n 各任意的字符，而且在輸入 n 個(gè)字符后，必須輸入 N=1個(gè)0,才能夠得到本程序所有能夠?qū)崿F(xiàn)的功能。T=Null是將二叉樹(shù)置為空。if(!(*T=(BiTNode *)malloc(sizeof(BiTNode)采用動(dòng)態(tài)申請(qǐng)結(jié)點(diǎn)的方式，不僅實(shí)現(xiàn)起來(lái)方便，而且還節(jié)省大量的存儲(chǔ)空間。(*T)->data=ch; /生成根結(jié)點(diǎn)CreateBiTree(&(*T)->lchild);左子樹(shù)CreateBiTree(&(*T)-&g

5、t;rchild);右子樹(shù)2、前序遍歷：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。具體實(shí)現(xiàn)如下：status PreOrderTraverse(BiTree T)if(T)prin tf("%c",T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);return OK;3、求葉子結(jié)點(diǎn)的個(gè)數(shù)：用 m變量表示葉子結(jié)點(diǎn)的總個(gè)數(shù)。當(dāng)樹(shù)為空是此時(shí)討論葉子結(jié)點(diǎn)個(gè)數(shù)無(wú)意義；當(dāng)樹(shù)非空時(shí)分為：一、左右子樹(shù)都不存在時(shí)，m自加1, m的值就為1,即葉子結(jié)點(diǎn)的個(gè)數(shù)為1；二、左右子樹(shù)存在，就用分別訪問(wèn)出

6、左右子樹(shù)中葉子結(jié)點(diǎn)的個(gè)數(shù)，兩者相加就 為二叉樹(shù)葉子結(jié)點(diǎn)的個(gè)數(shù)。具體實(shí)現(xiàn)如下：/求二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)status NumberLeaves(BiTree T)/先序遍歷得到葉結(jié)點(diǎn)的數(shù)目m=0;if(T)if(T->lchild=NULL&&T->rchild=NULL) m+;NumberLeaves(T->lchild);NumberLeaves(T->rchild);return OK;4、中序遍歷：先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。具體實(shí)現(xiàn)如下：status InO rderTraverse(BiTree T)if(T)In OrderTr

7、averse(T->lchild);prin tf("%c",T->data);In OrderTraverse(T->rchild);return OK;5、后序遍歷：先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。具體實(shí)現(xiàn)如下：status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);prin tf("%c",T->data);return OK;6求二叉樹(shù)的深度：先定義2個(gè)整形變量m

8、 n,并將其初值設(shè)為0。如果樹(shù)為空，則深度0; 否則，先分別訪問(wèn)出左右子樹(shù)的深度，再進(jìn)行比較，將較大的+1的結(jié)果就是所求二叉樹(shù)的深度。具體實(shí)現(xiàn)如下：status Max(i nt m, i nt n) /一個(gè)比較函數(shù)if (m > n) return m;elsereturn n;/獲取二叉樹(shù)的高度 status HighBitree(BiTree t) if (t = NULL)return 0;elsereturnMax(HighBitree(t->lchild),HighBitree(t->rchild);5、主函數(shù)包括：BiTreeprin tf("%d&q

9、uot;,HighBitree(T) PostOrderTraverse(T),/主函數(shù)T ， reateBiTree(&T) ， NumberLeaves(T)， ，PreOrderTraverse(T) ， InOrderTraverse(T) ，Arra ngeme ntTraverse(T)void mai n()BiTree T;prin tf("請(qǐng)創(chuàng)建二叉樹(shù)：CreateBiTree(&T);NumberLeaves(T);prin tf("葉節(jié)點(diǎn)個(gè)數(shù)為：prin tf("%d",m);printf("n二叉樹(shù)的高度

10、為:");prin tf("%d",HighBitree(T);printf("n先序遍歷:n");PreOrderTraverse(T);/* printf("n中序遍歷:n");In OrderTraverse(T);n");");printf("n后序遍歷:n");PostOrderTraverse(T);*/ prin tf("n層次遍歷 n");Arran geme ntTraverse(T);prin tf("n");2程序設(shè)計(jì)112

11、、概要設(shè)計(jì)2.1主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本設(shè)計(jì)中，對(duì)二叉樹(shù)采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其結(jié)構(gòu)定義如下：typedef struct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;每個(gè)結(jié)點(diǎn)中設(shè)置三個(gè)域，即值域data，左指針域*lchild和右指針域*child。2.2模塊的劃分及其功能本程序分為：6大模塊。二叉樹(shù)的建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，前序遍歷，求葉 子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算，中序遍歷，后序遍歷，深度求解。1）二叉樹(shù)的建立：定義二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，輸入數(shù)據(jù)生成二叉樹(shù)。 二叉樹(shù)的前序遍歷：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的前序遍歷；先訪

12、問(wèn)根結(jié) 點(diǎn)，再依次訪問(wèn)左右子樹(shù)。2）二叉樹(shù)的求葉子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算：先分別求的左右子樹(shù)中各葉子結(jié)點(diǎn)的個(gè)數(shù)，再計(jì)算出兩者之和即為二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)。3）二叉樹(shù)的中序遍歷：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的中序遍歷；先訪 問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。4）二叉樹(shù)的后序遍歷：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的前序遍歷；先訪 問(wèn)左右子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)5）求二叉樹(shù)的深度：首先判斷二叉樹(shù)是否為空，若為空則此二叉樹(shù)的深度為0.否則，就先求出左右子樹(shù)的深度并進(jìn)行比較，求較大的+1就為二叉樹(shù)的深度。6）主函數(shù)。核心算法的設(shè)計(jì)：二叉樹(shù)是n各結(jié)點(diǎn)的有窮個(gè)集合，它或者是空集（n=0）, 或者同時(shí)滿足以下兩個(gè)條件：（1）：有且

13、僅有一個(gè)稱為根的節(jié)點(diǎn)：（2）: 其余節(jié)點(diǎn)分為兩個(gè)互為相交的集合T1,T2，并且T1, T2都是二叉樹(shù)，分別稱為根的左子樹(shù)和右子樹(shù)。3、詳細(xì)設(shè)計(jì)3.1存儲(chǔ)結(jié)構(gòu)的建立由scanf ()函數(shù)實(shí)現(xiàn)一、首先輸入的是根結(jié)點(diǎn)；二、然后輸入的是根結(jié)點(diǎn)的左孩子；三、再者輸入的是根結(jié)點(diǎn)的右孩子；四、接著輸入的是根結(jié)點(diǎn)左孩子的左孩子;五、輸入的是根結(jié)點(diǎn)的左孩子的；六、輸入的是根結(jié)點(diǎn)的右孩子的左孩子；七、輸入的是根結(jié)點(diǎn)的右孩子的左孩子；ii八、最后輸入的是根結(jié)點(diǎn)的右孩子的右孩子。依次輸入數(shù)據(jù)3.2重要函數(shù)主函數(shù)、void mai n()輸入函數(shù)printf()輸出函數(shù)sca nf()二叉樹(shù)的先序建立函數(shù)CreateB

14、iTree()二叉樹(shù)的先序遍歷函數(shù)PreOrderTraverse（）二叉樹(shù)的中序遍歷函數(shù)InO rderTraverse（）二叉樹(shù)的后序遍歷函數(shù)PostOrderTraverse（）二叉樹(shù)的層序遍歷函數(shù)Arran geme ntTraverse（）求葉子節(jié)點(diǎn)函數(shù)NumberLeaves()求深度函數(shù)HighBitree()比較函數(shù)Max（）3.3程序相關(guān)分析#i nclude <stdio.h> /*標(biāo)準(zhǔn)輸入輸出函數(shù)定義*/#include <string.h> /*字符和字符串函數(shù)定義*/#in elude <con io.h> /*控制臺(tái)進(jìn)行數(shù)據(jù)輸入和

15、數(shù)據(jù)輸出的函數(shù)*/#include <stdlib.h> /*常見(jiàn)數(shù)學(xué)函數(shù)定義*/ （本程序中涉及很多關(guān)于字符串的函數(shù)，使用其函數(shù)，必須先定義）3.4結(jié)構(gòu)體和全局變量定義#defi ne OK 1#defi ne ERROR -1#defi ne ENDFLAG '#'/* 表示節(jié)點(diǎn)沒(méi)有左孩子或者沒(méi)有右孩子用 #代替*/ typedef char TelemType;/* 宏定義 char 類型 */ typedef int status;/* 宏定義 int 類型 */typedef struct BiTNodeTelemType data;struct BiTN

16、ode *lchild,*rchild;BiTNode,*BiTree; /*二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) */int m=0; /*全局變量，表示葉子個(gè)數(shù)*/3.5程序清單/頭文件#include "stdio.h"#i nclude "coni o.h"#i nclude "stdlib.h"/預(yù)定義宏常量#defi ne OK 1#defi ne ERROR -1#defi ne ENDFLAG '#' typedef char TelemType; typedef int status;/二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)typedef s

17、truct BiTNodeTelemType data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree;/全局變量，表示葉子個(gè)數(shù)int m=0;/二叉樹(shù)的創(chuàng)建status CreateBiTree(BiTree *T)/先序創(chuàng)建TelemType ch; sca nf("%c",&ch);if(ch=ENDFLAG) *T=NULL;elseif(!(*T=(BiTNode *)malloc(sizeof(BiTNode) prin tf("nOut of space.");getch();exit(

18、0);(*T)->data=ch; /生成根結(jié)點(diǎn)左子樹(shù)CreateBiTree(&(*T)->lchild);右子樹(shù)CreateBiTree(&(*T)->rchild); return OK;/先序遍歷status PreOrderTraverse(BiTree T)if(T)prin tf("%c",T->data);PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild);return OK;/*/中序status InO rderTraverse(BiTree

19、 T)if(T)In OrderTraverse(T->lchild);prin tf("%c",T->data);In OrderTraverse(T->rchild);return OK;/后序status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild); prin tf("%c",T->data);return OK;*/*用隊(duì)列層次遍歷*/存儲(chǔ)定義typedef char QEle

20、mType;/typedef int status;typedef struct QueueQElemType data; struct Queue *n ext;Queue;/頭指針和尾指針typedef structQueue *front;Queue *rear;Lin kQueue;/初始化隊(duì)列status In itQueue(L in kQueue *q)q->fron t=q->rear =NULL; /-無(wú)頭結(jié)點(diǎn)return OK;/*判斷隊(duì)列是否為空*/status QueueEmpty(L in kQueue *Q)return (Q->fro nt=NU

21、LL)&&(Q->rear=NULL);/*實(shí)際上只須判斷隊(duì)頭指針是否為空即可*/入隊(duì)void En Queue(L in kQueue *q,QEIemType e)Queue *p;p=(Queue *)malloc(sizeof(Queue);/*申請(qǐng)新結(jié)點(diǎn) */p->data=e;p-> next=NULL;if(QueueEmpty(q)q->fron t=q->rear=p;else/*x插入非空隊(duì)列的尾*/q->rear->next=p; /*p鏈到原隊(duì)尾結(jié)點(diǎn)后*/q->rear=p;/* 隊(duì)尾指針指向新的尾*/出隊(duì)

22、QElemType DeQueue(L in kQueue *q)Queue *p;QEIemType e;if(QueueEmpty(q)prin tf("Queue un derflow'n");/*下溢 */exit(1);p=q->front;/*指向?qū)︻^結(jié)點(diǎn)*/e=p->data;/*保存對(duì)頭結(jié)點(diǎn)的數(shù)據(jù)*/q->front=p->next;/*將對(duì)頭結(jié)點(diǎn)從鏈上摘下*/if(q->rear=p)/* 原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已 為空*/q->rear=NULL;free(p);/*釋放被刪隊(duì)頭結(jié)點(diǎn)*

23、/return e;/*返回原隊(duì)頭數(shù)據(jù)*/*層次遍歷思想遞歸a. 根結(jié)點(diǎn)入隊(duì)列b. 原隊(duì)左子樹(shù)的左右孩子(非空)入隊(duì)列c. 原隊(duì)右子數(shù)的左右孩子(非空)入隊(duì)列*/層次遍歷入隊(duì)列status Arran ge(BiTree T,Lin kQueue *Q)if(T)En Queue(Q,T->data);Arran ge(T->lchild,Q);Arran ge(T->rchild,Q);return OK;/從隊(duì)列中輸出各元素status Arran geme ntTraverse(BiTree T)char e;Lin kQueue Q;In itQueue(&Q

24、);if(T)Arran ge(T,&Q);遞歸調(diào)用while(!QueueEmpty(&Q)e=DeQueue(&Q);prin tf("%c",e);return OK;/求二叉樹(shù)的葉結(jié)點(diǎn)個(gè)數(shù)status NumberLeaves(BiTree T)/先序遍歷得到葉結(jié)點(diǎn)的數(shù)目m=0;if(T)if(T->lchild=NULL&&T->rchild=NULL) m+;NumberLeaves(T->lchild);NumberLeaves(T->rchild);return OK;/ 一個(gè)比較函數(shù)statu

25、s Max(i nt m, int n)if (m > n)return m;elsereturn n;/獲取二叉樹(shù)的高度status HighBitree(BiTree t)if (t = NULL)return 0;elsereturn 1 + Max(HighBitree(t->lchild), HighBitree(t->rchild);/主函數(shù)void mai n()BiTree T;prin tf("請(qǐng)創(chuàng)建二叉樹(shù)：n");CreateBiTree(&T);NumberLeaves(T);printf("葉節(jié)點(diǎn)個(gè)數(shù)為：");prin tf("%d",m);printf("n二叉樹(shù)的高度為:");prin tf("%d",HighB