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