数据结构与算法实验报告
二叉树高度的求解
姓名:孙瑞霜
一、实验目的
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++,将五部分代码拷贝进去,点击运行,按照提示输入数据,最后得出结果,关闭程序。