二叉樹(shù)實(shí)驗(yàn)報(bào)告_第1頁(yè)
二叉樹(shù)實(shí)驗(yàn)報(bào)告_第2頁(yè)
二叉樹(shù)實(shí)驗(yàn)報(bào)告_第3頁(yè)
二叉樹(shù)實(shí)驗(yàn)報(bào)告_第4頁(yè)
二叉樹(shù)實(shí)驗(yàn)報(bào)告_第5頁(yè)
已閱讀5頁(yè),還剩1頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

1、二叉樹(shù)實(shí)驗(yàn)報(bào)告問(wèn)題描述(1)問(wèn)題描述:用先序遞歸過(guò)程建立二叉樹(shù) (存儲(chǔ)結(jié)構(gòu):二叉鏈表)。輸入數(shù)據(jù)按先序遍歷所得序列輸入,當(dāng)某結(jié)點(diǎn)左子樹(shù)或右子樹(shù)為空時(shí),輸入*號(hào),如輸入abc*d*e*得到的二叉樹(shù)為:a eb dc 編寫遞歸算法,計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。按凹入表方式輸出該二叉樹(shù)。(2) 分析:此題要求用二叉鏈表作為存儲(chǔ)結(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é)點(diǎn)的左右孩子。輸入時(shí),按先序遍歷所得序列輸入,當(dāng)某結(jié)點(diǎn)左子樹(shù)或右子樹(shù)為空時(shí),輸入*號(hào)。輸出以凹入表的形式輸出。算法思想(1) 按照要求,這道題采用二叉鏈表來(lái)存儲(chǔ)矩陣的有關(guān)信息。存儲(chǔ)結(jié)構(gòu)定義為:typedef struct BiTNode char data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree;題中共有四個(gè)函數(shù),包括主函數(shù)main(),創(chuàng)建二叉樹(shù)函數(shù)Status preorder(BiTree &T),計(jì)算葉子結(jié)點(diǎn)函數(shù)Status calLeaf(BiTree &T),輸出函數(shù)Status output(B

3、iTree &T,int)。其中,主函數(shù)首先調(diào)用preorder()創(chuàng)建二叉樹(shù),然后調(diào)用函數(shù)calLeaf()。最后調(diào)用函數(shù)output(),輸出二叉樹(shù)。(2) 算法描述: main() BiTree T; int depth = 0; / 打印提示語(yǔ) /輸入先序序列 preorder(T);/調(diào)用函數(shù),先序創(chuàng)建二叉樹(shù) calLeaf(T);/調(diào)用函數(shù)calLeaf()計(jì)算葉子結(jié)點(diǎn)數(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; /讀到*號(hào),表明該結(jié)點(diǎn)無(wú)孩子 else if ( ! (T=(BiTNode *)malloc(sizeof(BiTNode) )/動(dòng)態(tài)申請(qǐng) exit(OVERFLOW); T-data=ch;/將數(shù)據(jù)計(jì)入結(jié)點(diǎn)的數(shù)據(jù)域 /遞歸調(diào)用 /CreatBiTree /計(jì)算葉子結(jié)點(diǎn)數(shù) Status calLeaf(BiTree &T) if(空樹(shù),無(wú)葉子) return ERROR; else if(只有左孩子或右孩子) return 1; / else 遞歸調(diào)用 Status output(BiTree &T,int depth) int i; i

5、f(當(dāng)前結(jié)點(diǎn)不為空) 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; 源程序 已提交測(cè)試結(jié)果(1) 用戶使用說(shuō)明:運(yùn)行環(huán)境:visual C+ 6.0 Dev-c+程序啟動(dòng):Ctrl+F10操作步驟:按照提示輸入輸入:abc*d*e* 圖 1打印提示語(yǔ),運(yùn)行正常。按要求輸入先序遍歷序列,按該序列得到的二叉

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

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

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

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

溫馨提示

  • 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論