实验七 二叉树

实验七 二叉树

实验目的和要求

  1. 掌握二叉树的特点和性质
  2. 掌握求取二叉树深度的方法

实验环境

  1. Visual Studio 2017 Community
  2. Windows 10 Pro

实验内容

  1. 利用给定数据构造二叉树,并将其遍历
  2. 使用三种不同的方式求取二叉树的深度

实验过程

任务一

设计

二叉树中的每个节点都可能具有左孩子和右孩子且需要存放数据,可以定义一个结构体来表示每一个节点。

遍历是对树的一种最基本的运算,所谓遍历二叉树,就是按一定的规则和顺序走遍二叉树的所有结点,使每一个结点都被访问一次,而且只被访问一次。

由于二叉树是非线性结构,因此,树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。考虑到二叉树本身就具有递归定义的特点——每个节点的子树又构成一颗二叉树,故而可以采用递归的方式来遍历二叉树,先访问根节点然后再遍历左、右子树。

编码实现

编码实现,通过 C++ 来实现以上分析过程。

测试

二叉树

任务二

设计

为了求树的深度,可以先求其左子树的深度和右子树的深度,可以用递归实现,当前树的高度即为左、右子树的高度中较大的一个再加 1,递归的出口就是节点为空。

利用层次遍历的算法,设置变量 depth 记录当前节点所在的层数,当遍历完层后,depth 自增一次。可以采用两个队列来存放当前层的节点和下一层的节点,这样即可分辨当前层的节点是否遍历完成。

利用递归遍历的算法,设置 depth 表示当前的深度,maxDepth 表示最大深度,访问子节点时 depth 自增,若 depth 大于 maxDepth,则 maxDepth 自增,从子节点返回父节点时, depth 自减,访问完每个节点后,即可得到二叉树的深度

编码实现

通过 C++ 进行编写代码。

测试

三种算法均可正确求出二叉树的深度

实验收获

通过本次实验,掌握了构造二叉树的方法,二叉树的递归特性有了更进一步的理解。尤其是在遍历二叉树时,利用二叉树的递归特性,可以写出非常简洁的递归算法。

在求二叉树的深度时,可以采用分治的方法,将整个二叉树的深度问题分解为许多子树的深度问题,最后再合并,可以说该算法非常简单明了。