二叉树（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 开始的。那么，如何在实际编程中实现这种存储方式呢？

WWH 系列文章列表：

[1] Why - 为什么 JS 更像一门编译型语言？

[2] What - 什么是依赖注入？

[3] What - 什么是 Big O？

[4] How - 不同的语言都如何处理错误？

[5] How - 面向对象语言如何处理异常？

[6] Why - 为什么排序算法复杂度上限是 O(NlogN)？

最近文章列表：

[1] 在 C 语言中实现简单的哈希表

[2] 成就卓越：事业成功的核心要素

[3] C++异常处理的底层机制

[4] .git 目录里到底包含了什么？

[5] 看图聊算法：一个游戏让你理解二分法的本质

[6] 看图聊算法：超越二分法，探索大厂经典面试题

[7] 看图聊算法：插入排序，使用频率最高的排序算法

[8] 看图聊算法：归并排序的原理与优化

[9] 看图聊算法：冯·诺依曼的第一个计算机程序

[10] 看图聊算法：快速排序为什么快？

[11] 不刷题，不面试，来看看算法学习在编程世界中的真正价值

喜欢本篇文章，记得动动小手点个