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

二叉樹(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