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

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

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

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

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

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

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

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

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

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

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

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