数据结构与算法实验报告

二叉树高度的求解

      姓名:孙瑞霜 

 

一、实验目的

1、熟练掌握学习的每种结构及其相应算法;

2、理论联系实际,会对现实问题建模并设计相应算法。

3、优化算法,使得算法效率适当提高

二、实验要求

1. 认真阅读和掌握教材上和本实验相关内容和算法;

2. 上机将各种相关算法实现;

3实现上面实验目的要求的功能,并能进行简单的验证

、实验内容

认真学习 学习通->数据结构->资料->数据结构实验指导书--陈越版,从第二章进阶实验1~10中任选一个来实现,编写程序,输入给定的数据,能得到给定的输出。总结算法思想、画出流程图,并思考程序有无改进空间,如何改进。

实验内容:还原二叉树。(给定一棵二叉树的先序遍历序列和中序遍历序列,要求计算该二叉树的高度。)

 

三、算法描述

(采用自然语言描述)

二叉树高度的求解:先分析二叉树的高度和它的左、右子树深度之间的关系。从二叉树深度的定义可知,二叉树的深度应为其左、右子树深度的最大值加1。由此,需先分别求得左、右子树的深度,算法中“访问结点”的操作为:求得左、右子树深度的最大值,然后加 1

 

四、详细设计

(画出程序流程图)

 数据结构与算法实验报告之二叉树高度的求解-LMLPHP 

五、程序代码

(给出必要注释)

#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

数据结构与算法实验报告之二叉树高度的求解-LMLPHP 

七、用户手册

(告诉用户如何使用程序)

打开Dev c++,将五部分代码拷贝进去,点击运行,按照提示输入数据,最后得出结果,关闭程序。

05-24 19:52