




版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
二叉樹(shù)試驗(yàn)匯報(bào)問(wèn)題描述(1)問(wèn)題描述:①用先序遞歸過(guò)程建立二叉樹(shù)(存儲(chǔ)構(gòu)造:二叉鏈表)。輸入數(shù)據(jù)按先序遍歷所得序列輸入,當(dāng)某結(jié)點(diǎn)左子樹(shù)或右子樹(shù)為空時(shí),輸入‘*’號(hào),如輸入abc**d**e**得到的二叉樹(shù)為:aaebebddcc②編寫遞歸算法,計(jì)算二叉樹(shù)中葉子結(jié)點(diǎn)的數(shù)目。③按凹入表方式輸出該二叉樹(shù)。分析:①此題規(guī)定用二叉鏈表作為存儲(chǔ)構(gòu)造,首先要定義二叉鏈表:typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;structBiTNode*lchild,*rchild中l(wèi)child,rchild分別表達(dá)該結(jié)點(diǎn)的左右孩子。②輸入時(shí),按先序遍歷所得序列輸入,當(dāng)某結(jié)點(diǎn)左子樹(shù)或右子樹(shù)為空時(shí),輸入‘*’號(hào)。③輸出以凹入表的形式輸出。算法思想按照規(guī)定,這道題采用二叉鏈表來(lái)存儲(chǔ)矩陣的有關(guān)信息。存儲(chǔ)構(gòu)造定義為:typedefstructBiTNode{chardata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;題中共有四個(gè)函數(shù),包括主函數(shù)main(),創(chuàng)立二叉樹(shù)函數(shù)Statuspreorder(BiTree&T),計(jì)算葉子結(jié)點(diǎn)函數(shù)StatuscalLeaf(BiTree&T),輸出函數(shù)Statusoutput(BiTree&T,int)。其中,主函數(shù)首先調(diào)用preorder()創(chuàng)立二叉樹(shù),然後調(diào)用函數(shù)calLeaf()。最終調(diào)用函數(shù)output(),輸出二叉樹(shù)。算法描述:main(){BiTreeT;intdepth=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");return0;}//創(chuàng)立Statuspreorder(BiTree&T){charch;scanf("%c",&ch);//讀入數(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ù)StatuscalLeaf(BiTree&T){if(空樹(shù),無(wú)葉子)returnERROR;elseif(只有左孩子或右孩子)return1;/else遞歸調(diào)用}Statusoutput(BiTree&T,intdepth){inti;if(目前結(jié)點(diǎn)不為空){depth++;//深度加1//打印元素前空格//打印數(shù)據(jù)if(左孩子)if(!output(T->lchild,depth))returnERROR;//遞歸if(右孩子)if(!output(T->rchild,depth))returnERROR;//遞歸returnOK;}elsereturnERROR;}源程序已提交測(cè)試成果顧客使用闡明:①運(yùn)行環(huán)境:visualC++6.0Dev-c++②程序啟動(dòng):Ctrl+F10③操作環(huán)節(jié):按照提醒輸入④輸入:abc**d**e**圖1打印提醒語(yǔ),運(yùn)行正常。按規(guī)定輸入先序遍歷序列,按該序列得到的二叉樹(shù)為圖1所示二叉樹(shù),葉子結(jié)點(diǎn)數(shù)為3,a在第一層,b,e在第二層,c,d在第三層。運(yùn)行正常。心得體會(huì)(1)StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空樹(shù),無(wú)葉子else{if(!(calLeaf(T->lchild)))num++;elseif(!(calLeaf(T->lchild)))num++;//遞歸調(diào)用}returnnum;}這種算法的思想是遞歸調(diào)用函數(shù),當(dāng)調(diào)用到?jīng)]有孩子的葉子結(jié)點(diǎn)時(shí),num數(shù)加1。這樣依次計(jì)算,最終找到所有的葉子結(jié)點(diǎn)。不過(guò),這種算法在調(diào)用時(shí),不能記錄右子樹(shù)上的葉子結(jié)點(diǎn),導(dǎo)致出現(xiàn)下面的錯(cuò)誤:因此改成了目前的算法:StatuscalLeaf(BiTree&T){if(!T)returnERROR;//空樹(shù),無(wú)葉子elseif(!T->lchild&&!T->rchild)return1;//只有左孩子或右孩子elsereturn(calLeaf(T->lchild)+calLeaf(T->rchild));//遞歸調(diào)用}當(dāng)T為空時(shí),是空樹(shù),葉子結(jié)點(diǎn)數(shù)為0;當(dāng)左孩子或右孩子有一種不存在時(shí),葉子結(jié)點(diǎn)數(shù)為1;當(dāng)左右孩子都存在時(shí),遞歸調(diào)用,懂得找到所有的葉子結(jié)點(diǎn),返回左右子樹(shù)上葉子結(jié)點(diǎn)數(shù)之和即為所求。心得體會(huì):這道題用二叉鏈表存儲(chǔ)二叉樹(shù),二叉鏈表由數(shù)據(jù)元素,左孩子指針和右孩子指針構(gòu)成。用二叉鏈表存儲(chǔ)二叉樹(shù)比較簡(jiǎn)樸,不過(guò)局限性是不能存儲(chǔ)該節(jié)點(diǎn)的雙親,這種狀況下,用線序序列建立二叉樹(shù)比較以便。雖然是用二叉鏈表這種較為簡(jiǎn)樸的方式存儲(chǔ)二叉樹(shù),但對(duì)于初次接觸樹(shù)的概念的我還是一種很好的鍛煉機(jī)會(huì),增強(qiáng)了對(duì)于二叉樹(shù)孩子與雙親的關(guān)系的理解,有助于更好的理解二叉樹(shù)的構(gòu)造。輸入數(shù)據(jù)後,循環(huán)調(diào)用創(chuàng)立函數(shù),依次讀入數(shù)據(jù)并保留。創(chuàng)立二叉樹(shù),計(jì)算葉子結(jié)點(diǎn)數(shù)和打印凹入表都要用到遞歸函數(shù)。可以說(shuō),對(duì)樹(shù)和操作都重要是對(duì)遞歸函數(shù)的調(diào)用,復(fù)習(xí)了對(duì)二叉鏈表的應(yīng)用。對(duì)于遞歸算法,目前的理解一直比較模糊,通過(guò)這道題在一定程度上增長(zhǎng)了對(duì)遞歸函數(shù)的理解。選做(1)用先序和中序遍歷建立二叉樹(shù)。顧客分別輸入一種二叉樹(shù)的先序遍歷序列和中序遍歷序列,通過(guò)兩個(gè)遍歷序列建立二叉樹(shù)。(2)處理措施:二叉樹(shù)存儲(chǔ)方式不變,但在程序中增長(zhǎng)兩個(gè)字符數(shù)組pre[]和in[]分別用于寄存兩個(gè)遍歷序列。用遞歸的算法處理問(wèn)題。不難發(fā)現(xiàn),pre[]中的第一種元素即為根節(jié)點(diǎn)對(duì)應(yīng)的元素。而在in[]數(shù)組中,若第i個(gè)元素等于pre[0],那么從第一種到第i-1個(gè)元素即為根節(jié)點(diǎn)的左子樹(shù)。按照這個(gè)措施,用遞歸的算法即可構(gòu)建一棵完整的二叉樹(shù)。算法描述:StatuscreatTree(BiTree&T,charpre[],charin[],intp,intq){inti=0;//i表達(dá)根節(jié)點(diǎn)在中序中的位置動(dòng)態(tài)申請(qǐng)T->data=pre[p];//根節(jié)點(diǎn)i=q;while(in[i]!=pre[p])i++;if(構(gòu)建左子樹(shù)){//確定左子樹(shù)的先序序列指針creatTre
溫馨提示
- 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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 煤礦機(jī)電設(shè)備強(qiáng)制維護(hù)保養(yǎng)規(guī)定 (一)
- 南京市聯(lián)合體中考語(yǔ)文一模試題及答案
- 臨港有色金屬有限公司燒結(jié)設(shè)備維護(hù)規(guī)程
- 老年自理課件
- 黨紀(jì)黨規(guī)教育
- 礦山開(kāi)采與環(huán)境保護(hù)責(zé)任書樣本
- 出渣車勞務(wù)分包與建筑垃圾資源化利用合同
- 城市共享單車借用服務(wù)合同協(xié)議書
- 老人和兒童課件
- 美術(shù)蝗蟲(chóng)介紹課件
- 全國(guó)工會(huì)財(cái)務(wù)知識(shí)競(jìng)賽題庫(kù)及答案
- 物聯(lián)網(wǎng)平臺(tái)介紹
- 《三國(guó)的世界》解說(shuō)詞 第一集 01
- 計(jì)算機(jī)組成原理考點(diǎn)整理
- 廣東省深圳市龍華區(qū)2022-2023學(xué)年五年級(jí)下學(xué)期期末數(shù)學(xué)試卷
- 黃石市陽(yáng)新縣法院系統(tǒng)書記員招聘考試真題
- 湖北省工傷職工停工留薪期分類目錄
- 教科版六下科學(xué)全冊(cè)課時(shí)練(含答案)
- 2023年主任醫(yī)師(正高)-中醫(yī)內(nèi)科學(xué)(正高)考試歷年真題精華集選附答案
- 人教版高中英語(yǔ)必修第二冊(cè)《Unit2Wildlifeprotection》教案及教學(xué)反思
- 內(nèi)蒙古匯能煤電集團(tuán)有限公司長(zhǎng)灘露天煤礦礦山地質(zhì)環(huán)境保護(hù)與土地復(fù)墾方案
評(píng)論
0/150
提交評(píng)論