PAGEPAGE2課題名:建立二叉樹,并對樹進(jìn)行操作系別:信息與計算科學(xué)系年級:2009級專業(yè):數(shù)學(xué)與應(yīng)用數(shù)學(xué)班級:一班學(xué)號:2009031116、2009031112、2009123123、2009031102、2009031110姓名:唐永橋、楊文升、李兵、陳丕權(quán)、范慶勇指導(dǎo)老師:李學(xué)勇2011-5-10目錄摘要 錯誤!未定義書簽。1、引言 錯誤!未定義書簽。1.1設(shè)計目標(biāo) 41.2相關(guān)知識 42、總體設(shè)計 92.1主要數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計 92.2模塊的劃分及其功能 93、詳細(xì)設(shè)計 103.1存儲結(jié)構(gòu)的建立由scanf（）函數(shù)實(shí)現(xiàn) 103.2重要函數(shù) 113.3程序相關(guān)分析 113.4結(jié)構(gòu)體和全局變量定義 113.5程序清單 124、測試數(shù)據(jù)及結(jié)果分析 185、總結(jié) 錯誤!未定義書簽。6、參考文獻(xiàn) 21［1］《數(shù)據(jù)結(jié)構(gòu)》（C語言版），嚴(yán)蔚敏，清華大學(xué)出版社，2003． 21returnOK;}4、中序遍歷：先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。具體實(shí)現(xiàn)如下：statusInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}returnOK;}5、后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點(diǎn)。具體實(shí)現(xiàn)如下：statusPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}returnOK;｝6、求二叉樹的深度：先定義2個整形變量m，n，并將其初值設(shè)為0。如果樹為空，則深度0；否則，先分別訪問出左右子樹的深度，再進(jìn)行比較，將較大的+1的結(jié)果就是所求二叉樹的深度。具體實(shí)現(xiàn)如下：statusMax(intm,intn)//一個比較函數(shù){if(m>n)returnm;elsereturnn;}//獲取二叉樹的高度statusHighBitree(BiTreet){if(t==NULL)return0;elsereturn1+Max(HighBitree(t->lchild),HighBitree(t->rchild));}主函數(shù)包括：BiTreeT，reateBiTree(&T)，NumberLeaves(T)，printf("%d",HighBitree(T))，PreOrderTraverse(T)，InOrderTraverse(T)，PostOrderTraverse(T)，ArrangementTraverse(T)//主函數(shù)voidmain(){BiTreeT;printf("請創(chuàng)建二叉樹：\n");CreateBiTree(&T);NumberLeaves(T);printf("葉節(jié)點(diǎn)個數(shù)為：");printf("%d",m);printf("\n二叉樹的高度為:");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è)計2、概要設(shè)計2.1主要數(shù)據(jù)存儲結(jié)構(gòu)設(shè)計本設(shè)計中，對二叉樹采用鏈?zhǔn)酱鎯Y(jié)構(gòu)，其結(jié)構(gòu)定義如下：typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;每個結(jié)點(diǎn)中設(shè)置三個域，即值域data，左指針域*lchild和右指針域*child。2.2模塊的劃分及其功能本程序分為：6大模塊。二叉樹的建立鏈?zhǔn)酱鎯Y(jié)構(gòu)，前序遍歷，求葉子結(jié)點(diǎn)的個數(shù)計算，中序遍歷，后序遍歷，深度求解。1）二叉樹的建立：定義二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，輸入數(shù)據(jù)生成二叉樹。二叉樹的前序遍歷：利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷；先訪問根結(jié)點(diǎn)，再依次訪問左右子樹。二叉樹的求葉子結(jié)點(diǎn)的個數(shù)計算：先分別求的左右子樹中各葉子結(jié)點(diǎn)的個數(shù)，再計算出兩者之和即為二叉樹的葉子結(jié)點(diǎn)數(shù)。二叉樹的中序遍歷：利用二叉鏈表作為存儲結(jié)構(gòu)的中序遍歷；先訪問左子樹，再訪問根結(jié)點(diǎn)，最后訪問右子樹。二叉樹的后序遍歷：利用二叉鏈表作為存儲結(jié)構(gòu)的前序遍歷；先訪問左右子樹，再訪問根結(jié)點(diǎn)求二叉樹的深度：首先判斷二叉樹是否為空，若為空則此二叉樹的深度為0.否則，就先求出左右子樹的深度并進(jìn)行比較，求較大的+1就為二叉樹的深度。主函數(shù)。核心算法的設(shè)計：二叉樹是n各結(jié)點(diǎn)的有窮個集合，它或者是空集（n=0）,或者同時滿足以下兩個條件：（1）：有且僅有一個稱為根的節(jié)點(diǎn)：（2）：其余節(jié)點(diǎn)分為兩個互為相交的集合T1,T2，并且T1，T2都是二叉樹，分別稱為根的左子樹和右子樹。3、詳細(xì)設(shè)計開始開始建立二叉樹建立二叉樹中序遍歷求葉子結(jié)點(diǎn)數(shù)先序遍歷后序遍歷求樹的深度主函數(shù)3.1存儲結(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)的右孩子的左孩子；八、最后輸入的是根結(jié)點(diǎn)的右孩子的右孩子。依次輸入數(shù)據(jù)。3.2重要函數(shù)主函數(shù)voidmain()輸入函數(shù)printf()輸出函數(shù)scanf()二叉樹的先序建立函數(shù)CreateBiTree（）二叉樹的先序遍歷函數(shù)PreOrderTraverse（）二叉樹的中序遍歷函數(shù)InOrderTraverse（）二叉樹的后序遍歷函數(shù)PostOrderTraverse（）二叉樹的層序遍歷函數(shù)ArrangementTraverse（）求葉子節(jié)點(diǎn)函數(shù)NumberLeaves（）求深度函數(shù)HighBitree（）比較函數(shù)Max（）3.3程序相關(guān)分析#include<stdio.h>/*標(biāo)準(zhǔn)輸入輸出函數(shù)定義*/#include<string.h>/*字符和字符串函數(shù)定義*/#include<conio.h>/*控制臺進(jìn)行數(shù)據(jù)輸入和數(shù)據(jù)輸出的函數(shù)*/#include<stdlib.h>/*常見數(shù)學(xué)函數(shù)定義*/（本程序中涉及很多關(guān)于字符串的函數(shù)，使用其函數(shù)，必須先定義）3.4結(jié)構(gòu)體和全局變量定義#defineOK1#defineERROR-1#defineENDFLAG'#'/*表示節(jié)點(diǎn)沒有左孩子或者沒有右孩子用#代替*/typedefcharTelemType;/*宏定義char類型*/typedefintstatus;/*宏定義int類型*/typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/*二叉樹的存儲結(jié)構(gòu)*/intm=0;/*全局變量，表示葉子個數(shù)*/3.5程序清單//頭文件#include"stdio.h"#include"conio.h"#include"stdlib.h"http://預(yù)定義宏常量#defineOK1#defineERROR-1#defineENDFLAG'#'typedefcharTelemType;typedefintstatus;//二叉樹的存儲結(jié)構(gòu)typedefstructBiTNode{TelemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;//全局變量，表示葉子個數(shù)intm=0;//二叉樹的創(chuàng)建statusCreateBiTree(BiTree*T){ //先序創(chuàng)建 TelemTypech; scanf("%c",&ch);if(ch==ENDFLAG)*T=NULL;else{if(!(*T=(BiTNode*)malloc(sizeof(BiTNode)))){ printf("\nOutofspace.");getch();exit(0);}(*T)->data=ch;//生成根結(jié)點(diǎn)CreateBiTree(&((*T)->lchild));//左子樹CreateBiTree(&((*T)->rchild));//右子樹}returnOK;}//先序遍歷statusPreOrderTraverse(BiTreeT){ if(T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } returnOK; }/*//中序statusInOrderTraverse(BiTreeT){if(T){InOrderTraverse(T->lchild);printf("%c",T->data);InOrderTraverse(T->rchild);}returnOK;}//后序statusPostOrderTraverse(BiTreeT){if(T){PostOrderTraverse(T->lchild);PostOrderTraverse(T->rchild);printf("%c",T->data);}returnOK;}*//*用隊(duì)列層次遍歷*///存儲定義typedefcharQElemType;//typedefintstatus;typedefstructQueue{ QElemTypedata; structQueue*next;}Queue;//頭指針和尾指針typedefstruct{ Queue*front;Queue*rear;}LinkQueue;//初始化隊(duì)列statusInitQueue(LinkQueue*q){ q->front=q->rear=NULL;//無頭結(jié)點(diǎn) returnOK;}/*判斷隊(duì)列是否為空*/statusQueueEmpty(LinkQueue*Q){return(Q->front==NULL)&&(Q->rear==NULL);/*實(shí)際上只須判斷隊(duì)頭指針是否為空即可*/}//入隊(duì)voidEnQueue(LinkQueue*q,QElemTypee){ 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ì)QElemTypeDeQueue(LinkQueue*q){ Queue*p; QElemTypee; if(QueueEmpty(q)) { printf("Queueunderflow\n");/*下溢*/ exit(1);} 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ì)中只有一個結(jié)點(diǎn)，刪去后隊(duì)列變空，此時隊(duì)頭指針已為空*/ q->rear=NULL; free(p);/*釋放被刪隊(duì)頭結(jié)點(diǎn)*/ returne;/*返回原隊(duì)頭數(shù)據(jù)*/}/*層次遍歷思想遞歸a.根結(jié)點(diǎn)入隊(duì)列b.原隊(duì)左子樹的左右孩子（非空）入隊(duì)列c.原隊(duì)右子數(shù)的左右孩子（非空）入隊(duì)列*///層次遍歷入隊(duì)列statusArrange(BiTreeT,LinkQueue*Q){ if(T) { EnQueue(Q,T->data); Arrange(T->lchild,Q); Arrange(T->rchild,Q);}returnOK;}//從隊(duì)列中輸出各元素statusArrangementTraverse(BiTreeT){chare;LinkQueueQ;InitQueue(&Q);if(T){Arrange(T,&Q);//遞歸調(diào)用while(!QueueEmpty(&Q)){e=DeQueue(&Q);printf("%c",e);}}returnOK;}//求二叉樹的葉結(jié)點(diǎn)個數(shù)statusNumberLeaves(BiTreeT){//先序遍歷得到葉結(jié)點(diǎn)的數(shù)目//m=0;if(T){ if(T->lchild==NULL&&T->rchild==NULL)m++; NumberLeaves(T->lchild); NumberLeaves(T->rchild);}returnOK;}//一個比較函數(shù)statusMax(intm,intn){if(m>n)returnm;elsereturnn;}//獲取二叉樹的高度statusHighBitree(BiTreet){if(t==NULL) return0;else return1+Max(HighBitree(t->lchild),HighBitree(t->rchild));}//主函數(shù)voidmain(){ BiTreeT; printf("請創(chuàng)建二叉樹：\n"); CreateBiTree(&T);NumberLeaves(T); printf("葉節(jié)點(diǎn)個數(shù)為："); printf("%d",m);printf("\n二叉樹的高度為:");printf("%d",HighBitree(T));printf("\n先序遍歷:\n");PreOrderTraverse(T);/*printf("\n中序遍歷:\n");InOrder