2024年二叉樹實驗報告_第1頁
2024年二叉樹實驗報告_第2頁
2024年二叉樹實驗報告_第3頁
2024年二叉樹實驗報告_第4頁
2024年二叉樹實驗報告_第5頁
已閱讀5頁,還剩1頁未讀, 繼續(xù)免費閱讀

下載本文檔

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

文檔簡介

二叉樹試驗匯報問題描述(1)問題描述:①用先序遞歸過程建立二叉樹(存儲構(gòu)造:二叉鏈表)。輸入數(shù)據(jù)按先序遍歷所得序列輸入,當(dāng)某結(jié)點左子樹或右子樹為空時,輸入‘*’號,如輸入abc**d**e**得到的二叉樹為:aaebebddcc②編寫遞歸算法,計算二叉樹中葉子結(jié)點的數(shù)目。③按凹入表方式輸出該二叉樹。分析:①此題規(guī)定用二叉鏈表作為存儲構(gòu)造,首先要定義二叉鏈表:typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;structBiTNode*lchild,*rchild中l(wèi)child,rchild分別表達該結(jié)點的左右孩子。②輸入時,按先序遍歷所得序列輸入,當(dāng)某結(jié)點左子樹或右子樹為空時,輸入‘*’號。③輸出以凹入表的形式輸出。算法思想按照規(guī)定,這道題采用二叉鏈表來存儲矩陣的有關(guān)信息。存儲構(gòu)造定義為:typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;題中共有四個函數(shù),包括主函數(shù)main(),創(chuàng)立二叉樹函數(shù)Statuspreorder(BiTree&T),計算葉子結(jié)點函數(shù)StatuscalLeaf(BiTree&T),輸出函數(shù)Statusoutput(BiTree&T,int)。其中,主函數(shù)首先調(diào)用preorder()創(chuàng)立二叉樹,然後調(diào)用函數(shù)calLeaf()。最終調(diào)用函數(shù)output(),輸出二叉樹。算法描述:main(){BiTreeT;intdepth=0;//打印提醒語//輸入先序序列preorder(T);//調(diào)用函數(shù),先序創(chuàng)立二叉樹calLeaf(T);//調(diào)用函數(shù)calLeaf()計算葉子結(jié)點數(shù)并打印output(T,depth);//調(diào)用函數(shù)凹入輸出system("pause");return0;}//創(chuàng)立Statuspreorder(BiTree&T){charch;scanf("%c",&ch);//讀入數(shù)據(jù)if(ch=='*')T=NULL;//讀到*號,表明該結(jié)點無孩子else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))//動態(tài)申請exit(OVERFLOW);T->data=ch;//將數(shù)據(jù)計入結(jié)點的數(shù)據(jù)域//遞歸調(diào)用}}//CreatBiTree//計算葉子結(jié)點數(shù)StatuscalLeaf(BiTree&T){if(空樹,無葉子)returnERROR;elseif(只有左孩子或右孩子)return1;/else遞歸調(diào)用}Statusoutput(BiTree&T,intdepth){inti;if(目前結(jié)點不為空){depth++;//深度加1//打印元素前空格//打印數(shù)據(jù)if(左孩子)if(!output(T->lchild,depth))returnERROR;//遞歸if(右孩子)if(!output(T->rchild,depth))returnERROR;//遞歸returnOK;}elsereturnERROR;}源程序已提交測試成果顧客使用闡明:①運行環(huán)境:visualC++6.0Dev-c++②程序啟動:Ctrl+F10③操作環(huán)節(jié):按照提醒輸入④輸入:abc**d**e**圖1打印提醒語,運行正常。按規(guī)定輸入先序遍歷序列,按該序列得到的二叉樹為圖1所示二叉樹,葉子結(jié)點數(shù)為3,a在第一層,b,e在第二層,c,d在第三層。運行正常。心得體會(1)StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空樹,無葉子else{if(!(calLeaf(T->lchild)))num++;elseif(!(calLeaf(T->lchild)))num++;//遞歸調(diào)用}returnnum;}這種算法的思想是遞歸調(diào)用函數(shù),當(dāng)調(diào)用到?jīng)]有孩子的葉子結(jié)點時,num數(shù)加1。這樣依次計算,最終找到所有的葉子結(jié)點。不過,這種算法在調(diào)用時,不能記錄右子樹上的葉子結(jié)點,導(dǎo)致出現(xiàn)下面的錯誤:因此改成了目前的算法:StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空樹,無葉子elseif(!T->lchild&&!T->rchild)return1;//只有左孩子或右孩子elsereturn(calLeaf(T->lchild)+calLeaf(T->rchild));//遞歸調(diào)用}當(dāng)T為空時,是空樹,葉子結(jié)點數(shù)為0;當(dāng)左孩子或右孩子有一種不存在時,葉子結(jié)點數(shù)為1;當(dāng)左右孩子都存在時,遞歸調(diào)用,懂得找到所有的葉子結(jié)點,返回左右子樹上葉子結(jié)點數(shù)之和即為所求。心得體會:這道題用二叉鏈表存儲二叉樹,二叉鏈表由數(shù)據(jù)元素,左孩子指針和右孩子指針構(gòu)成。用二叉鏈表存儲二叉樹比較簡樸,不過局限性是不能存儲該節(jié)點的雙親,這種狀況下,用線序序列建立二叉樹比較以便。雖然是用二叉鏈表這種較為簡樸的方式存儲二叉樹,但對于初次接觸樹的概念的我還是一種很好的鍛煉機會,增強了對于二叉樹孩子與雙親的關(guān)系的理解,有助于更好的理解二叉樹的構(gòu)造。輸入數(shù)據(jù)後,循環(huán)調(diào)用創(chuàng)立函數(shù),依次讀入數(shù)據(jù)并保留。創(chuàng)立二叉樹,計算葉子結(jié)點數(shù)和打印凹入表都要用到遞歸函數(shù)。可以說,對樹和操作都重要是對遞歸函數(shù)的調(diào)用,復(fù)習(xí)了對二叉鏈表的應(yīng)用。對于遞歸算法,目前的理解一直比較模糊,通過這道題在一定程度上增長了對遞歸函數(shù)的理解。選做(1)用先序和中序遍歷建立二叉樹。顧客分別輸入一種二叉樹的先序遍歷序列和中序遍歷序列,通過兩個遍歷序列建立二叉樹。(2)處理措施:二叉樹存儲方式不變,但在程序中增長兩個字符數(shù)組pre[]和in[]分別用于寄存兩個遍歷序列。用遞歸的算法處理問題。不難發(fā)現(xiàn),pre[]中的第一種元素即為根節(jié)點對應(yīng)的元素。而在in[]數(shù)組中,若第i個元素等于pre[0],那么從第一種到第i-1個元素即為根節(jié)點的左子樹。按照這個措施,用遞歸的算法即可構(gòu)建一棵完整的二叉樹。算法描述:StatuscreatTree(BiTree&T,charpre[],charin[],intp,intq){inti=0;//i表達根節(jié)點在中序中的位置動態(tài)申請T->data=pre[p];//根節(jié)點i=q;while(in[i]!=pre[p])i++;if(構(gòu)建左子樹){//確定左子樹的先序序列指針creatTre

溫馨提示

  • 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)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論