当前位置：文档之家 › 实验五 二叉树的基本操作

实验五 二叉树的基本操作

  • 格式：doc
  • 大小：43.00 KB
  • 文档页数：4

实验五 还原二叉树

实验目的：

1. 熟练掌握二叉树存储结构。

2. 熟练掌握二叉树的遍历及应用。

实验内容：

给定一棵二叉树的先序遍历序列和中序遍历序列，要求计算该二叉树的高度。

实验要求：

1. 输入说明：输入第1行给出正整数N（N≤50），为树中结点总数。下面2行先后给出先序和中序遍历序列，均是长度为N的不包含重复英文字母（区别大小写）的字符串。

2. 输出说明：输出为一个整数，即该二叉树的高度。

测试用例：

序号 输入 输出 说明

1 9

ABDFGHIEC

FDHGIBEAC 5 一般情况测试

2 15

cdefghi jklmnxyz

cdefghi jklmnxyz 15 完全右斜

3 7

Abcdefg

gfedcbA 7 完全左斜

4 1

a

a 1 边界测试：最小N

5 50 略 边界测试：最大N 50 个随机数据

实验分析：

1. 问题分析

本题需要解决两个子问题。

通过输入给定的先序遍历和中序遍历两个序列构建对应二叉树。由于我们知道先序遍历序列的第1个结点必然是根结点，可以在中序遍历序列中找到这个根结点的位置，于是就知道在中序遍历序列中，根结点左边的所有结点一定属于左子树，右边的所有结点一定属于右子树。根据这个判断，可以从中序遍历序列中知道左、右子树分别有L和R个结点，它们必然对应存储在先序遍历序列中第2~（L+1）个结点以及最后的R个结点。于是可以对左、右子树递归地解决这个问题，直到生成整个二叉树。

求二叉树的高度。如果已经知道左、右子树的高度，那么树的高度就是左、右子树中比较高的那个高度加1。这是一个可以用二叉树后序遍历解决的问题，在遍历过程中，我们将“访问结点”定义为“求左、右子树高度的较大值并加1”。

2. 实现要点

树形结构用教材中介绍的链表结构存储，结点结构体存储该结点的字符以及左右子树的指针。在构建二叉树和求二叉树高度的过程中，须注意递归终止的条件。

实验参考代码：

#include

#include

#define MAXN 50

typedef struct TreeNode *BinTree;

struct TreeNode {

char Data;

BinTree Left;

BinTree Right;

};

BinTree CreateBinTree( char *Pre, char *In, int Len )

