1、一、設計目標二叉樹是形象地說既樹中每個節點最多只有兩個分支，它是一中重要的數 據類型。可以運用于建立家譜，公司所有的員工的職位圖，以及各種事物的分類 和各種機構的職位圖表。二叉樹是通過建立一個鏈式存儲結構，達到能夠實現前序遍歷，中序遍歷， 后序遍歷。以及能夠從輸入的數據中得知二叉樹的葉子結點的個數，二叉樹的深 度。在此，二叉樹的每一個結點中必須包括：值域，左指針域，右指針域。二、總體設計1對程序中定義的核心數據結構及對其說明：typedef struct BiTNode /創建二叉樹char data;struct BiTNode *lchild,*rchild;BiTNode,*BiTree

2、;在開頭定義了二叉樹的鏈式存儲結構，此處采用了每個結點中設置三個域， 即值域，左指針域和右指針域。模塊的劃分及其功能：本程序分為：7 大模塊。二叉樹的建立鏈式存儲結構、前序遍歷、求葉子結 點的個數計算、中序遍歷、后序遍歷、深度、主函數。1、二叉樹的建立鏈式存儲結構；首先typedef struct BiTNode：定義二叉 樹的鏈式存儲結構，此處采用了每個結點中設置三個域，即值域，*lchild：左 指針域和rchild：右指針域。2、二叉樹的前序遍歷；利用二叉鏈表作為存儲結構的前序遍歷：先訪問根 結點，再依次訪問左右子樹。3、二叉樹的求葉子結點的個數計算；先分別求得左右子樹中各葉子結點的個數

3、，再計算出兩者之和即為二叉樹的葉子結點數。4、二叉樹的中序遍歷；利用二叉鏈表作為存儲結構的中序遍歷：先訪問左子數，再訪問根結點，最后訪問右子樹。5、二叉樹的后序遍歷；利用二叉鏈表作為存儲結構的前序遍歷：先訪問左右子樹，再訪問根結點。6、求二叉樹的深度：首先判斷二叉樹是否為空，若為空則此二叉樹的深度為 0。否則，就先別求出左右子樹的深度并進行比較，取較大的+1 就為二叉樹的深度。7、主函數。核心算法的設計：二叉樹是n個節點的有窮個集合，它或者是空集(n=0),或者同時滿足以下兩個條件：(1):有且僅有一個稱為根的節點；(2)：其余節點分為兩個互不相交的集合T1，T2，并且T1，T2都是二叉樹，分

4、別稱 為根的左子樹和右子樹。三、詳細設計：1、存儲結構的建立由scanfl()函數實現：一、首先輸入的是根結點；二、然后輸入的是根結點的左孩子；三、再者輸入的是根結點的右孩子；四、接著輸入的是根結點左孩子的左孩子；五、輸入的是根結點的左孩子的；六、輸入的是根結點的右孩子的左孩子；七、輸入的是根結點的右孩子的左孩子；八、最后輸入的是根結點的右孩子的右孩子。依次輸入數據。具體函數實現如下：typedef struct BiTNode /創建二叉樹 char data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;BiTree Create(BiTr

5、ee T)char ch; ch=getchar();scanf(%c,&ch1); if(ch=0) T=NULL;elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode) 申請新結點 printf(Error!);T-data=ch;值域T-lchild=Create(T-lchild); 左指針域 T-rchild=Create(T-rchild); 右指針域return T;在創建的二叉樹中，左右孩子都為字符型。char的作用是輸入n個任意的字符，而且在輸入n個字符后，必須輸入N+1個0, 才能得到本程序所有能夠實現的功能。T=Nul是將二叉樹置為空。i

