樹和二叉樹實(shí)驗(yàn)報(bào)告

1、樹和二叉樹一、實(shí)驗(yàn)?zāi)康?. 掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及適用范圍。2. 掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。二、實(shí)驗(yàn)要求1. 認(rèn)真閱讀和掌握本實(shí)驗(yàn)的程序。2. 上機(jī)運(yùn)行本程序。3. 保存和打印出程序的運(yùn)行結(jié)果，并結(jié)合程序進(jìn)行分析。4. 按照二叉樹的操作需要，重新改寫主程序并運(yùn)行，打印出文件清單和運(yùn)行結(jié)果。三、實(shí)驗(yàn)內(nèi)容1. 輸入字符序列，建立二叉鏈表。2. 按先序、中序和后序遍歷二叉樹（遞歸算法）。3. 按某種形式輸出整棵二叉樹。4. 求二叉樹的高度。5. 求二叉樹的葉節(jié)點(diǎn)個(gè)數(shù)。6. 交換二叉樹的左右子樹。7. 借助隊(duì)列實(shí)現(xiàn)二叉樹的層次遍歷。8. 在主函數(shù)中設(shè)計(jì)一個(gè)簡單

2、的菜單，分別調(diào)試上述算法。為了實(shí)現(xiàn)對二叉樹的有關(guān)操作，首先要在計(jì)算機(jī)中建立所需的二叉樹。建立二叉樹有各種不同的方法。一種方法是利用二叉樹的性質(zhì)5來建立二叉樹，輸入數(shù)據(jù)時(shí)要將節(jié)點(diǎn)的序號（按滿二叉樹編號）和數(shù)據(jù)同時(shí)給出：（序號，數(shù)據(jù)元素0）。另一種方法是主教材中介紹的方法，這是一個(gè)遞歸方法，與先序遍歷有點(diǎn)相似。數(shù)據(jù)的組織是先序的順序，但是另有特點(diǎn)，當(dāng)某結(jié)點(diǎn)的某孩子為空時(shí)以字符“#”來充當(dāng)，也要輸入。若當(dāng)前數(shù)據(jù)不為“#”，則申請一個(gè)結(jié)點(diǎn)存入當(dāng)前數(shù)據(jù)。遞歸調(diào)用建立函數(shù)，建立當(dāng)前結(jié)點(diǎn)的左右子樹。四、解題思路1、先序遍歷：O訪問根結(jié)點(diǎn)，G2先序遍歷左子樹，03先序遍歷右子樹2、中序遍歷：O中序遍歷左子樹，

3、。2訪問根結(jié)點(diǎn)，o中序遍歷右子樹3、后序遍歷：。后序遍歷左子樹，。2后序遍歷右子樹，。3訪問根結(jié)點(diǎn)4、層次遍歷算法：采用一個(gè)隊(duì)列q,先將二叉樹根結(jié)點(diǎn)入隊(duì)列，然后退隊(duì)列，輸出該結(jié)點(diǎn)；若它有左子樹，便將左子樹根結(jié)點(diǎn)入隊(duì)列；若它有右子樹，便將右子樹根結(jié)點(diǎn)入隊(duì)列，直到隊(duì)列空為止。因?yàn)殛?duì)列的特點(diǎn)是先進(jìn)后出，所以能夠達(dá)到按層次遍歷二叉樹的目的。五、程序清單#include<>#include<>#defineM100typedefcharEtype;立二叉樹方法1"）;printf（"nn2.建立二叉樹方法2"）;printf（"nn3.先序

4、遞歸遍歷二叉樹"）;printf（"nn4.中序遞歸遍歷二叉樹"）;printf（"nn5.后序遞歸遍歷二叉樹"）;printf（"nn6.層次遍歷二叉樹"）;printf（"nn7.計(jì)算二叉樹的高度"）;printf（"nn8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)"）;printf（"nn9.交換二叉樹的左右子樹"）;printf（"nn10.打印二叉樹"）;printf（"nn0.結(jié)束程序運(yùn)行"）;printf（"n=&quo

5、t;）;printf（"n請輸入您的選擇（0,1,2,3,4,5,6,7,8,9,10）"）;scanf（"%d",&k）;）;break;switch（k）case1:t=creat_bt1（2.建立二叉樹方法23.先序遞歸遍歷二叉樹4.中序遞歸遍歷二叉樹5.后序遞歸遍歷二叉樹6.層次遍歷二叉樹7.計(jì)算二叉樹的高度8.計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)1請輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值(如1,a):1,a請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)

6、的值：2,b請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：3,c請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：4,d請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：6,e請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：7,f請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：9,g請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：13,h請繼續(xù)輸入二叉樹各結(jié)點(diǎn)的編號和對應(yīng)的值：0,#=生菜單=")；1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束

7、程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)3先序遍歷二叉樹：abdgcehf=生菜單=)1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)4中序遍歷二叉樹：dgbaehcf=生菜單=)1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷

8、二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)5后序遍歷二叉樹：gdbhefca=生菜單=");1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)6層次遍歷二叉樹：97989904=生菜單="

9、;);1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)7二叉樹的高度為：4=生菜單=")；1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程

10、序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)8二叉樹的葉子結(jié)點(diǎn)數(shù)為：3二叉樹的葉結(jié)點(diǎn)為：ghf=生菜單=")；1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)9交換二叉樹的左右子樹：dgb=生菜單=");1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹

11、5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)10逆時(shí)針旋轉(zhuǎn)90度輸出的二叉樹：dgbaehcf=生菜單=)1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)2請輸入二叉樹各結(jié)點(diǎn)值：abd#g#ce#h#f#=生菜單=");1 .建立二叉樹方法12 .建立二叉樹方法23 .先序遞歸遍歷二叉樹4 .中序遞歸遍歷二叉樹5 .后序遞歸遍歷二叉樹6 .層次遍歷二叉樹7 .計(jì)算二叉樹的高度8 .計(jì)算二叉樹中葉結(jié)點(diǎn)個(gè)數(shù)9 .交換二叉樹的左右子樹10 .打印二叉樹0.結(jié)束程序運(yùn)行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)