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

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

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

3、深度。在此，二叉樹的每一個(gè)結(jié)點(diǎn)中必須包括：值域，左指針域，右指針域。2.2 相關(guān)知識1、 status CreateBiTree(BiTree *T)/ 先序創(chuàng)建二叉樹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)->l

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

5、>rchild);/右子樹2、前序遍歷：先訪問根結(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹。具體實(shí)現(xiàn)如下：status PreOrderTraverse(BiTree T)if(T)printf("%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í)討論葉子結(jié)點(diǎn)個(gè)數(shù)無意義；當(dāng)樹非空時(shí)分為：一、左右子樹都不存在時(shí)，m自加1, m的值就為1,即葉子結(jié)點(diǎn)的個(gè)數(shù)為1;二、左右子樹存在，就用分別訪問出左右子

6、樹中葉子結(jié)點(diǎn)的個(gè)數(shù)，兩者相加就 為二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)。具體實(shí)現(xiàn)如下：/求二叉樹的葉結(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、中序遍歷：先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。具體實(shí)現(xiàn)如下：status InOrderTraverse(BiTree T)if(T)InOrderTraver

7、se(T->lchild);printf("%c”,T->data);InOrderTraverse(T->rchild);return OK;5、后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點(diǎn)。具體實(shí)現(xiàn)如下：status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c”,T->data);return OK;6、求二叉樹的深度：先定義2個(gè)整形變量3n,并將其初值設(shè)為0o如果樹為空

8、，則深度0；否則，先分別訪問出左右子樹的深度，再進(jìn)行比較，將較大的+1的結(jié)果就是所求二叉樹的深度。具體實(shí)現(xiàn)如下：status Max(int m, int n) /一個(gè)比較函數(shù)if (m > n)return m;elsereturn n;/獲取二叉樹的高度status HighBitree(BiTree t)if (t = NULL)return 0;elsereturn1+ Max(HighBitree(t->lchild),HighBitree(t->rchild);5、主函數(shù)包括：BiTree T , reateBiTree(&T) , NumberLeave

9、s(T), printf("%d",HighBitree(T) , PreOrderTraverse(T) , InOrderTraverse(T), PostOrderTraverse(T) , ArrangementTraverse(T)/主函數(shù)void main()BiTree T;printf("請創(chuàng)建二叉樹：n");CreateBiTree(&T);NumberLeaves(T);printf("葉節(jié)點(diǎn)個(gè)數(shù)為：");printf("%d",m);printf("n二叉樹的高度為:&quo

10、t;);printf("%d",HighBitree(T);printf("n先序遍歷:n");PreOrderTraverse(T);/* printf("n中序遍歷:n");InOrderTraverse(T);printf("n后序遍歷:n");PostOrderTraverse(T);*/ printf("n層次遍歷 n");ArrangementTraverse(T);printf("n");2程序設(shè)計(jì)92、概要設(shè)計(jì)2.1 主要數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)本設(shè)計(jì)中，對二叉樹采用

11、鏈?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大模塊。二叉樹的建立鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，前序遍歷，求葉 子結(jié)點(diǎn)的個(gè)數(shù)計(jì)算，中序遍歷，后序遍歷，深度求解。1）二叉樹的建立：定義二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，輸入數(shù)據(jù)生成二叉樹。二叉樹的前序遍歷：利用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)的前序遍歷；先訪問根結(jié)點(diǎn)，再依次訪問左右子樹。2） 二叉樹的求葉子

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

13、為兩個(gè)互為相交的集合 T1,T2,并且T1, T2都是二叉樹， 分別稱為根的左子樹和右子樹。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ù)輸出函數(shù)二叉樹的先序建立函數(shù) 二叉樹的先序遍歷函數(shù) 二叉樹的中序遍歷函數(shù) 二叉樹的后序遍歷函數(shù) 二叉樹的層序遍歷函數(shù) 求葉子節(jié)點(diǎn)函數(shù)求深度函

14、數(shù)比較函數(shù)3.3程序相關(guān)分析王函數(shù)void main() printf()scanf()CreateBiTree ()PreOrderTraverse ()InOrderTraverse()PostOrderTraverse ()ArrangementTraverse ()NumberLeaves()HighBitree()#include <stdio.h> /*#include <string.h> /*標(biāo)準(zhǔn)輸入輸出函數(shù)定義*/ 字符和字符串函數(shù)定義*/Max()#include <conio.h> /*控制臺(tái)進(jìn)行數(shù)據(jù)輸入和數(shù)據(jù)輸出的 函數(shù)*/#incl

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

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

17、 *lchild,*rchild;BiTNode,*BiTree;/全局變量，表示葉子個(gè)數(shù)int m=0;/二叉樹的創(chuàng)建status CreateBiTree(BiTree *T)/先序創(chuàng)建TelemType ch;scanf("%c",&ch);if(ch=ENDFLAG) *T=NULL;elseif(!(*T=(BiTNode *)malloczeof(BiTNode)printf("nOut of space.");getch();exit(0);(*T)->data=ch; / 生成根結(jié)點(diǎn)CreateBiTree(&(*T

18、)->lchild);/左子樹右子樹CreateBiTree(&(*T)->rchild);/ return OK;/先序遍歷status PreOrderTraverse(BiTree T)if(T)printf("%c”,T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);return OK;/*/中序status InOrderTraverse(BiTree T)if(T)InOrderTraverse(T->lchild);printf("%c”

19、,T->data);InOrderTraverse(T->rchild);return OK;/后序status PostOrderTraverse(BiTree T)if(T)PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c”,T->data);return OK;*/*用隊(duì)列層次遍歷*/存儲(chǔ)定義typedef char QElemType;/typedef int status;typedef struct QueueQElemType data;struct Q

20、ueue *next;Queue;/頭指針和尾指針typedef structQueue *front;Queue *rear;LinkQueue;/初始化隊(duì)列status InitQueue(LinkQueue *q)q->front=q->rear =NULL; /無頭結(jié)點(diǎn)return OK;/*判斷隊(duì)列是否為空*/status QueueEmpty(LinkQueue *Q)return (Q->front=NULL)&&(Q->rear=NULL);/*實(shí)際上只須判斷隊(duì)頭指針是否為空即可*/入隊(duì)void EnQueue(LinkQueue *q,

21、QElemType e)Queue *p;p=(Queue *)malloc(sizeof(Queue);/* 申請新結(jié)點(diǎn) */ p->data=e;p->next=NULL;if(QueueEmpty(q) q->front=q->rear=p;else /*x插入非空隊(duì)列的尾*/ q->rear->next=p; /*p鏈到原隊(duì)尾結(jié)點(diǎn)后*/q->rear=p;/* 隊(duì)尾指針指向新的尾*/出隊(duì)QElemType DeQueue(LinkQueue *q)Queue *p;QElemType e;if(QueueEmpty(q)printf("

22、;Queue underflow'n");/* 下溢 */exit；p=q->front;/*指向?qū)︻^結(jié)點(diǎn)*/e=p->data;/*保存對頭結(jié)點(diǎn)的數(shù)據(jù)*/q->front=p->next;/*將對頭結(jié)點(diǎn)從鏈上摘下*/if(q->rear=p)/*原隊(duì)中只有一個(gè)結(jié)點(diǎn)，刪去后隊(duì)列變空，此時(shí)隊(duì)頭指針已為空*/q->rear=NULL;free(p);/*釋放被刪隊(duì)頭結(jié)點(diǎn)*/return e;/* 返回原隊(duì)頭數(shù)據(jù)*/*層次遍歷思想遞歸a.根結(jié)點(diǎn)入隊(duì)列b.原隊(duì)左子樹的左右孩子(非空)入隊(duì)列c.原隊(duì)右子數(shù)的左右孩子(非空)入隊(duì)列*/層次遍歷入隊(duì)列st

23、atus Arrange(BiTree T,LinkQueue *Q)if(T)EnQueue(Q,T->data);Arrange(T->lchild,Q);Arrange(T->rchild,Q);return OK;/從隊(duì)列中輸出各元素status ArrangementTraverse(BiTree T)char e;LinkQueue Q;InitQueue(&Q);if(T)Arrange(T,&Q);/遞歸調(diào)用while(!QueueEmpty(&Q)e=DeQueue(&Q);printf("%c",e);r

24、eturn OK;/求二叉樹的葉結(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ù)status Max(int m, int n)if (m > n)return m;elsereturn n;/獲取二叉樹的高度status HighBitree(BiTree t)if (t = N

25、ULL)return 0;elsereturn 1 + Max(HighBitree(t->lchild), HighBitree(t->rchild);/主函數(shù)void main()BiTree T;printf("請創(chuàng)建二叉樹：n");CreateBiTree(&T);NumberLeaves(T);printf("葉節(jié)點(diǎn)個(gè)數(shù)為：");printf("%d",m);printf("n二叉樹的高度為:");printf("%d",HighBitree(T); printf("n先序遍歷:n");PreOrderTraverse(T);/* printf("n中序遍歷:n");InOrderTraverse(T);printf("n后序遍歷:n&qu