6、f(!(T=(BiTNode *)malloc(sizeof(BiTNode) 采用動態申請新結點的方式，不僅 實現起來方便，而且還節省大量的存儲空間。T-data=ch;值域T-lchild=Create(T-lchild);左指針域T-rchild=Create(T-rchild);右指針域 將二叉樹中的每一個結點設置為：值域，左指針域，右指針。 這一小段程序實現了二叉樹的置空，二叉樹的建立，二叉樹的存儲。2、前序遍歷：先訪問根結點，再訪問左子樹，最后訪問右子樹。具體實現如下：void Preorder(BiTree T) /前序遍歷 if(T) printf(%c,T-data); Pr

7、eorder(T-lchild); Preorder(T-rchild);3、求葉子結點的個數：用 sum 變量表示葉子結點的總個數，用 m、n 分別 表示訪問的左右子樹中葉子結點的個數。 當樹為空是此時討論葉子結點個數無意義；當樹非空時分為：一、左右子數都不存在時，sum自加1, sum的值就為1, 即葉子結點的個數為1； 二、左右子樹存在,就用分別訪問出左右子樹中葉子結點的個數,兩者相加 就為二叉樹葉子結點的個數。具體實現如下：int Sumleaf(BiTree T) /求葉子結點的總個數int sum=0,m,n;if(T) if(!T-lchild)&(!T-rchild) sum+

8、;m=Sumleaf(T-lchild); /左子樹葉子結點的個數 sum+=m;n=Sumleaf(T-rchild); /右子樹葉子結點的個數 sum+=n;return sum;4、中序遍歷：先訪問左子樹,再訪問根結點,最后訪問右子樹。具體實現如下：void zhongxu(BiTree T) /中序遍歷if(T) zhongxu(T-lchild); printf(%c,T-data); zhongxu(T-rchild);5、后序遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結點。具體實現如下：void houxu(BiTree T) /后序遍歷if(T)houxu(T-lchild)

9、;houxu(T-rchild); printf(%c,T-data);6、求二叉樹的深度：先定義三個整形變量dep、depl、depr，并將的初值設為0。如果 樹為空，則 dep=0； 否則，先分別訪問出左右子樹的深度，再進行比較，將較大的+1 的 結果就是所求二叉樹的深度。具體函數實現如下：int Depth(BiTree T) /二叉數的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild); /左子樹深度 depr=Depth(T-rchild);/ 右子數深度dep=l+(depldepr?depl:depr);比較左右

10、子樹中較大的，較大的+1為樹的深度return dep;7、主函數：包括：二叉樹的數據結構BiTree T、函數sum、dep、sumleaf、Depth前序遍歷Preoder、中序遍歷zhongxu、后序遍歷houxu。main()BiTree T;int sum,dep;T=Create(T);Preorder(T); printf(n); zhongxu(T); printf(n); houxu(T); printf(n); sum=Sumleaf(T); printf(%d,sum); dep=Depth(T);printf(n%d,dep);四、程序清單：#include stdio

11、.h #include string.h #includestdlib.h/#define NULL 0 char ch1;typedef struct BiTNode /創建二叉樹 char data;struct BiTNode *lchild,*rchild; BiTNode,*BiTree;BiTree Create(BiTree T) char ch;ch=getchar(); scanf(%c,&ch1);if(ch=0) T=NULL; elseif(!(T=(BiTNode *)malloc(sizeof(BiTNode)/動態申請地址 printf(Error!);T-dat

12、a=ch;值域T-lchild=Create(T-lchild);左指針域T-rchild=Create(T-rchild);右指針域return T;void Preorder(BiTree T) /前序遍歷 if(T)printf(%c,T-data);Preorder(T-lchild); Preorder(T-rchild);int Sumleaf(BiTree T) /求葉子結點的總個數int sum=0,m,n;if(T)if(!T-lchild)&(!T-rchild)sum+;m=Sumleaf(T-lchild); /左子樹葉子結點的個數 sum+=m;n=Sumleaf(T

13、-rchild); /右子樹葉子結點的個數 sum+=n;return sum;void zhongxu(BiTree T) /中序遍歷if(T) zhongxu(T-lchild); printf(%c,T-data); zhongxu(T-rchild);void houxu(BiTree T) /后序遍歷if(T) houxu(T-lchild); houxu(T-rchild); printf(%c,T-data);int Depth(BiTree T) /二叉數的深度int dep=0,depl,depr;if(!T) dep=0;elsedepl=Depth(T-lchild);

14、/左子樹深度 depr=Depth(T-rchild);/ 右子數深度dep=l+(depldepr?depl:depr);比較左右子樹中較大的，較大的+1為樹的深度 return dep;main()BiTree T;int sum,dep;T=Create(T); Preorder(T); printf(n); zhongxu(T); printf(n); houxu(T); printf(n); sum=Sumleaf(T); printf(%d,sum); dep=Depth(T); printf(n%d,dep);五、測試結果輸入：d g j 輸入：d g j 0 0 0 0輸出： dgj 2 gdj gjd 1輸入：4 5 6 7 8 9 10 0 0 0 0 0 0 0 0 0輸出：4 5 7 8 6 9 10 4 7 5 8 4 9 6 10 7 8 5 9 10 6 4 2六、總結本程序基本上實現了，前序遍歷，中序遍歷，后序遍歷，葉子結 點個數的求出，二叉樹深