二叉樹實驗報告

1、二叉樹實驗報告問題描述（1）問題描述：用先序遞歸過程建立二叉樹 (存儲結(jié)構(gòu)：二叉鏈表)。輸入數(shù)據(jù)按先序遍歷所得序列輸入，當某結(jié)點左子樹或右子樹為空時，輸入*號，如輸入abc*d*e*得到的二叉樹為：a eb dc 編寫遞歸算法，計算二叉樹中葉子結(jié)點的數(shù)目。按凹入表方式輸出該二叉樹。（2） 分析：此題要求用二叉鏈表作為存儲結(jié)構(gòu)，首先要定義二叉鏈表： typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;struct BiTNode *lchild, *rchild中l(wèi)child，r

2、child分別表示該結(jié)點的左右孩子。輸入時，按先序遍歷所得序列輸入，當某結(jié)點左子樹或右子樹為空時，輸入*號。輸出以凹入表的形式輸出。算法思想（1） 按照要求，這道題采用二叉鏈表來存儲矩陣的有關信息。存儲結(jié)構(gòu)定義為：typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;題中共有四個函數(shù)，包括主函數(shù)main()，創(chuàng)建二叉樹函數(shù)Status preorder(BiTree &T)，計算葉子結(jié)點函數(shù)Status calLeaf(BiTree &T)，輸出函數(shù)Status output(B

3、iTree &T,int)。其中，主函數(shù)首先調(diào)用preorder()創(chuàng)建二叉樹，然后調(diào)用函數(shù)calLeaf()。最后調(diào)用函數(shù)output()，輸出二叉樹。（2） 算法描述： main() BiTree T; int depth = 0; / 打印提示語 /輸入先序序列 preorder(T);/調(diào)用函數(shù)，先序創(chuàng)建二叉樹 calLeaf(T);/調(diào)用函數(shù)calLeaf()計算葉子結(jié)點數(shù)并打印 output(T,depth);/調(diào)用函數(shù)凹入輸出 system(pause); return 0; /創(chuàng)建 Status preorder(BiTree &T) char ch; scanf(%c,&ch

4、);/讀入數(shù)據(jù) if(ch = *) T=NULL; /讀到*號，表明該結(jié)點無孩子 else if ( ! (T=(BiTNode *)malloc(sizeof(BiTNode) )/動態(tài)申請 exit(OVERFLOW); T-data=ch;/將數(shù)據(jù)計入結(jié)點的數(shù)據(jù)域 /遞歸調(diào)用 /CreatBiTree /計算葉子結(jié)點數(shù) Status calLeaf(BiTree &T) if(空樹,無葉子) return ERROR; else if(只有左孩子或右孩子) return 1; / else 遞歸調(diào)用 Status output(BiTree &T,int depth) int i; i

5、f(當前結(jié)點不為空) depth +;/深度加1 /打印元素前空格 /打印數(shù)據(jù) if (左孩子) if (! output(T-lchild,depth) return ERROR;/遞歸 if (右孩子) if (! output(T-rchild,depth) ) return ERROR;/遞歸 return OK; else return ERROR; 源程序 已提交測試結(jié)果（1） 用戶使用說明：運行環(huán)境：visual C+ 6.0 Dev-c+程序啟動：Ctrl+F10操作步驟：按照提示輸入輸入：abc*d*e* 圖 1打印提示語，運行正常。按要求輸入先序遍歷序列，按該序列得到的二叉

6、樹為圖1所示二叉樹，葉子結(jié)點數(shù)為3，a在第一層，b，e在第二層，c，d在第三層。運行正常。心得體會（1）Status calLeaf(BiTree &T) if(!T) return ERROR; /空樹,無葉子 else if(!(calLeaf(T-lchild) num +; else if(!(calLeaf(T-lchild) num +;/遞歸調(diào)用 return num; 這種算法的思想是遞歸調(diào)用函數(shù)，當調(diào)用到?jīng)]有孩子的葉子結(jié)點時，num數(shù)加1。這樣依次計算，最終找到所有的葉子結(jié)點。但是，這種算法在調(diào)用時，不能統(tǒng)計右子樹上的葉子結(jié)點，導致出現(xiàn)下面的錯誤：所以改成了現(xiàn)在的算法：Sta

7、tus calLeaf(BiTree &T) if(!T) return ERROR; /空樹,無葉子 else if(!T-lchild & !T-rchild) return 1; /只有左孩子或右孩子 else return (calLeaf(T-lchild) + calLeaf(T-rchild);/遞歸調(diào)用 當T為空時，是空樹，葉子結(jié)點數(shù)為0；當左孩子或右孩子有一個不存在時，葉子結(jié)點數(shù)為1；當左右孩子都存在時，遞歸調(diào)用，知道找到所有的葉子結(jié)點，返回左右子樹上葉子結(jié)點數(shù)之和即為所求。（2） 心得體會：這道題用二叉鏈表存儲二叉樹，二叉鏈表由數(shù)據(jù)元素，左孩子指針和右孩子指針組成。用二叉鏈

8、表存儲二叉樹比較簡單，但是不足是不能存儲該節(jié)點的雙親，這種情況下，用線序序列建立二叉樹比較方便。雖然是用二叉鏈表這種較為簡單的方式存儲二叉樹，但對于初次接觸樹的概念的我還是一個很好的鍛煉機會，增強了對于二叉樹孩子與雙親的關系的理解，有助于更好的了解二叉樹的結(jié)構(gòu)。輸入數(shù)據(jù)后，循環(huán)調(diào)用創(chuàng)建函數(shù)，依次讀入數(shù)據(jù)并保存。創(chuàng)建二叉樹，計算葉子結(jié)點數(shù)和打印凹入表都要用到遞歸函數(shù)?？梢哉f，對樹和操作都主要是對遞歸函數(shù)的調(diào)用，復習了對二叉鏈表的應用。對于遞歸算法，現(xiàn)在的理解一直比較模糊，通過這道題在一定程度上增加了對遞歸函數(shù)的理解。選做 （1）用先序和中序遍歷建立二叉樹。用戶分別輸入一個二叉樹的先序遍歷序列和中

9、序遍歷序列，通過兩個遍歷序列建立二叉樹。 （2）解決方法：二叉樹存儲方式不變，但在程序中增加兩個字符數(shù)組pre和in分別用于存放兩個遍歷序列。用遞歸的算法解決問題。不難發(fā)現(xiàn)，pre中的第一個元素即為根節(jié)點對應的元素。而在in數(shù)組中，若第i個元素等于pre0，那么從第一個到第i-1個元素即為根節(jié)點的左子樹。按照這個方法，用遞歸的算法即可構(gòu)建一棵完整的二叉樹。（3） 算法描述： Status creatTree(BiTree &T,char pre,char in,int p,int q) int i = 0; /i表示根節(jié)點在中序中的位置 動態(tài)申請 T-data = prep; /根節(jié)點 i = q; while(ini != prep) i+; if(構(gòu)建左子樹)