软考-软件设计师：数据结构-二叉树的分类：空树、一个结点的树、单支树、完全二叉树、满二叉树

作者：马育民 • • 阅读：10086

介绍

二叉树是一种常见的树，每个节点 最多有两个子节点：

  • 左子节点
  • 右子节点

每个节点都包含一个值或者数据，值可以是任何类型的数据。

二叉树分类

  • 空树，即：没有结点的树

  • 1个结点的树

  • 单支树

  • 满二叉树

  • 完全二叉树

  • 非完全二叉树

空树

没有结点的树

1个结点的树

即：只有一个节点

单支树

单支树指的是：只有一个孩子并且方向一致，如下图：4层的左单支树和右单支树

类比：相当于链表

特点

每个结点最多只有一个孩子结点，

完全二叉树

深度为 k、有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号 从1至n 的结点一一对应时，称之为完全二叉

理解

除了最后一层，所有层都填满。最后一层的节点 靠左排列，只允许右边空缺，但不能中间空缺。编号是连续的

一句话：从上到下、从左到右依次填满，只允许 最后一层右边缺。编号连续的

特征

  • 除最后一层外，其他层都是满的
  • 最后一层节点必须靠左连续排列
  • 非常适合用数组存储（堆就是完全二叉树）

非完全二叉树

如下图：各层结点 不是 从左到右依次放置，编号 不是 连续的，就是非完全二叉树

满二叉树

若深度为 k 的二叉树有 2^k - 1 个结点，就是满二叉树

提示： -1 是因为 根只有一个结点

理解

除了叶子节点，每个结点下面都有两个子节点。编号连续

连续编号

编号从根结点起，自上而下、自左至右依次进行

可以对满二叉树连续编号，如上图

特征

  • 高度为 k 的满二叉树，节点总数 2_k-1

  • 所有叶子节点都在最后一层

  • 是最 “完美” 的二叉树结构

完全二叉树、满二叉树

满二叉树一定是完全二叉树
完全二叉树不一定是满二叉树
满二叉树是完全二叉树的 “特例”。

存储结构

顺序存储 - 方式一

用一组连续的存储单元存储二叉树中的节点，按照从上到下，从左到右的顺序依次存储每个节点

缺点：没有存位置信息，无法还原树，摒弃

顺序存储 - 方式二

先计算出与该树对应的满二叉树的结点数量，定义数组，按照结点编号放入到应对的索引位置

根据上面的树，算出满二叉树的结点数量，按照结点编号放入到应对的索引位置，如下图：

优点：能还原树
缺点：浪费空间

链式存储 - 二叉链表

用二叉链表来存储二叉树节点，二叉链表中每个元素包含：

  • 该节点本身的数据
  • 左孩子结点的指针
  • 右孩子结点的指针

即：一个数据 + 两个指针，每个二叉链表节点存储一个二叉树节点，头指针则指向根节点

优点：能还原树，不浪费空间
缺点：无法根据子结点找到父结点

特性

