數據結構與算法實驗報告之二叉樹高度的求解
- 2020 年 5 月 24 日
- 筆記
數據結構與算法實驗報告
二叉樹高度的求解
姓名：孫瑞霜
一、實驗目的
1、熟練掌握學習的每種結構及其相應算法；
2、理論聯繫實際，會對現實問題建模並設計相應算法。
3、優化算法，使得算法效率適當提高
二、實驗要求：
1． 認真閱讀和掌握教材上和本實驗相關的內容和算法；
2． 上機將各種相關算法實現；
3． 實現上面實驗目的要求的功能，並能進行簡單的驗證。
三、實驗內容
認真學習 學習通->數據結構->資料->數據結構實驗指導書–陳越版，從第二章進階實驗1~10中任選一個來實現，編寫程序，輸入給定的數據，能得到給定的輸出。總結算法思想、畫出流程圖，並思考程序有無改進空間，如何改進。
實驗內容：還原二叉樹。（給定一棵二叉樹的先序遍歷序列和中序遍歷序列，要求計算該二叉樹的高度。）
三、算法描述
（採用自然語言描述）
二叉樹高度的求解：先分析二叉樹的高度和它的左、右子樹深度之間的關係。從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中「訪問結點」的操作為：求得左、右子樹深度的最大值，然後加 1 。
四、詳細設計
（畫出程序流程圖）
五、程序代碼
（給出必要注釋）
#include<stdio.h>
#include<stdlib.h>
typedef struct TNode * BinTree;
struct TNode{
int data;
BinTree Left;
BinTree Right;
};
//typedef struct TNode BinTree;
BinTree tree (char f[],char m[],int n)
{ BinTree BT;
if(n==0)
{
return NULL;
}
int i;
char r;
r=f[0];
BT=(BinTree )malloc(sizeof(struct TNode)); //空間
BT->data=r;
for(i=0;i<n;i++)
if(m[i]==r)
break;
BT->Left=tree(f+1,m,i);
BT->Right=tree(f+i+1,m+i+1,n-i-1);
return BT;
}
int GetHeight(BinTree BT)
{
int hl,hr;
if(!BT)
return 0;
// 計算左子樹的高度和右子樹的高度
hl=GetHeight(BT->Left);
hr=GetHeight(BT->Right);
if(hl>hr)
return hl+1; // 返回二者較大者加1
return hr+1;
}
int main()
{
BinTree BT; //=(BinTree)malloc(sizeof(struct TNode));
int n;
char f[51]={0},m[51]={0};
scanf(“%d”,&n);
scanf(“%s”,f);
scanf(“%s”,m);
BT=tree(f,m,n);
printf(“%d”,GetHeight(BT));
}
六、測試和結果
（給出測試用例以及測試結果）
輸入樣例:
9
ABDFGHIEC
FDHGIBEAC
輸出樣例:
5
七、用戶手冊
（告訴用戶如何使用程序）
打開Dev c++,將五部分代碼拷貝進去，點擊運行，按照提示輸入數據，最後得出結果，關閉程序。
