看图聊算法：完全二叉树

将 脚本之家 设为“星标⭐”

第一时间收到文章更新

来源 | dingtingli

作者 | dingtingli

二叉树（Binary Tree）是一种特殊的数据结构。在这种结构中，每个节点都有两个子节点，通常被称为“左子树”和“右子树”。

二叉树

在这种数据结构中，每个节点都有指向其父节点和左右子节点的三个指针。

当一棵二叉树的特性满足以下条件时，它被称为完全二叉树（Complete Binary Tree）：

• 除最底层外，其他层的节点数均已满。

• 最底层的节点都集中在左侧。

完全二叉树

与普通的二叉树不同，完全二叉树可以使用数组进行隐式表示，无需使用指针。

这种表示方法是将树上的所有节点按顺序存放在数组中。节点间的关系可以通过其在数组中的位置来确定。

完全二叉树数组结构

例如，根节点存放在数组的第 1 位置，其左右子节点分别位于 2 和 3 位置。对于任意位置 i 的节点，其父节点和子节点的位置可以通过以下公式计算：

  Parent = i / 2
  Left = 2 * i
  Right = 2 * i + 1

其中，Parent 表示节点 i 的父节点位置，Left 和 Right 分别表示其左子节点和右子节点的位置。

完全二叉树数组节点公式

以图中的数组为例，当 i=4 时，我们可以直接计算出其父节点和两个子节点的位置。

完全二叉树数组节点 i=4

最后，我们来思考一个问题：

我们选择从数组的第 1 位置开始存储完全二叉树的节点。这种方式确实使得节点关系的计算变得直观和简单。但我们都知道，传统的数组索引是从 0 开始的。那么，如何在实际编程中实现这种存储方式呢？

  推荐阅读：