二叉树的类型


难度级别 易得奖学金
经常问 德里韦里 印孚瑟斯 空气质量
理论

在继续之前,我们首先要了解BT的真正含义是什么? 二叉树是一种 数据结构 本质上是分层的。 BT由节点表示,其中每个节点都有左,右指针,并且数据是节点的权重。 每个节点最多可以包含2个子节点,它们分别引用父节点的左子节点和右子节点。

二叉树的类型

为什么我们需要二叉树? | 为什么我们使用二叉树?

  • 使用BT,我们可以对数据进行快速搜索,插入和删除(以某种优先级顺序提供,例如BST)。
  • 使用BT,我们还可以找到最接近的项目。
  • 以分层方式存储数据(例如计算机中的文件系统)。
  • 使用指针实现BT,只需花费较少的时间即可执行任何操作。
  • 用前缀查找实现字典。
  • 快速搜索给定数据集的固定文本。

二叉树的性质

  1. 任何级别的最大节点数: 2 ^升 其中L是多个级别(0 <= L <= H)。
  2. 高度为H的BT中的最小和最大节点数: 高+1 和最大- 2 ^(H + 1)– 1 其中级别0为高度0。
  3. 具有N个节点的给定BT的最小可能高度: log2(N + 1)-1 其中级别0为高度0。
  4. 叶节点总数: 有2个子节点+ 1的节点总数。
  5. 具有L个叶节点的BT的最小级别数: (log2 L)+1.

二叉树的类型

全二叉树

一棵二叉树,其根节点和中间节点有2个子节点。 换句话说,我们也可以说除叶节点外,每个节点都有2个子节点。

请注意: 完整二叉树中的叶节点数: 内部节点数+1.

全二叉树

完整的二叉树

一棵二叉树,其除最后一个级别外的所有级别都被完全填充,并且所有节点从左到右都被填充

请注意: 二进制堆是完整的二进制树的示例。

完整的二叉树

完美的二叉树

一棵二叉树,其内部节点和根节点有2个子节点,所有叶均处于同一级别。

请注意: 完美二叉树中的节点总数: 2 ^ H -1 其中H是BT的高度。

完美的二叉树

平衡二叉树

然后其左子树高度h1和右子树高度h2的二叉树 | h1-h2 | <= 1.

请注意: AVL和RB树维护平衡的二叉树。

平衡二叉树

病理二叉树(倾斜 BT /简并BT)

所有内部节点只有一个子节点的二叉树可能是左子节点,也可能是右子节点。

请注意: 病理性BT高度: 节点数-1.

病理二叉树

 

参考 面试问题