{ /* 根据先序遍历序列和中序遍历序列构造二叉树 */

BinTree T;

int i;

if ( !Len ) return NULL; /* 递归终止 */

/* 建立当前根结点 */

T = (BinTree)malloc(sizeof(struct TreeNode));

T->Data = Pre[0];

for (i=0; i

if (Pre[0]==In[i]) break;

/* 递归生成左右子树 */

T->Left = CreateBinTree(Pre+1, In, i);

T->Right = CreateBinTree(Pre+i+1, In+i+1, Len-i-1);

return T;

}

int Height( BinTree T )

{ /* 求树的高度 */

int THeight, LHeight, RHeight;

if( !T ) /* 递归终止条件 */

THeight=0; else { /* 后序遍历 */

LHeight = Height(T->Left);

RHeight = Height(T->Right);

THeight = (LHeight>RHeight)? LHeight : RHeight;

THeight++; /* 树高为左右树高较大者加1 */

}

return THeight;

}

int main()

{

int N;

char Pre[MAXN+1], In[MAXN+1];

BinTree T = NULL;

scanf("%d", &N);

scanf("%s\n%s", Pre, In);

T = CreateBinTree(Pre, In, N);

printf("%d\n", Height(T));

return 0;

}

实验思考题：

1. 如果题目改为给定后序和中序遍历序列，该如何修改程序？

2. 如果题目输入的序列不保证正确，如何修改程序识别不匹配的错误？

合集下载

二叉树的基本运算实验

二叉树的基本运算实验

实

验

报

告

课 程 数据结构教程

班 级 信息管理与信息系统

学 号

姓 名

实验项目数 １

2014年05月 说明：

1.实验预习：通过实验预习，明确实验目的要求、实验原理及相关知识点、实验方法、步骤以及操作注意事项等；对设计性实验要事先设计实验方案；根据需要合理设计实验数据记录表格。

2.实验过程：实际采用的实验方法、步骤、操作过程或实验设计方案（设计型实验）的描述。对于实验结果的表述一般有以下两种方法，在撰写实验报告时，可任选其中一种或两种方法并用，以获得最佳效果。

（1）文字表述:

根据实验目的将原始资料系统化、条理化，用准确的专业语言客观

（2）图表或图形表示: 利用表格、坐标图、绘画或利用记录仪器描绘出的曲线图，使实验结果突出、清晰、形象、直观。

3.数据分析、实验结论

（1）根据相关的理论知识对所得到的实验结果进行解释和分析，包括实验成功或失败的原因。

（2）不能因实验结果与预期的结果或理论不符而随意取舍甚至修改实验原始数据和伪造实验结果。如果实验失败，应找出原因及今后应注意的事项。

4. 任课老师可结合学科和专业课程特点，对实验报告内容作科学合理的调整。

5．学生在课程结束后将本门课程所有实验报告装订成册，任课教师负责收齐交实验室存档 实验 七 （实验项目序号）

数据结构教程 课程实验报告 实验地点：

实 验

名 称 实现二叉树的各种基本运算的算法 指 导 教 师 实验时间 2014-5-21

姓 名 学号 成绩

一、实验、训练目的

1. 了解如何创建二叉链；

2. 了解如何使用算法计算二叉链的宽度,节点个数,叶子节点个数；

数据结构实验指导书(新版)

数据结构实验指导书(新版)

《数据结构和算法》

实验指导书

实验及学时数分配

序号 实验名称 学时数（小时）

1 实验一 线性表 4

2 实验二 树和二叉树 2

3 实验三 图 2

4 实验四 查找 2

5 实验五 内部排序 2

合计 12

几点要求：

一、 上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。

二、 上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。

三、 下机后：按要求完成实验报告，并及时提交（实验后1周内）。

实验一 线性表

【实验目的】

1、 掌握用Turbo c上机调试线性表的基本方法；

2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；

3、 运用线性表解决线性结构问题。

【实验学时】

4 学时

【实验类型】

设计型

【实验内容】

1、 顺序表的插入、删除操作的实现；

2、 单链表的插入、删除操作的实现；

3、 两个线性表合并算法的实现。(选做)

【实验原理】

1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；

2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；

3、 详细原理请参考教材。

【实验步骤】

一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。

1、 通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）

实验5 树和二叉树

实验5 树和二叉树

实验五 树和二叉树

一、实验目的

熟练掌握树与二叉树的基本概念、基本操作、各种遍历的递归与非递归算法，提高算法分析能力和源程序设计能力。

二、主要仪器及耗材

装有C编译系统的计算机

三、实验内容与步骤

1. 按前序遍历顺序创建一棵3度树，树的存储用孩子表示法存储，输出后序遍历、层次遍历序列。

输入序列AB___CE___FH___I____G___D___

2. 树的存储用数组方式孩子表示法存储，括号表示树，输出前序、后序遍历。

输入序列A（B，C（F，G，H），D，E（J，I））

3．假设树采用指针方式的孩子表示法表示：输入序列A（B（E，F（G，H，I）），C，D（J，K），L）

（1）实现树的前序遍历算法，后序遍历算法。

（2）判断两棵给定的树是否等价（两棵树等价当且仅当其根结点的值相等且其对应的子树均相互等价）。

4. 实现二叉树各种基本运算的算法，采用链式存储结构。

输入序列为：abd_e__fg___c__

（1）按前序遍历创建一颗二叉树，按后序输出；

（2）中序输出

（3）前序输出

（4）查找该树中是否存在结点X

（5）统计结点个数

（6）判断两颗二叉树是否等价

（7）求二叉树的高度

四、实验小结

[精品]【数据结构】二叉树实验报告

[精品]【数据结构】二叉树实验报告

[精品]【数据结构】二叉树实验报告

二叉树实验报告

一、实验目的：

1.掌握二叉树的基本操作；

2.理解二叉树的性质；

3.熟悉二叉树的广度优先遍历和深度优先遍历算法。

二、实验原理：

1.二叉树是一种树形结构，由n(n>=0)个节点组成；

2.每个节点最多有两个子节点，称为左子节点和右子节点；

3.二叉树的遍历分为四种方式：前序遍历、中序遍历、后序遍历和层次遍历。

三、实验环境：

1.编程语言：C++；

2.编译器：Dev-C++。

四、实验内容：

1.定义二叉树节点结构体：

struct BinaryTreeNode

{

int data; // 节点数据

BinaryTreeNode *leftChild; // 左子节点指针

BinaryTreeNode *rightChild; // 右子节点指针

};

2.初始化二叉树：

queue q; // 使用队列存储节点 q.push(root);

int i = 1; // 创建子节点

while (!q.empty() && i < length)

{

BinaryTreeNode *node = q.front();

q.pop();

if (data[i] != -1) // 创建左子节点