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

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

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

4、遞歸遍歷二叉樹"）;printf（"nn4.中序遞歸遍歷二叉樹"）;printf（"nn5.后序遞歸遍歷二叉樹"）;printf（"nn6.層次遍歷二叉樹"）;printf（"nn7.計算二叉樹的高度"）;printf（"nn8.計算二叉樹中葉結(jié)點個數(shù)"）;printf（"nn9.交換二叉樹的左右子樹"）;printf（"nn10.打印二叉樹"）;printf（"nn0.結(jié)束程序運行"）;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.計算二叉樹的高度8.計算二叉樹中葉結(jié)點個數(shù)9.交換二叉樹的左右子樹10.打印二叉樹0.結(jié)束程序運行請輸入您的選擇(0,1,2,3,4,5,6,7,8,9,10)1請輸入二叉樹各結(jié)點的編號和對應的值(如1,a):1,a請繼續(xù)輸入二叉樹各結(jié)點的編號和對應

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

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

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

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

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

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