




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
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)
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 藥品分成協(xié)議書
- 茶館合伙協(xié)議書
- 簽訂貿(mào)易協(xié)議書
- 夫妻吵架解決好協(xié)議書
- 王楠離婚協(xié)議書
- 聯(lián)合應(yīng)急協(xié)議書
- 服裝店員工聘用協(xié)議書
- 在職研究生定向協(xié)議書
- 房產(chǎn)代理人合同協(xié)議書
- 村環(huán)境衛(wèi)生保潔協(xié)議書
- 液化天然氣汽車加氣站技術(shù)規(guī)范
- (正式版)SHT 3158-2024 石油化工管殼式余熱鍋爐
- 加油站百日攻堅(jiān)行動實(shí)施方案
- 供電企業(yè)輿情的預(yù)防及處置
- GB/T 41666.4-2024地下無壓排水管網(wǎng)非開挖修復(fù)用塑料管道系統(tǒng)第4部分:原位固化內(nèi)襯法
- 4、《通向金融王國的自由之路》
- 大學(xué)生職業(yè)素養(yǎng)(高職)全套教學(xué)課件
- 涉密內(nèi)網(wǎng)分級保護(hù)設(shè)計(jì)方案
- 木地板培訓(xùn)資料大全
- 康養(yǎng)旅游概念及市場現(xiàn)狀分析
- 99版-干部履歷表-A4打印
評論
0/150
提交評論