二叉樹的遞歸遍歷和葉子數(shù),深度

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告四實(shí)驗(yàn)內(nèi)容： 建一個二叉樹并對其進(jìn)行遍歷，并求出該樹的葉子數(shù)和深度 學(xué)號：20105101256 姓名：肖麗芳 一、上機(jī)實(shí)驗(yàn)的問題和要求（需求分析）： 題目 1從鍵盤接受輸入（先序），以二叉鏈表作為存儲結(jié)構(gòu)，建立二叉樹（以先序來建立），并采用遞歸算法對其進(jìn)行遍歷（先序、中序、后序），將遍歷結(jié)果打印輸出。2 求該二叉數(shù)的深度、并統(tǒng)計(jì)葉子結(jié)點(diǎn)的個數(shù)。二、程序設(shè)計(jì)的基本思想，原理和算法描述： 根據(jù)先序遍歷的性質(zhì)，先建立頭結(jié)點(diǎn)，再建立左右子樹，利用遞歸算法，先序建立二叉樹。對樹進(jìn)行遍歷時，根據(jù)先序、中序、后序不同的算法，將輸出不同的序列。求樹的葉子數(shù)和深度是要判斷樹是否為空，然后依據(jù)算

2、法看左右孩子。三、調(diào)試和運(yùn)行程序過程中產(chǎn)生的問題及采取的措施：寫主函數(shù)時注意不要抄寫錯誤，尤其是大小寫，注意函數(shù)的調(diào)用四、源程序及注釋 源程序 程序名： 二叉樹#include#include#include#define error 0#define ok 1#define overflow -1#define null 0typedef int status;typedef char telemtype;typedef struct bitnodetelemtype data;struct bitnode *lchild,*rchild;/左右孩子指針bitnode,*bitree;/二叉

3、樹的二叉鏈表存儲表示bitree creatbitree(bitree t)/按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個字符），空格字符表示空數(shù)/構(gòu)造二叉連表表示的二叉樹tchar ch;scanf(%c,&ch);if(ch=#) t=null;/用#表示空指針elset=(bitree)malloc(sizeof(bitnode);t-data=ch;/生成根結(jié)店t-lchild=creatbitree(t-lchild);/生成左子樹t-rchild=creatbitree(t-rchild);/生成右子樹return t;/createbitreevoid preorder(bitree t

4、) if(t!=null)/樹非空printf(%c,t-data);/訪問根結(jié)點(diǎn)preorder(t-lchild);/先序遍歷左子樹preorder(t-rchild);/先序遍歷右子樹/先序遍歷二叉樹void inorder(bitree t) if(t!=null)/樹非空inorder(t-lchild);/中序遍歷左子樹 printf(%c,t-data);/訪問根結(jié)點(diǎn)inorder(t-rchild);/中序遍歷右子樹/中序遍歷二叉樹void postorder(bitree t) if(t!=null)/樹非空postorder(t-lchild);/后序遍歷左子樹postor

5、der(t-rchild);/后序遍歷右子樹 printf(%c,t-data);/訪問根結(jié)點(diǎn)/后序遍歷二叉樹int leaf_count(bitree t)/求二叉樹中葉子結(jié)點(diǎn)的數(shù)目if(!t) return 0;/空樹沒有葉子else if(!t-lchild &!t-rchild ) return 1;/葉子節(jié)點(diǎn)else return leaf_count(t-lchild)+leaf_count(t-rchild);/左子樹的葉子數(shù)加上右子樹的葉子數(shù)int height(bitree t)int m,n;if(t=null) return 0;/空數(shù)深度為0else m=height(

6、t-rchild);/m為右孩子的深度n=height(t-lchild);/n為左孩子的深度if(mn)return(m+1);/如果右孩子的深度大于左孩子的深度則右孩子m+1else return(n+1);/否則左孩子n+1void main()bitree t=null; t=creatbitree(t);int depth;int leaf; printf(先序遍歷的順序是); preorder(t);printf(n); printf(中序遍歷的順序是); inorder(t);printf(n);printf(后序遍歷的順序是); postorder(t);printf(n);leaf=leaf_count(t);printf(此二叉樹的葉子數(shù)為：%dn,leaf);depth=height(t);printf(此二叉樹的深度為：%dn,depth);五、運(yùn)行結(jié)果 abc#de#