1、實驗四二叉樹的操作題目：對于給定的一二義樹，實現各種約定的遍歷。一、實驗目的：1掌握二義樹的定義和存儲表示，學會建立一棵特定二義樹的方法；2掌握二義樹的遍歷算法先序、中序、后序遍歷算法的思想，并學會遍歷算法的遞歸實現和非遞歸實現。二、實驗內容：構造二義樹，再實現二義樹的先序、中序、后序遍歷，最后統計二義樹的深度。三、實驗步驟：1. （一）需求分析二義樹的建立首先要建立一個二義鏈表的結構體，包含根節點和左右子樹。因為樹的每一個左右子樹乂是一顆二義樹，所以用遞歸的方法來建立其左右子樹。二義樹的遍歷是一種把二義樹的每一個節點訪問并輸出的過程，遍歷時根結點與左右孩子的輸出順序構成了不同的遍歷方法，這個

2、過程需要按照不同的遍歷的方法，先輸出根結點還是先輸出左右孩子，可以用選擇語句來實現。2. 程序的執行命令為：1構造結點類型，然后創建二義樹。2根據提小，從鍵盤輸入各個結點。3通過選擇一種方式先序、中序或者后序遍歷。4輸出結果，結束。1. （二）概要設計二義樹的二義鏈表結點存儲類型定義typedefstructNode（DataTypedata;structNode*LChild;structNode*RChild;2. BitNode,*BitTree;建立如下列圖所示二義樹：voidCreatBiTree（BitTree*bt）用擴展先序遍歷序列創建二義樹，如果是當前樹根置為空，否則申請一個

3、新節點。3. 本程序包含四個模塊1) 主程序模塊:2) 先序遍歷模塊3) 中序遍歷模塊后序遍歷模塊三詳細設計/=構造二又樹=voidCreatBiTree(BitTree*bt)/用擴展先序遍歷序列創建二叉樹，如果是當前樹根置為空,否則申請一個新節點/(charch;ch=getchar();if(ch='.')*bt=NULL;else(*bt=(BitTree)malloc(sizeof(BitNode);/申請一段關于該節點類型的存儲空間(*bt)->data=ch;/生成根結點CreatBiTree(&(*bt)->LChild);/構造左子樹Cre

4、atBiTree(&(*bt)->RChild);/構造右子樹2.編程實現以上二叉樹的前序、中序和后序遍歷操作，輸出遍歷序列1先序遍歷二叉樹的遞歸算法如下：voidPreOrder(BitTreeroot)(if(root!=NULL)(Visit(root->data);PreOrder(root->LChild);/遞歸調用核心PreOrder(root->RChild);2中序遍歷二叉樹的遞歸算法如下：voidInOrder(BitTreeroot)if(root!=NULL)(InOrder(root->LChild);Visit(root->

5、;data);InOrder(root->RChild);3后序遍歷二叉樹的遞歸算法如下:voidPostOrder(BitTreeroot)(if(root!=NULL)(PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);4計算二義樹的深度算法如下：intPostTreeDepth(BitTreebt)求二叉樹的深度(inthl,hr,max;if(bt!=NULL)(hl=PostTreeDepth(bt->LChild);求左子樹的深度hr=PostTreeDepth(bt-&

6、gt;RChild);求右子樹的深度max=hl>hr?hl:hr;得到左、右子樹深度較大者return(max+1);返回樹的深度elsereturn(0);如果是空樹，則返回01. 四、調試分析及測試結果進入演示程序后的顯示主界面：請輸入二義樹中的元素；先序、中序和后序遍歷分別輸出結果。以擴展先序遍歷序列輸入，其中.代表空子樹：ABC.DE.G.F先序遍歷序列為：ABCDEGF中序遍歷序列為：CBEGDFA后序遍歷序列為：CGEFDBA此二義樹的深度為：5.代表空子樹，顯示1輸入二義樹中的元素以擴展先序遍歷序列輸入，其中截圖為：2輸出結果，顯示界面為:'C:PrcgramFi

7、les(xSSJMicrosoftVisualStudioMyProiectsXeeDebLig?e.eKe*圖二4. 調試分析：本程序通過分別調用先序遍歷、中序遍歷以及后序遍歷函數對二義樹中的元素進行遍歷，整個程序基本滿足實驗要求，但是在一些細節問題上面還是存在缺陷，比方大小寫字母不同也會導致程序無法運行，這就需要我們在處理問題上認真細致，還有就是程序并不是很完善，總之，我會在今后更加努力，是程序更完美。六、實驗總結1. 二義樹對于進行表達式的前綴，中綴和后綴的表示有明顯的優勢，既方便，乂容易理解。其先序，中序和后序分別對應這表達式的前綴，中綴和后綴。2. 在建樹與進行樹的遍歷的時候一定要理

8、解其建樹與遍歷的整個過程。不然就會連為什么這樣做都不知道。在遍歷樹的時候最常用到的就是棧的結構了非遞歸。3. 本次實驗讓我更加了解了哈夫曼樹的構造和生成方法，以及如何用順序結構來存儲哈夫曼樹及構樹過程的信息，如何進行編碼、譯碼。也感知到模塊程序設計在大程序設計使用中的普遍性，該實驗是最好的證明，通過模塊程序設計，能使程序可讀可寫性明顯加強。通過本次實驗，使我初步掌握了二義樹的結構特性以及各種存儲的結構的特點和適用范圍，掌握了哈夫曼樹的定義和思想，初步掌握了用凹入法顯示樹。不過程序仍有樹的顯示不夠完善的缺點，在今后的學習中，我會不斷學習，在學習中注意改變。附錄源程序活單：#include<

9、stdio.h>#include<stdlib.h>#include<malloc.h>#include<conio.h>typedefintDataType;typedefstructNode/創建結點類型結構體DataTypedata;structNode*LChild;structNode*RChild;BitNode,*BitTree;voidCreatBiTree(BitTree*bt)用擴展先序遍歷序列創建二叉樹，如果是當前樹根置為空,否則申請一個新節點/charch;ch=getchar();if(ch='.')*bt=N

10、ULL;else*bt=(BitTree)malloc(sizeof(BitNode);(*bt)->data=ch;CreatBiTree(&(*bt)->LChild);CreatBiTree(&(*bt)->RChild);voidvisit(charch)/訪問根節點printf("%c",ch);voidPreOrder(BitTreeroot)/先序遍歷二叉樹的遞歸算法if(root!=NULL)Visit(root->data);PreOrder(root->LChild);PreOrder(root->RC

11、hild);voidInOrder(BitTreeroot)中序遍歷二叉樹的遞歸算法if(root!=NULL)InOrder(root->LChild);Visit(root->data);InOrder(root->RChild);voidPostOrder(BitTreeroot)(if(root!=NULL)(PostOrder(root->LChild);PostOrder(root->RChild);Visit(root->data);intPostTreeDepth(BitTreebt)(inthl,hr,max;if(bt!=NULL)(hl=PostTreeDepth(bt->LChild);hr=PostTreeDepth(bt->RChild);max=hl>hr?hl:hr;return(max+1);elsereturn(0);voidmain()后序遍歷求二叉樹的遞歸算法求二叉樹的深度求左子樹的深度求右子樹的深度得到左、右子樹深度較大者返回樹的深度如果是空樹，則返回0(BitTreeT;inth;intlayer;inttreeleaf;layer=0;printf("請輸入二叉樹中的元素(以擴展先序遍歷序列輸入,其中.代表空子樹):n");CreatBiTree(&T)