二叉树基础：从定义到性质，再到两种特殊形态

各位同学，今天我们来聊聊二叉树。说实话，树形结构里最常用、最基础的就是二叉树了。我在做嵌入式开发那几年，几乎每个项目都离不开它——从表达式解析到哈夫曼编码，二叉树的身影无处不在。

一、二叉树的定义

先给个严谨的定义：二叉树（Binary Tree）是每个节点最多只有两个子树的树结构。这两个子树分别叫左子树和右子树，而且它们是有顺序的——左就是左，右就是右，不能互换。

你可能会问：「那它和普通的树有啥区别？」

区别大了。普通树的节点可以有任意多个孩子，而二叉树最多两个。这个「最多两个」的限制，让很多算法变得简单又高效。我个人习惯把二叉树想象成一个家族图谱——每对夫妻最多生两个孩子，老大是左孩子，老二是右孩子。

二、二叉树的性质（性质1-5）

二叉树有5个经典性质，我当年考试时背得滚瓜烂熟。但真正理解它们，是在我写一个内存分配器时——这些性质帮我算出了最坏情况下的空间开销。

性质1：第i层最多有2^(i-1)个节点

这个很好理解。根节点在第1层，最多1个（2^0）。第2层最多2个（2^1）。第3层最多4个（2^2）。说白了，每层最多是上一层的两倍。

性质2：深度为k的二叉树，最多有2^k - 1个节点

把每一层的最大节点数加起来：2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1。嗯，等比数列求和，初中数学。

性质3：叶子节点数 = 度为2的节点数 + 1

这个性质有点意思。记叶子节点数为n0，度为1的节点数为n1，度为2的节点数为n2。那么总节点数 n = n0 + n1 + n2。

另一方面，从边的角度看：除了根节点，每个节点都有且仅有一条边指向它。所以边数 = n - 1。而每个度为2的节点贡献2条边，度为1的贡献1条，度为0的贡献0条。所以边数 = 2*n2 + 1*n1。

联立两个等式：n0 + n1 + n2 - 1 = 2*n2 + n1 → n0 = n2 + 1。

我在项目中用这个性质来验证二叉树的合法性——如果发现叶子节点数不等于度为2的节点数加1，那这棵树肯定有问题。

性质4：具有n个节点的完全二叉树，深度为⌊log₂n⌋ + 1

这个性质在实现堆排序时特别有用。你想想看，给定节点数，就能直接算出树的高度，方便分配数组空间。

性质5：完全二叉树的节点编号规律

如果对完全二叉树按层序编号（从上到下，从左到右），那么对于编号为i的节点：

• 如果i=1，它是根节点
• 如果i>1，它的父节点编号是⌊i/2⌋
• 如果2i ≤ n，左孩子编号为2i；否则无左孩子
• 如果2i+1 ≤ n，右孩子编号为2i+1；否则无右孩子

这个性质太重要了。用数组存储完全二叉树时，直接通过下标就能找到父子关系，不需要指针。我曾经用这个特性写过一个极简的优先队列，代码量少得惊人。

三、满二叉树与完全二叉树

这两个概念经常被混淆，我刚开始学的时候也搞混过。咱们把它们掰开揉碎了讲。

满二叉树（Full Binary Tree）

定义：所有层的节点数都达到最大值。也就是说，深度为k的满二叉树，节点数正好是2^k - 1。

特点：

• 每个节点要么是叶子，要么有两个孩子
• 不存在度为1的节点
• 叶子节点全部在最底层

完全二叉树（Complete Binary Tree）

定义：除了最后一层，其他各层都是满的；最后一层的节点全部靠左排列。

特点：

• 最后一层可以不满，但必须从左到右连续
• 不存在「中间空一个节点」的情况
• 满二叉树一定是完全二叉树，反之不成立

两者的对比

对比项	满二叉树	完全二叉树
节点数	固定：2^k - 1	范围：[2^(k-1), 2^k - 1]
最后一层	全部填满	从左到右连续填充
度为1的节点	不存在	最多1个
数组存储	无空洞	无空洞

四、知识体系结构图

下面我用一张图把本章的核心知识点串起来，方便你建立整体认知：

这张图把二叉树的知识体系分成了三大块：定义、性质和特殊形态。我个人建议你先把性质3和性质5记牢——这两个在笔试面试中出现频率最高。

好了，二叉树的基础就讲到这里。记住，这些性质不是用来死记硬背的，而是在写代码时帮你做正确性判断的工具。下次你写树的遍历或者堆排序时，回头看看这些性质，会有新的体会。

---

公众号:蓝海资料掘金营，微信deep3321