特性1

  • 在二叉树的第 i 层上最多有 2^{i-1}个结点 (i从1开始）

  • 深度为 k 的二叉树最多有 2^k-1 个结点(k从1开始）

特性2 - 完全二叉树特性

如果对一棵有 n 个结点的完全二叉树的结点按层序编号（从第1层到 \left \lfloor log_2n \right \rfloor + 1 层，每层从左到右），则对任一结点 i （ 1≤i≤n ）

提示： 符号 \left \lfloor \right \rfloor 表示取低函数，即：向下取整

有:

  • 如果 i=1，则结点 i 无父结点，是二叉树的根

  • 如果 i>1，则父结点是 \left \lfloor \frac{i}{2} \right \rfloor

    如：上图结点 3 ，代入公式，父结点：\left \lfloor \frac{3}{2} \right \rfloor = 1

  • 如果 2i>n，则结点 i 为叶子结点（无左子结点）；否则，其左子结点是 2i ;

    如：上图结点 4，代入公式，2 * 4 > 6，是叶子节点，无左子结点；上图结点 2，代入公式，2 * 2 < 6，不是叶子节点，左子结点是 4

  • 如果 2i+1 > n ，则结点 i 无右子叶点，否则，其右子结点是结点 2i+1

    如：上图结点 3，代入公式，2 * 3 + 1 > 6，无右子结点；上图结点 2，代入公式，2 * 2 + 1 < 6，右子结点是 5

特性3

对任何一棵二叉树，如果其 叶子结点数 为 n_0，度为 2 的结点数为 n_2，则 n_0 = n_2 + 1

提示： 度为 2 的结点，表示该结点有 2 个子树

理解：有公式可以推导，但复杂，直接看上图：

  • 叶子结点：4、5、6，共3个
  • 度为 2 的结点：1、2，共2个

结论： 3 = 2 + 1

特性4 - 具有N个结点的二叉树形态数

有公式，复杂，略

原理：拿出 1个结点做根，剩余结点分成 2组，在左右两侧分布排列。

  • 0个结点的二叉树形态 1 种：空树

  • 1个结点的二叉树形态 1 种：单结点树

  • 2个结点的二叉树形态 2 种，如下图：

  • 3个结点的二叉树形态 5 种：1 个是根节点，其余结点：左0右2、左1右1、左2右0，其中，有两个结点的又有 2 个形态。

  • 4个结点的二叉树形态 14 种

  • 5个结点的二叉树形态 42 种

特性5

上图可知：

  • 度为 2 的结点：1、2，共 2 个
  • 度为 1 的结点：3，共 1 个
线的数量 + 1 = 结点的数量

即：

度为m * 度为m的数量 + 度为n * 度为n的数量 + ... + 1 = 结点数量

代入公式：

2(度为2) * 2(度为2的数量) + 1(度为1) * 1(度为1的数量) + 1 = 6

题

思考：各个结点的编号为多少？

分析

根结点 A 的编号是 1

根据上面特性：左节点的编号是 2i，右节点的编号是 2i + 1，

所以：

  • B 编号 2
  • C 编号 3
  • D 编号 6
  • E 编号 7
  • F 编号 14

题

对下面的二叉树进行顺序存储（用数组MEM表示），已知结点A、B、C在MEM中对应元素的下标分别为1、2、3，那么结点D、E、F对应的数组元素下标为（ ）

A、4、5、6
B、4、7、10
C、6、7、8
D、6、7、14

分析

根据上面的 特性2 可知：

  • D 的下标是 C的下标 * 2 = 3 * 2 = 6
  • E 的下标是 C的下标 * 2 + 1 = 3 * 2 + 1 = 7
  • F 的下标是 E的下标 * 2 = 7 * 2 = 14

答案

D

题

设某二叉树采用二叉链表表示（即结点的两个指针分别指示左、右孩子）。当该二叉树包含k个结点时，其二叉链表结点中必有（）个 空的孩子指针

A、k-1
B、k
C、k+1
D、2k

分析

没什么更好的方法，就是随便画个二叉树，计算空的孩子指针，如下图：

答案

C

题

已知树T的度为 4，且度为 4 的结点数为 7 个、度为 3 的结点数为 5 个、度为 2 的结点数为 8 个、度为 1 的结点数为 10 个，那么T的叶子结点个数为（ ）。（注：树中结点个数称为结点的度，结点的度中的最大值称为树的度。

A、30
B、35
C、40
D、49

分析

由特性5可知：

4 * 7 + 3 * 5 + 2 * 8 + 1 * 10 + 1 = 7 + 5 + 8 + 10 + 叶子节点数量

所以：

叶子节点数量 = 40

答案

D

参考：
https://blog.csdn.net/aa2528877987/article/details/135436389

原文出处：/show_1GWvnIob1nB.html

吉ICP备15003043号