2024年二叉樹實驗報告

二叉樹試驗匯報問題描述（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