树系列第 3 篇：二叉树——最受宠的树

本文是“树系列”的第三篇。前两篇我们认识了树的整体面貌：什么是根、什么是叶子、什么是子树，以及树与线性表、图之间到底差在哪里。这一篇我们只做一件事：给“树”加上一条最严格的限制——每个节点最多只能有两个孩子——然后看看计算机世界为什么如此偏爱这棵被“砍”过的树。你会发现，堆、二叉搜索树、AVL 树、红黑树、哈夫曼树，这些鼎鼎大名的数据结构全都长在二叉树这块地基上。它不是森林里最高大的那棵树，却是计算机科学里最受宠的那棵树。

如果你在前两篇里还没有完全熟悉树的术语，先别急着往下冲，花两分钟把第 0 节过一遍。这篇之后，你脑子里应该形成一幅地图：二叉树是“地基”，后面所有高级树都是在这个地基上盖出来的不同建筑。

0 先把前两篇的术语捡回来

树（tree）是由节点（node）和连接节点的边（edge）组成的层次结构。它有一个特殊的起点叫根节点（root），根是唯一没有父亲（parent）的节点；从根出发，沿着边一层一层往下走，每个节点可以有若干个孩子（child），有同一个父亲的节点互为兄弟（sibling）。没有孩子的节点叫叶子节点（leaf），至少有一个孩子的节点叫内部节点（internal node）。从某个节点出发，把它自己和它所有的后代（descendant）一起“剪”下来，仍然是一棵树，这叫子树（subtree）。

描述树的位置，我们需要三个容易混淆的词：深度（depth）、层（level）和高度（height）。第 2 篇里我们约定：根在第 1 层，根的深度是 0，每往下走一条边，深度就加 1，层数等于深度加 1。高度有两种常见说法：一种是“从根到最远叶子的边数”，另一种是“从根到最远叶子的层数”。两种说法相差 1，很多教材混着用，这是初学者最容易踩的坑。本文会明确说明每次用的是哪一种，读到公式时先看约定，再套数字。

还有一个词叫度（degree）：一个节点有几个孩子，它的度就是几。第 1 篇里我们说，一棵树的“度”可以是任意的：组织架构图里，一个经理可以带 3 个、5 个甚至 10 个下属；文件系统里，一个文件夹可以装几十个子文件夹。普通树没有对孩子数量的硬性限制，这正是“树”这个大家庭最自由的地方。

自由当然是好事，但对计算机来说，自由往往意味着“难处理”。这一篇的主角——二叉树——就是给这份自由加上一条规则：每个节点的度最多是 2。别小看这条限制，它把一棵毫无章法的树，变成了一个可以分析、可以证明、可以高效搜索的数学对象。下面我们就从“为什么是二”这个问题开始。

0.1 本系列的路线图：你正站在哪一站

学习新知识最怕“不知道自己在哪”。所以这里先给你一张树系列的地图。第 1 篇回答“树是什么”，介绍了节点、根、叶子、子树这些最基本的积木；第 2 篇回答“树有什么性质”，讲了层、深度、高度、度数以及树和线性表、图的区别；本篇（第 3 篇）回答“为什么是二叉树”，把树的形态限定到“最多两个孩子”，并推导出它的核心数学性质。接下来，第 4 篇讲树在计算机里怎么存，第 5 篇讲遍历，之后会依次进入二叉搜索树、AVL 树、红黑树，以及堆——还记得吗，堆就是第 16 篇那个用数组装的完全二叉树。

这张地图告诉你两件事。第一，本篇是“地基中的地基”：后面几乎所有内容都会引用第 4 节的公式和第 3 节的形态定义，地基打不牢，后面盖楼会晃。第二，本篇的定位是“建立直觉”，所以很多严格证明和代码实现被刻意留到了后面的篇章：公式先讲“为什么”，代码后讲“怎么写”。如果你读本篇时觉得某些地方“懂了但写不出来”，完全正常，那是第 4、5 篇的职责。

1 为什么是“二叉”：最多两个孩子的直觉

1.1 从“一对多”到“一对二”，世界一下子变简单了

想象你要设计一个问答程序：程序内部有一个问题库，用户每回答一个“是”或“否”，程序就沿着一条路往下走，最终给出诊断结果。这个结构天然就是一棵树，而且每个节点只需要两个出口：是、否。如果每个问题允许 5 个答案，问答树会立刻变得臃肿：每个节点要维护 5 个分支，代码要多写 5 份判断逻辑，画图时 5 条线挤在一起，更别提“这些分支该怎么排序、怎么查找”这些麻烦事了。

把出口压缩到两个之后，一切变得清爽：左和右、是和否、小于和不小于、进左半区和进右半区。两个出口意味着每一次选择都是二分（binary）的：不是走左边，就是走右边。人类的直觉、数学的证明、计算机的判断，全都围绕“二”这个数字转，这就是“二叉”二字背后的第一层直觉：二分让每一步的选项最少化。

你可能会问：那为什么不是“一叉”？一个孩子退化成一条链，每一步都没有选择，查找只能老老实实从头走到尾，效率跟线性表一样，失去了“树”的意义。两个是“有选择”的最小数量：有左右两条路，才能把规模一分为二，才有可能实现“每次排除一半”的指数级加速。所以二叉树不是“随便选的形态”，而是“有选择能力的最简形态”。

1.2 “二分”是计算机世界里的老熟人

其实你早就见过二分的威力。二分查找（binary search）的故事是这样的：一本 1000 页的电话簿，你想找某个名字，不会从第 1 页翻到第 1000 页，而是先翻到中间，看看目标在左半本还是右半本，然后只带着一半继续翻。每翻一次，待查找的页数减半。翻 10 次，1000 页就缩小到大约 1 页。这种“每次把问题砍掉一半”的思路，正是二叉树最大的卖点：如果一棵树的每个节点都把数据分成左右两半，那么从根走到叶子只需要“高度那么多次”选择，而高度只有节点数的对数级别。

再看数学里的二分法。求一个方程的近似根，先取区间中点，判断根在中点左边还是右边，然后丢掉另一半区间，继续缩小区间。过程里每一步只有两个方向。二分法、二分查找、二叉搜索树，它们共享同一个灵魂：通过“二”来分裂问题，通过分裂来压缩搜索空间。

更妙的是，“二”与计算机的底层世界天然合拍。计算机里的所有信息最终都表示成二进制：一位（bit）只有 0 和 1 两个值。一个二进制位可以回答一个“是/否”问题，n 个二进制位可以区分 2 的 n 次方种状态。二叉树的每一层也像一个二进制位：在某一层，节点要么走左（记作 0），要么走右（记作 1）。从根到某个节点的路径，就等价于一串 0/1 编码。二叉树和二进制之间的这种呼应不是巧合，它让树的结构可以轻松映射成数字、下标和位运算，这是很多高级数据结构能“跑得快”的底层原因。

1.3 递归结构最简：一棵树里长着两棵更小的树

二叉树还有一个常被低估的优点：它的结构定义本身就是递归的。普通的多叉树，定义成“若干棵子树”时，你总得面对“若干”这个不确定的数字；而二叉树可以这样干干净净地定义：一棵二叉树要么是空树，要么由一个根节点加上一棵左子树和一棵右子树组成，而且左、右子树本身仍然是二叉树。

这个定义有多重要？递归的定义意味着我们能用递归的函数去处理它：要处理整棵树，先处理根，再调用自己处理左子树，再调用自己处理右子树。代码长度可以压缩到几行，逻辑也特别容易用数学归纳法证明。后面第 5 篇要讲的前序、中序、后序遍历，本质上就是把这句话翻译成三行不同的顺序。一个结构“天生适合递归”，对程序员来说是巨大的幸福——很多复杂问题（表达式求值、语法分析、文件统计）在二叉树上写起来都像行云流水。

1.4 一棵“坏”的二叉树是什么样的

为了让“二叉”的威力看得更清楚，先看一眼它的反面。如果一棵二叉树的每个节点都只有一个孩子，比如根只有左孩子，左孩子又只有左孩子……那么整棵树就变成一条长长的链，专业说法叫退化二叉树（degenerate binary tree），或者“链表形态的树”。链式二叉树每一步只有一个选择，从根到最深的叶子要走 n-1 条边，查找效率和链表一模一样，完全没有利用“二”的优势。

所以请记住一个重要结论：不是所有二叉树都高效。二叉树的效率天花板，取决于它是否“长得匀称”——左右两半是否大致平衡。这就是为什么后面的二叉搜索树要引入平衡机制（AVL、红黑树），本质上都是在说：别让树退化成链。现在我们把“为什么是二叉”的直觉建立起来了，接下来给出严格的数学定义。

1.5 二叉与分治：一棵树就是一张“决策地图”

“为什么是二叉”还有一个更宏观的答案：二叉树是分治思想（divide and conquer）最自然的可视化。分治的套路是三步：把大问题分解成小问题，分别解决小问题，再把结果合并成大问题的答案。二叉树的形状恰好就是这三步的图解：根节点代表“当前问题”，左右子树代表“两个更小的子问题”，递归下去，直到叶子（最小问题）直接给出答案。

举一个你熟悉的例子：单败淘汰赛。16 名选手捉对厮杀，每场比赛淘汰一人，最后决出冠军。把比赛过程画成图：第一轮的 8 场比赛是第 4 层，第二轮 4 场是第 3 层，依次往上，决赛是根节点——这正是一棵完美的二叉树，16 个叶子是选手，15 个内部节点是比赛。整个赛程天然是二分的：每场比赛只有两个参赛者，只有输赢两个结果。如果改成 3 人混战，比赛规则、赛程表、排名算法都会变得一团糟。体育界和计算机科学界不约而同地选择了“二”，因为二最简洁、最公平、最好分析。

再看另一个例子：判断一个数是否在有序数组中。二分查找每次把数组切成两半，只进入包含目标的那一半；这个“每步二选一”的决策过程，画出来就是一棵二叉树——虽然查找时我们并没有真的把树建出来，但每一步的“比较 → 向左或向右”和树的形状完全同构。所以学二叉树，不只是学一种数据结构，更是在学一种思维方式：凡是能二分的决策，都可以看作在一棵隐形的二叉树上走路。这颗种子会在二叉搜索树、AVL 树、红黑树里长成参天大树。

1.6 常见误解：“二叉树一定比普通树快”

聊完“为什么是二叉”，顺便拆掉一个最流行的误解：“二叉树一定比普通树快”。这句话错在把“结构叫二叉树”和“效率高”划了等号。

首先，效率高不高，看的是形态而不是名字。一棵退化成链的二叉树，查找要走 n-1 步，和链表一样慢；一棵长得匀称的多叉树，如果每层能装 10 个孩子、高度只有两层，查找可能比某些二叉树还快。第 4 节会给出精确结论：二叉树的高效，前提是“每层尽量翻倍”，也就是树要接近完美或至少保持平衡。所以正确的说法是：“长得匀称的二叉树，能提供对数级别的查找效率”，而不是“二叉树天然高效”。

其次，场景决定选型。内存里的数据，二叉树结构简单、指针开销小，很划算；磁盘上的数据，一次 I/O 的代价比一次比较大几万倍，这时候宁可让每个节点多装一些孩子（B 树），把树压得更矮、减少访问次数。数据库选 B+ 树、路由表选前缀树，都不是因为它们“不是二叉树”所以不好，而是因为它们更适合自己的存储介质。

最后，别忘了“快”还有另一层意思：写起来快、证明起来快。二叉树最吸引人的地方之一，是代码和数学分析都简洁。对一个学习者来说，“结构简单到能彻底搞懂”本身就是巨大的效率优势。所以正确的态度是：爱上二叉树的简单，但不迷信二叉树的名字——效率永远来自形态与场景的匹配。

2 二叉树的定义：左孩子和右孩子不是一回事

2.1 一句话定义

二叉树（binary tree）是一棵有序树，它的每个节点最多只有两个孩子，并且这两个孩子有明确的位置区别：一个是左孩子（left child），一个是右孩子（right child）。当某个孩子不存在时，我们说左子树为空或右子树为空，这个“空”也是树的一种合法形态，绝对不能省略。

把这句话拆开，有三个要点。第一，“最多两个”，所以 0 个、1 个、2 个孩子都合法。第二，“有序”，这是二叉树和“度不超过 2 的普通树”之间最本质的区别：普通树只要满足“孩子数量不超过 2”，但孩子的顺序无关紧要；二叉树则把左右当成两个不同的“槽位”。第三，“空位合法”，一个节点可以只有左孩子没有右孩子，也可以只有右孩子没有左孩子，这两种情况是两个不同的结构，因为占用的槽位不同。

下面这张图是二叉树的“标准证件照”：根节点 A 有左孩子 B 和右孩子 C；B 又有自己的左孩子 D 和右孩子 E；C 有左孩子 F 和右孩子 G；D 也有两个孩子 H 和 I。整棵树的每一个节点都满足“最多两个孩子”，并且左、右的位置清清楚楚。

2.2 左右有序：交换两个孩子，得到的是另一棵树

初学者最容易忽略的一点是：在二叉树里，“左”和“右”是信息的一部分，而不是画图时的排版习惯。把一棵树的左右孩子整体交换，得到的树虽然在“形状镜像”上看起来差不多，但作为数据结构是两棵不同的树。

为什么这个区别如此重要？因为后面几乎所有基于二叉树的结构都要“利用”左右的位置。二叉搜索树规定左子树放“较小”的数据、右子树放“较大”的数据；表达式树里，左子树是被减数、右子树是减数，一旦左右颠倒，a - b 就会变成 b - a，计算结果完全不同。左右有序意味着同一个节点集合可以“装进”很多种不同的二叉树，而每一种都对应不同的语义。所以判断两棵二叉树是否相同，不能只看节点值，还要看每个节点的左右子树分别是谁。

2.3 五种基本形态：先认识“积木”

既然每个节点最多两个孩子，而且左右是两个独立槽位，那么一棵二叉树最基本的结构形态只有五种：

第 ③ 种（只有左孩子）和第 ④ 种（只有右孩子）看起来只是方向不同，但在二叉树里必须区分：给节点 B 只挂一个左孩子，和给节点 B 只挂一个右孩子，是两个不同的结构。很多新手画图时习惯把单孩子画在左边，或者画在右边，自己心里却不当回事——这个习惯一定要改掉，因为后面做遍历、做序列化、判断两棵树相等时，左右颠倒会导致完全不同的结果。

2.4 递归定义：一棵树里藏着两棵更小的树

用“积木”搭出任意二叉树之后，数学家还喜欢把定义写得更有用一点。二叉树的递归定义是这样的：

• 基础情况：空树是一棵二叉树；
• 归纳步骤：如果 L 和 R 都是二叉树，那么由一个根节点、一棵左子树 L 和一棵右子树 R 组成的结构也是一棵二叉树；
• 封闭原则：除上述方式构造出来的结构之外，没有其他结构是二叉树。

这个定义听起来绕，其实意思很朴素：任意二叉树的任意一个节点，它往左延伸出去的部分是一棵完整的二叉树（左子树），往右延伸出去的部分也是一棵完整的二叉树（右子树）。也就是说，树里套着树。正因为“树中有树”，我们才能把大问题不断拆成两个小问题：想处理整棵树，先处理根，再处理左子树，再处理右子树；左子树和右子树又各自重复同样的过程。这个思路后面会反复出现，第 5 篇的三种遍历、第 7 篇的二叉搜索树操作、第 9 篇的 AVL 旋转，全都建立在“递归地看待树”这个习惯上。

2.5 四个常见误区，先踩为敬

第一个误区：“二叉树就是每个节点最多两个分支。”这句话只对了一半，还缺了“左右有序”这个关键前提。如果只是限制分支数量而不区分左右，那叫“度不超过 2 的普通树”，它和二叉树的数学性质差别很大。第二个误区：“空树不算二叉树。”空树在定义、证明和代码里极其常用——很多递归算法的终止条件就是“遇到空树直接返回”，如果不承认空树，算法写起来会麻烦得多。第三个误区：“有左孩子就必须有右孩子，不然结构不完整。”完全不是，只有左孩子或只有右孩子的二叉树完全合法，甚至后面讲退化二叉树时，一棵链状的树就是靠“只有单侧孩子”拼出来的。第四个误区：“二叉树每个节点都必须有两个孩子。”这是把二叉树和满二叉树搞混了，下一节专门讲这些特殊形态。

2.6 拿到一棵树，怎么判断它是不是二叉树

把定义翻译成一张检查清单，遇到任何一棵树，逐条打勾：

• 第一条：每个节点的孩子数是否不超过 2？ 只要出现一个节点有 3 个或更多孩子，直接排除。注意这条只数“孩子”，不数父亲、不数兄弟。
• 第二条：左右位置是否有意义？ 如果两个孩子的顺序可以随便换、换了也不影响结构，那它不是二叉树（只是一棵度不超过 2 的无序树）。二叉树的孩子集合是“槽位”，左边就是左边，右边就是右边。
• 第三条：空子树是否被允许？ 一个节点只有左孩子、没有右孩子，在二叉树里完全合法；反过来也合法。判断时不要把“只有单侧孩子”当成错误。
• 第四条：空树算不算？ 按教材约定，空树是一棵合法的二叉树。很多递归算法的“出口”就是空树，不承认它，代码就写不顺。
• 第五条：别被“长得像”骗了。 一棵多叉树如果每个节点的孩子恰好都不超过两个，但画图时从没区分左右，严格地说它还不是二叉树；只有明确了左右语义，才是。

用清单检验几个熟悉的例子。文件系统目录树不是二叉树：一个文件夹可以有十几个子文件夹。组织架构图通常不是二叉树：一个部门可以有多个下属团队。算式的表达式树是二叉树：每个运算符最多两个操作数，而且左右操作数绝不能互换。比赛对阵表是二叉树（更精确地说是完美二叉树）：每场比赛只有两个参赛者。家谱一般不当作二叉树：一对夫妻可以有多个孩子，而且兄弟姐妹没有“左弟右兄”的固定顺序。多练几次这种判断，二叉树的边界感就建立起来了。

3 特殊形态：满二叉树、完全二叉树、完美二叉树、退化二叉树

光有“最多两个孩子”这条规则，二叉树能长出的形状依然千奇百怪。为了说话方便，人们给几种特别典型的形状起了名字。这一节是本文的“看图识字”环节：四种形态各配一张图，逐个讲清定义，最后用一张关系图回答“谁包含谁”。

先立一个重要的约定。“满二叉树”这个词在不同教材里有两种完全不同的定义：有些教材把“每一层都铺满”的树叫满二叉树（英文 perfect binary tree），有些教材把“每个节点要么没有孩子、要么有两个孩子”的树叫满二叉树（英文 full binary tree，也叫 proper binary tree）。这两种定义并不等价，网上查资料时经常打架。本文统一采用后一种约定：满二叉树指“每个节点有 0 个或 2 个孩子”，即没有“只有一个孩子”的节点；而“每一层都铺满”的树，本文叫完美二叉树。记住这个约定，后面读别的书时只要对照一下它的定义就不会被绕晕。

3.1 满二叉树（Full Binary Tree）：没有“独生子”

满二叉树的定义就一句话：每个节点要么没有孩子，要么有两个孩子，绝不允许只有一个孩子。换句话说，树上找不到任何一个“独生子”节点。

注意看图 3 的一个细节：节点 C 和 E、F 是叶子，但 C 在第 2 层，E 和 F 在第 3 层，叶子并不都在同一层。这说明满二叉树不要求叶子对齐，它只禁止“独生子”。也正因为如此，满二叉树的节点总数可以是任意奇数——每加入一个新节点，必须同时加入它的兄弟，节点数一次性增加 2，所以非空满二叉树的节点数永远是奇数（1、3、5、7……）。

满二叉树有一个非常漂亮的计数性质，这里先剧透，后面 4.1 节会证明：在任何一棵非空二叉树里，叶子节点的个数恒等于“有两个孩子的节点”的个数加 1。写成公式就是 n₀ = n₂ + 1，其中 n₀ 是叶子数，n₂ 是有两个孩子的节点数。对满二叉树来说，没有“独生子”，这个公式描述的就是它最核心的骨架。你可以拿图 3 验证：叶子有 5 个，有两个孩子的节点有 3 个（A、B、D），5 = 3 + 1，完全吻合。

3.2 完全二叉树（Complete Binary Tree）：从左往右不许留空

完全二叉树的关键词是“连续”。它的定义是：除了最后一层之外，每一层都必须铺满节点；最后一层的节点必须从左到右连续排列，中间不能有空缺。

完全二叉树为什么重要？因为它和“数组”天生一对：把完全二叉树按从上到下、从左到右的顺序编号，节点恰好能一个萝卜一个坑地塞进数组里，中间不浪费任何下标。这是第 4 节的压轴内容，也是第 16 篇讲堆（heap）时的地基。现在先记住：完全二叉树是“可以压缩进数组”的树。

完全二叉树还有一个容易被忽略的特点：它允许最后一层不满，但不满的部分只能出现在最右侧。想象一排座位，观众必须从左边开始坐满，可以有人没来，但不能出现“左边的座位空着、右边的座位坐着人”的情况。用这个“坐座位”的比喻去判断一棵树是不是完全二叉树，会直观很多：从根出发一层一层数，只要发现某个节点右侧有空位、左侧却还缺着节点，它就不是完全二叉树。

3.3 完美二叉树（Perfect Binary Tree）：每一层都铺满

完美二叉树是“最对称、最理想”的形态：每一层都恰好铺满，任何一个位置都不空。第 k 层恰好有 2^(k-1) 个节点，整棵树像一个满格的三角形。

完美二叉树是满二叉树和完全二叉树的“交集明星”：它没有独生子（满足满），它也没有任何空缺（满足完全）。它的节点总数有精确公式：如果一共有 h 层，节点数就是 1 + 2 + 4 + … + 2^(h-1) = 2^h - 1。比如图 5 有 3 层，节点数是 2³ - 1 = 7。这个公式是下一节所有高度推导的原点，请务必记住它的推导过程，而不只是背结果。

完美二叉树之所以“完美”，还因为它的搜索效率是最优的：任何一次查找，最多只需要走 h 步，而 h 只有 log₂(节点数+1) - 1 那么大。不过现实中的数据很难恰好凑成完美的形状，所以工程上我们追求的不是“完美”，而是“接近完美”——这正是后面 AVL 树和红黑树要解决的问题：让树尽量匀称，但不苛求每一层都满。

3.4 退化二叉树（Degenerate Binary Tree）：披着树皮的链表

退化二叉树是“二叉”的反面教材：每个节点最多只有一个孩子，整棵树要么一直往左拐，要么一直往右拐，要么左右交替拐，总之永远不分支。它看起来完全不像一棵树，倒像一条拉直了的链。

退化二叉树不是“错误”，它是一种合法的边界情况。它的意义在于提醒我们：光靠“二叉树”这个名字，并不能保证任何效率。如果一棵二叉搜索树的插入顺序恰好是有序的，它就会长成退化形态，查找效率从 O(log n) 跌回 O(n)。正因为存在这种极端情况，后面才会有“自平衡”这一整套设计。所以看到退化二叉树时不要慌，把它当作“树的病态照片”，和健康形态对照着看，理解反而更深。

3.5 谁包含谁：四种形态的关系图

四种形态不是四个互不相干的盒子，它们之间有清晰的包含关系。用一个“性格测试”来记：

• 完美二叉树：每一层都满，是最严格的形态；
• 完全二叉树：除了最后一层，每层都满，最后一层从左到右连续；
• 满二叉树：没有独生子，叶子可以在不同层；
• 退化二叉树：几乎没有分支，是链状极端。

它们的关系可以总结成三句话。第一句：完美二叉树一定是完全二叉树，也一定是满二叉树。因为它每一层都铺满，自然满足“最后一层从左到右连续”，也自然没有独生子。第二句：完全二叉树和满二叉树互不包含——完全二叉树可能含有独生子（例如最后一层的某个节点只有一个孩子），满二叉树可能叶子不在同一层、甚至中间层有空缺（例如根有左右孩子，但左孩子是叶子、右孩子有两个叶子，左子树在第 2 层就断了，树不是按层铺满的）。第三句：退化二叉树是“满”和“完全”的对立面，通常与两者毫无交集，只有单节点这棵最小的树同时属于所有形态——它没有独生子，最后一层全满，也满足退化定义，是个有趣的“四栖”成员。

3.6 形态判定小练习：六棵树的“体检报告”

定义说得再多，不如亲手判几棵。下面六棵树，分别是什么形态？先自己判断，再看解析。

树 T1：一共 3 层，第 1 层 1 个节点，第 2 层 2 个节点，第 3 层 4 个节点，没有任何空位。它当然是完美二叉树；因为每一层都满，所以它同时也是满二叉树和完全二叉树，是“三料冠军”。

树 T2：4 层，前三层全部铺满，最后一层只有最左边的 2 个节点，且其中某个节点只有一个左孩子。它是完全二叉树（最后一层从左到右连续），但不是满二叉树（存在独生子），也不是完美二叉树（最后一层没满）。

树 T3：根有两个孩子，左孩子是两个叶子的父亲，右孩子本身就是叶子；左孩子的两个孩子中，又有一个继续往下长了一代。全树没有任何独生子，但叶子散落在第 2、3、4 层。它是满二叉树（没有独生子），但不是完全二叉树（第 4 层的节点没有从最左边连续铺满），更不是完美二叉树。

树 T4：每个节点都只有一个孩子，一路拐到底。它是退化二叉树，披着树皮的链表，高度高达 n-1。

树 T5：只有孤零零一个根节点。它是完美二叉树（1 层就是满的），是完全二叉树，是满二叉树（根有 0 个孩子，符合“0 或 2”），也是退化二叉树（每个节点最多 1 个孩子）——前面说过的“四栖”成员。

树 T6：5 个节点：根有左右两个孩子，左孩子有左右两个孩子，右孩子是叶子。它没有独生子，所以是满二叉树；最后一层（第 3 层）只有两个节点且从左到右连续，所以也是完全二叉树；但它不是完美二叉树（第 3 层没有铺满 4 个）。这个例子说明：满和完全并不互斥，交集里除了完美二叉树，还有 T6 这种“差一点点就完美”的树。这个细节很多教材不提，但面试官偶尔会拿它考人。

做完这组练习，你应该能体会到：判断形态的关键是先看“有没有独生子”（决定是不是满），再看“按层从左到右是否连续”（决定是不是完全），最后看“是否每一层都满”（决定是不是完美）。三个问题按顺序问，答案不会乱。

4 重要性质与直觉解释：二叉树为什么“好用”

这一节是全文的“数学重头戏”。好消息是：所有公式都不需要背，只需要跟着“每层翻倍”这个直觉走一遍，公式自己会长出来。我们一共推导四件事：某一层最多几个节点、整棵树最多几个节点、n 个节点的树有多高、完全二叉树怎么塞进数组。

4.1 第 k 层最多 2^(k-1) 个节点：每一层都翻倍

先从最基础的问题开始：一棵二叉树，第 k 层（根在第 1 层）最多能有多少个节点？

答案是 2^(k-1) 个。这个结论可以用一个非常朴素的“繁殖”故事讲清楚。第 1 层只有根，1 个节点，也就是 2⁰ 个。每个节点最多有 2 个孩子，所以第 2 层最多有 2 个节点，也就是 2¹ 个。到了第 3 层，第 2 层每个节点又最多贡献 2 个孩子，所以最多 2×2 = 4 个，也就是 2² 个。照这样推下去，每一层的节点数至多翻一倍：第 k 层最多 2^(k-1) 个。

用数学归纳法写出来也很短。当 k=1 时，2^(1-1)=1，根恰好 1 个，成立。假设第 k 层最多 2^(k-1) 个节点，那么第 k+1 层的每个节点都来自第 k 层某个节点的一个孩子，而第 k 层的每个节点最多有 2 个孩子，所以第 k+1 层最多有 2 × 2^(k-1) = 2^k 个节点，也满足公式。归纳完成。

“每层翻倍”这四个字，是二叉树全部数学性质的心脏。翻倍的威力有多大？第 10 层最多 512 个节点，第 20 层最多 52 万多个节点，第 30 层最多 10 亿多个节点。换句话说，只要树“长得匀称”，30 层就能装下全世界的人口数据。这正是二叉搜索树查找为什么快如闪电的根本原因：从根走到目标，走的步数大约就是“层数”，而层数随节点数增长得非常缓慢。

顺便把上一节承诺的公式证掉：在一棵非空二叉树里，叶子节点数 n₀ 等于“有两个孩子的节点数”n₂ 加 1，即 n₀ = n₂ + 1。证明只用“数边”这一招。设 n₁ 是只有一个孩子的节点数。整棵树有 n = n₀ + n₁ + n₂ 个节点，边数一定是 n - 1（除根外每个节点都有一条指向父亲的边）。另一方面，从“每个节点贡献多少条向下的边”来数，n₀ 个叶子贡献 0 条，n₁ 个节点贡献 1 条，n₂ 个节点贡献 2 条，总数是 n₁ + 2n₂。于是 n - 1 = n₁ + 2n₂，把 n 的表达式代入：n₀ + n₁ + n₂ - 1 = n₁ + 2n₂，两边约掉 n₁，得到 n₀ = n₂ + 1。这个公式看似不起眼，却是满二叉树、哈夫曼树、各种树计数问题的万能钥匙。

4.2 高度为 h 的二叉树最多 2^h - 1 个节点：等比数列求和

有了“第 k 层最多 2^(k-1) 个”，整棵树的节点数上限就是把每一层的上限加起来：

1 + 2 + 4 + … + 2^(h-1)

这里 h 表示层数（根是第 1 层，h 层就表示树“最高到第 h 层”）。这是一个等比数列，公比是 2，第一项是 1，一共 h 项。等比数列求和的公式是：和 = 首项 × (公比^项数 - 1) / (公比 - 1)，代入后得到：

1 + 2 + 4 + … + 2^(h-1) = 2^h - 1

这就是本文最重要的一条公式：高度为 h（层数）的二叉树最多有 2^h - 1 个节点。达到这个上限的树，正是上一节说的完美二叉树——每一层都铺满，一个空位都不留。

为什么非要会推导而不是背公式？因为“2^h - 1”背后的直觉比公式本身有用：每一层都翻倍，所以前面所有层的节点总数，加起来只比最后一层少 1。你看，1+2+4=7，而 8-1=7；1+2+4+8=15，而 16-1=15。前 h-1 层加起来永远等于 2^(h-1) - 1，恰好比最后一层 2^(h-1) 少 1。这个“最后一层比前面所有层加起来还多 1 个”的观察，在很多算法分析里会反复出现，比如哈夫曼树的编码长度、堆排序的建堆分析。

这张图把“2^h - 1”的推导画成了实物：第 3 层有 4 个节点，而前两层加起来只有 3 个——最后一层恰好比前面所有层加起来还多 1，所以三层总数是 4 + 3 = 7。

这里必须再次提醒“高度”的两种约定。本文这条公式里的 h 是层数：单节点树的 h=1，最多 2¹-1=1 个节点，自洽。如果把高度定义成“边数”（记为 H），那么单节点树的 H=0，公式要写成最多 2^(H+1) - 1 个节点。两套约定只是相差 1，本身没有对错，但混用就会出错。后面 4.3 节推导高度范围时，我们会明确采用“边数”约定，因为任务里给出的范围公式 log₂(n+1)-1 到 n-1 用的就是边数。读任何资料前，先搞清楚对方说的“高度”是层数还是边数，这个习惯能帮你避开一大类错误。

4.3 n 个节点的二叉树，高度范围从 log₂(n+1)-1 到 n-1

把公式倒过来用，就能回答一个更有用的问题：给定 n 个节点，这棵树最高能多高？最矮能多矮？

先看最高。如果每个节点都只有一个孩子，树就退化成一条链（上一节的退化二叉树）。n 个节点的链，从根到最深的叶子有 n-1 条边，所以用边数表示的高度是 n-1。这是 n 个节点能“拉”出的最大高度，因为每次只能让树“变深”一个节点，别无他法。

再看最矮。树要矮，就得让每一层尽量装得多，也就是“每层翻倍”地铺。假设用边数表示的高度是 H，那么层数就是 H+1，最多能装 2^(H+1) - 1 个节点。既然这棵树有 n 个节点，就必须满足：

n ≤ 2^(H+1) - 1

两边加 1，再取以 2 为底的对数：log₂(n+1) ≤ H+1，也就是 H ≥ log₂(n+1) - 1。因为 H 必须是整数，实际写成 H ≥ ⌈log₂(n+1)⌉ - 1，其中 ⌈⌉ 表示向上取整。

所以结论是：n 个节点的二叉树，高度（边数）最小是 log₂(n+1)-1 附近，最大是 n-1。举例感受一下：n=7 时，完美树的 H=2，恰好等于 log₂8-1=2；链状树的 H=6。n=100 万时，完美树的高度只有约 19，链状树的高度却是 999999——两者相差 5 万多倍。这就是“长得匀称”和“退化成链”之间的天壤之别，也是为什么算法工程师对“平衡”二字如此执着。

直觉推导可以浓缩成一句话：树越矮越好，而“每层翻倍”决定了最矮的树也至少要有 log₂(n+1)-1 那么深，因为层数太少，容量不够装下 n 个节点。反过来，“每层只放一个”决定了最高能到 n-1。这个区间 [log₂(n+1)-1, n-1] 就是所有二叉树形态的“身高范围”，后面讲 BST、AVL、红黑树时，我们衡量“平不平衡”用的正是它。

4.4 完全二叉树的数组存储：父子下标 2i 和 2i+1

现在终于轮到完全二叉树的“独门绝技”：它可以用数组存储，而且不需要任何指针。

做法是把节点按“从上到下、从左到右”的顺序编号：根是 1 号，根的孩子依次是 2 号、3 号，再往下第 3 层的节点从左到右是 4、5、6、7 号……把第 i 号节点放进数组的第 i 个位置（下标从 1 开始）。神奇的事情发生了：

• 下标 i 的节点，左孩子在下标 2i；
• 下标 i 的节点，右孩子在下标 2i+1；
• 反过来，下标 j 的节点（j>1），它的父亲在下标 ⌊j/2⌋（向下取整）。

拿图 9 验证：节点 ② 的下标是 2，左孩子在 2×2=4，右孩子在 2×2+1=5；节点 ③ 的下标是 3，左孩子在 6，右孩子在 7。反着来：下标 6 的节点父亲是 ⌊6/2⌋=3，下标 7 的父亲也是 3。整棵树上上下下的关系，全部被“乘 2、乘 2 加 1、除以 2”三招覆盖，不需要存任何指针，只需要一个数组和这几条下标规则。

为什么只有完全二叉树能做到“零浪费”？因为完全二叉树的层序编号是连续的：从 1 到 n 每个编号都有对应的节点。如果树中间有空洞，比如第 2 层的左孩子空缺，那么层序编号就会出现断档，数组里就必须留空位，要么浪费空间，要么引入复杂的“空洞标记”。普通二叉树强行用数组存，最坏情况下 n 个节点要开 2^n 量级的空间，完全不可行；而完全二叉树（以及堆）恰好避免了所有空洞，是数组存储的天然搭档。

很多编程语言里数组下标从 0 开始，公式会相应变成：下标 i 的节点左孩子在 2i+1、右孩子在 2i+2，父亲在 ⌊(j-1)/2⌋。公式变了，直觉没变：还是“乘 2 找孩子、除 2 找父亲”。实现时先约定好下标从 0 还是 1 开始，全程保持一致即可。

这个“数组二叉树”在第 16 篇讲堆的时候会直接派上用场：堆正是建立在完全二叉树之上的优先队列，建堆、上滤、下滤全都靠 2i 和 2i+1 这两个下标公式在数组里跳来跳去。现在把下标关系记牢，后面学堆会轻松一大半。

4.5 用具体数字感受公式：n = 1、3、7、12 各是什么情况

公式不拿来算数，永远只是符号。我们挑几个具体的 n，把第 4 节的三条性质走一遍。

n = 1：只有根的树，层数 h=1，节点数 1 = 2¹ - 1，是完美二叉树；按边数算高度 H=0，正好落在范围 [⌈log₂2⌉-1, 0] = [0, 0] 里，上限和下限重合——1 个节点的树只有一个形状，没有发挥空间。

n = 3：层数最少是 2（第 1 层 1 个、第 2 层最多 2 个，两层能装 3 个），最多是 3（链状）。边数高度的范围是 [⌈log₂4⌉-1, 2] = [1, 2]。也就是说 3 个节点的树，高度要么是 1（根加两个孩子，满且完全），要么是 2（链）。你可以随手画一画，确认没有第三种高度。

n = 7：层数最少是 3（2³-1=7，正好是完美树），最多是 7（全链）。边数高度范围是 [⌈log₂8⌉-1, 6] = [2, 6]。n=7 是第一个“既能长成完美树、也能退化成链”的非平凡数字，用来对比两种极端形态最合适：完美树查找只要 2 步，链要 6 步。

n = 12：3 层最多 7 个节点、4 层最多 15 个，所以 12 个节点至少需要 4 层；边数高度范围是 [⌈log₂13⌉-1, 11] = [3, 11]。12 个节点的树，高度不可能小于 3，因为 3 层的容量上限 7 装不下 12 个节点——这就是“每层翻倍”决定的容量硬约束。

这种“拿具体数字验算”的习惯非常值得养成：每一个公式都自己挑几个数代入，看看边界（n=1、n=2、刚好满层、刚好多一个节点）是否成立。做一次，比背十遍记得牢。

4.6 完全二叉树的一个隐藏规律：叶子都挤在最后两层的后半段

完全二叉树除了“能塞进数组”，还有一个容易被忽略但非常实用的规律：如果完全二叉树一共有 n 个节点（层序编号 1 到 n），那么编号大于 ⌊n/2⌋ 的节点全部是叶子，编号小于等于 ⌊n/2⌋ 的节点全部不是叶子。换句话说，叶子恰好是编号从 ⌊n/2⌋+1 到 n 的那一批，它们集中在整棵树的“后半段”。

为什么？用下标公式一推就明白。编号 i 的节点如果有左孩子，左孩子编号是 2i。如果 2i > n，说明下标越界，左孩子不存在，那右孩子（2i+1）更不存在，所以 i 是叶子。而 2i > n 等价于 i > n/2，即 i ≥ ⌊n/2⌋+1。反过来，只要 i ≤ ⌊n/2⌋，就有 2i ≤ n（n 为偶数时 2i=n 说明 i 有左孩子；n 为奇数时更宽裕），所以它一定有至少一个孩子，不是叶子。

拿 n=7 验证：⌊7/2⌋=3，编号 4、5、6、7 全是叶子，编号 1、2、3 都有孩子，和完美二叉树完全吻合。拿 n=6 验证：⌊6/2⌋=3，编号 4、5、6 是叶子，编号 3 有左孩子 6——注意这里编号 6 的父节点是 3，与 4.4 的公式互相印证。

这个规律在堆里至关重要：堆排序里“从最后一个非叶子节点开始向下调整”，那个“最后一个非叶子节点”就是编号 ⌊n/2⌋；优先队列的建堆操作从它往前逐个处理，正好覆盖所有可能违规的节点。第 16 篇讲堆时，你会感谢现在记住的这个结论。

4.7 一条主线：所有公式都是“翻倍”的变奏

如果只让你记住这一章的一句话，那应该是：二叉树的一切数学性质，都从“每一层最多翻一倍”长出来。你可以把这一章的四组公式看成一首变奏曲，主题只有一个。

“第 k 层最多 2^(k-1) 个”是主题的第一次陈述：每一层翻倍，翻到第 k 层就是 2 的 k-1 次方。“h 层最多 2^h - 1 个”是主题的第一次变奏：把每一层的上限加起来，等比数列求和得到 2^h - 1，等价的说法是“最后一层比前面所有层加起来还多 1”。“高度范围”是主题的第二次变奏：把公式倒过来解不等式，n 个节点至少要 log₂(n+1)-1 层那么深，因为每层翻倍决定了“层数太少装不下”。“数组下标 2i 和 2i+1”是主题的第三次变奏：层序编号本身就是按 1、2、4、8 的节奏增长，所以父子关系恰好是乘 2 和除 2。

这种“一条主线串起所有公式”的复习方法，比逐个背公式高效得多。考试时就算忘了某个公式，只要记得“每层翻倍”，也能当场推出来：先写第 1 层 1 个，然后每层乘 2，最后把等比数列加起来。推导一遍只要十秒钟，而背错一个指数的代价是整道题全错——所以请务必练习“现场推导”，而不是“背诵结论”。

顺便一提，“翻倍”的直觉不只属于二叉树。计算机里的二分查找、归并排序、快速排序的分治过程，全都是翻倍（或减半）思想的亲戚。你在二叉树里建立的“每层翻倍”的体感，会直接迁移到这些算法的时间复杂度分析上：为什么是 O(log n)？因为每走一步，问题的规模减半；树为什么只有 log n 层？因为每层容量翻倍。数据结构与算法之间这种互相印证的乐趣，是这门学科最迷人的地方之一。

5 二叉树和普通树的区别：为什么算法书默认“树”指二叉树

如果你翻开一本算法书，会发现一个有趣的现象：作者说“今天我们讲树”，结果整章画的全是二叉树；说“树的遍历”，介绍的却是前序、中序、后序；说“树的存储”，给的例子十有八九是 left 和 right 两个指针。为什么普通树明明更自由、更贴近现实，算法书却几乎把“树”和“二叉树”划了等号？这一节把这个问题讲透。

5.1 两者的核心区别

普通树和二叉树最本质的区别有两个：孩子数量不限，以及孩子没有“左右”位置（除非特别说明，普通树的孩子集合是无序的）。围绕这两个区别，派生出一系列连锁差异。

第一，结构上的差异。普通树的节点可以带任意多个孩子，所以它的形状千变万化，同一个父节点的孩子们没有先后之分；二叉树每个节点最多两个孩子，并且左右是两个不同的槽位，形状被限制在“二分”的框架里。

第二，定义上的差异。普通树很难给出干净的递归定义——一棵普通树是“一个根加上若干棵子树”，这个“若干”是不确定的；二叉树则能写成“一个根加一棵左子树加一棵右子树”，左、右各就各位，定义天然递归。

第三，遍历上的差异。普通树没有“前序、中序、后序”这种整齐的三种走法，因为孩子数量不固定，“中序”的位置根本没有意义；二叉树因为只有左右两个槽位，访问顺序可以清晰地分成“根、左、右”的排列组合，从而演化出标准的三种深度优先遍历。这也是为什么第 5 篇的遍历教学几乎全在二叉树上进行。

第四，存储上的差异。普通树存孩子通常要用孩子链表、孩子数组或“第一个孩子 + 下一个兄弟”之类的结构；二叉树只需要两个指针（或两个数组下标）就能完整表达结构，实现简单、内存规整、缓存友好。

第五，数学上的差异。二叉树有 2^(k-1)、2^h-1、n₀=n₂+1 这一整套漂亮的计数公式，可以精确分析高度、节点数、复杂度；普通树的分析则要借助“转化为二叉树”来间接完成。数学上“可分析”，是计算机科学选择二叉树的最深层次原因。

为了把差异看得更清楚，可以用一个表格快速对照：

对比维度	普通树	二叉树
孩子数量	不限，可以 0 到任意多个	最多 2 个
孩子顺序	通常无序	严格区分左孩子、右孩子
递归定义	根 + 若干子树，“若干”不定	根 + 左子树 + 右子树，位置固定
遍历方式	无统一的三序遍历	前序、中序、后序、层序
存储实现	孩子链表、孩子数组等	左右指针或数组下标
数学性质	较少，需转换后分析	层数、高度、节点数公式完整
典型应用	文件系统、组织架构、Trie	堆、BST、表达式树、哈夫曼树

5.2 多叉树也能“翻译”成二叉树：孩子兄弟表示法

普通树和二叉树之间的鸿沟，其实没有想象中那么大。任何一棵普通树都可以无损地转换成二叉树，最经典的方法叫孩子兄弟表示法（first-child / next-sibling），思路非常巧妙：把普通树里“第几个孩子”的横向关系，翻译成二叉树的“右孩子”关系；把“父子”的纵向关系，翻译成二叉树的“左孩子”关系。

具体规则只有两条：每个节点只保留它的第一个孩子作为二叉树的左孩子；每个节点的下一个兄弟作为二叉树的右孩子。经过这样的转换，一棵孩子再多、再杂的普通树，都能变成一棵规规矩矩的二叉树，而且信息没有任何丢失：从任意节点出发，沿着左指针能找到它的第一个孩子，再沿着右指针能找到它的兄弟姐妹。

转换后的读法很直接：任意节点沿左指针下去是它的第一个孩子，沿右指针过去是它的下一个兄弟；A→B→C→D 的链把“A 的三个孩子”完整保存下来，E→F 的右链则保存了“E 的兄弟 F”，所以普通树的全部信息都没有丢失。

孩子兄弟表示法告诉我们两件事。第一，二叉树并不比普通树“小”——它表达能力足够强，任何树都能装进二叉树这个壳子里；第二，很多针对普通树的算法（比如遍历、统计高度），都可以先转换成二叉树再做，通用性没有损失。这个表示法也是第 4 篇《树的存储方式》里的重头戏，这里先混个脸熟。

5.3 为什么算法书默认“树”指二叉树

原因可以归纳成五条。

第一，教学效率。二叉树的形态最少、规则最清晰，最适合作为“树”的入门模型。先学会二叉树，再学普通树、多叉树、图，是一条平滑的坡度；反过来从最自由的多叉树入手，反而容易迷失在“孩子数量不定”的细节里。

第二，分析方便。计算机科学本质上很在乎“能不能证明”。二叉树的层数、高度、节点数、复杂度全都算得清清楚楚，教材可以把“为什么查找是 O(log n)”写成完整推导；普通树的复杂度分析则绕不开“先二叉化”。

第三，应用广泛。堆、二叉搜索树、AVL 树、红黑树、哈夫曼树、表达式树、决策树……数据结构教科书里的“名角”几乎全是二叉树。掌握了二叉树，等于掌握了算法世界的半壁江山。

第四，实现简单。二叉树只要 left、right 两个指针，插入、删除、遍历的代码短小精悍；普通树要维护动态的孩子集合，代码和内存管理都复杂一截。对教材和读者来说，“简单可复现”本身就是巨大的优势。

第五，表达力足够。上一节的孩子兄弟表示法说明，普通树能表达的东西，二叉树都能表达；反过来，二叉树能表达的东西，普通树当然也能表达。既然大家表达力一样，教材自然选择结构更简单、分析更顺手的那一个。

不过要补充一句公道话：“默认树指二叉树”只是教材的简化，不是工程的真相。数据库索引用的 B 树、B+ 树是多叉树，文件系统目录是任意多叉树，路由表里的前缀树（Trie）每个节点有几十个孩子。真实世界需要什么样的树，就选什么样的树；算法书先带你吃透二叉树，是为了让你以后看这些更复杂的树时，能立刻抓住“高度、平衡、检索”这些共性。

5.4 一个容易混淆的概念：二叉树不是“普通树的子类”

最后纠正一个常见的思维误区：很多人以为“二叉树是普通树的一种”，因为“二”听起来像是“多”的特例。严格地说，这个说法不够准确。二叉树除了限制孩子数量，还额外规定了“左右有序”；而普通树通常不区分孩子的顺序。所以二叉树和普通树更像是两个有重叠的集合：孩子不超过两个且无序的树，既是普通树又是“度受限树”；但一棵只有左孩子、没有右孩子的二叉树，放在普通树的视角里，和“只有一个孩子”的普通树看起来相同，在二叉树视角里却独占一个位置。简单记法：二叉树 = 度不超过 2 + 左右有序 + 空子树合法，三个条件缺一不可。搞清这一点，很多“这棵树是不是二叉树”的判断题就不会再纠结。

5.5 面试常问的三连问：把这一章浓缩成对话

这一章的知识点，在算法面试里几乎每次都会以不同面目出现。我们把最常见的三个问题连同回答思路写出来，你甚至可以找朋友模拟一问一答。

问：二叉树和普通树有什么区别？ 答：三个层面。结构上，二叉树每个节点最多两个孩子且区分左右，普通树孩子数量不限、通常无序；定义上，二叉树可以干净地递归定义（根 + 左子树 + 右子树），普通树是“根 + 若干子树”；使用上，二叉树有标准的三序遍历和完整的计数公式，适合分析，普通树则需要转成二叉树（如孩子兄弟表示法）才能套用这些工具。

问：为什么很多教材默认“树”就是指二叉树？ 答：因为二叉树结构最简单、数学性质最完整、实现最方便，又能通过孩子兄弟表示法无损表达任意普通树；堆、BST、AVL、红黑树等核心数据结构都以二叉树为骨架。所以教材先用二叉树建立“树”的直觉，再扩展到多叉树（B 树、Trie 等）。

问：满二叉树、完全二叉树、完美二叉树是什么关系？ 答：完美二叉树一定是满的也是完全的；满二叉树不一定完全，完全二叉树不一定满；两者的交集除了完美二叉树，还包括“最后缺了右侧几个节点、但没有任何独生子”的特殊形态（比如 5 个节点那种树）。判断口诀：满看“有没有独生子”，完全看“按层从左到右连不连续”，完美看“每层是不是都满”。

这三个问题答顺了，说明你对第 3 章和第 5 章的理解已经到位。别满足于背答案，试着用自己的话讲给一个完全不懂的人听——能讲明白，才是真懂。

6 二叉树的三种遍历预告：前序、中序、后序

“遍历（traversal）”是树的头号基本功：把树里的每一个节点都访问一次，而且只访问一次。线性表（数组、链表）的遍历只有一种主流走法——从头到尾；树的遍历却有很多种，因为树有“根、左子树、右子树”三个部分，先访问谁、后访问谁，可以排出不同的顺序。

6.1 为什么正好是“前、中、后”三种

二叉树里只有三样东西可以安排顺序：访问根节点（记为 D，D 表示“数据/节点本身”）、左子树（L）和右子树（R）。按照“先左后右”的通行约定（不先左后右也可以，但约定俗成），把“访问根”这个动作插进“遍历左子树、遍历右子树”这两个动作之间，就得到三种标准顺序：

• 前序遍历（preorder）：根 → 左子树 → 右子树，顺序是 DLR；
• 中序遍历（inorder）：左子树 → 根 → 右子树，顺序是 LDR；
• 后序遍历（postorder）：左子树 → 右子树 → 根，顺序是 LRD。

“前、中、后”三个字，说的是根被访问的位置：根在最前，就叫前序；根在中间，就叫中序；根在最后，就叫后序。注意，“前序”不是“从前往后走”的意思，“中序”也不是“按大小排好序”的意思——它们描述的是根的相对位置，这一点很多初学者会误解。

6.2 每种遍历适合干什么：先建立一个模糊印象

虽然第 5 篇才会详细展开，但提前知道“每种遍历擅长什么”，能帮你建立方向感。

前序遍历的顺序是“先根后子树”，这意味着在访问一个节点时，它的祖先们都已经访问过了。这个特性让前序遍历特别适合复制一棵树（先建根，再递归复制左右子树）、序列化（把树存成字符串再恢复）、以及打印目录结构（先打印文件夹，再打印里面的子文件夹）。

中序遍历的顺序是“左根右”。如果一棵树是二叉搜索树（左小右大），中序遍历恰好能把所有节点按从小到大输出。所以中序遍历是 BST 的“排序接口”：想验证一棵树是不是 BST，中序遍历一遍看是否严格递增即可。这个性质在第 7 篇讲 BST 时会反复使用。

后序遍历的顺序是“先子树后根”，访问根的时候，左右子树的所有信息都已经算完了。这个特性让它特别适合自底向上地计算：统计每棵子树的高度、节点数、总和，删除一棵树（先删孩子再删自己），以及表达式树求值（先算左右子树的结果，再用根上的运算符合并）。

除了这三种深度优先遍历，还有一种广度优先的层序遍历（level-order / BFS）：按层从上到下、每层从左到右访问，正好对应第 4.4 节那个“层序编号”的顺序。层序遍历在判断完全二叉树、寻找树的“最浅深度”时非常有用。第 5 篇会把五种常见走法（前、中、后、层序，外加非递归版）全部讲透，包括如何用栈模拟递归、如何用队列实现层序、如何根据两种遍历序列反推一棵树，这里先按下不表。

6.3 遍历顺序对同一棵树的变化：一个预告示例

为了让你对“三种顺序真的不一样”有体感，看一棵只有 3 个节点的小树：根是 A，左孩子 B，右孩子 C。

• 前序：A → B → C；
• 中序：B → A → C；
• 后序：B → C → A。

同一个结构，三种走法输出三个不同的序列。反过来，这也意味着：给定一个序列，不一定能唯一确定一棵二叉树；但给定“前序 + 中序”或“后序 + 中序”两个序列，通常就能把树唯一地复原出来。这是很多算法面试题的考点，也是第 5 篇会专门训练的能力。现在你只需要记住一句话：遍历的顺序 = 根的位置，剩下的细节留给下一篇。

6.4 三行代码的直觉：伪代码预告

三序遍历之所以好写，是因为递归定义给了我们一份现成的“模板”。用伪代码写出来，三种遍历的差别小得惊人：

前序(node)：访问 node；前序(node.left)；前序(node.right)
中序(node)：中序(node.left)；访问 node；中序(node.right)
后序(node)：后序(node.left)；后序(node.right)；访问 node

三个函数结构完全一样，唯一不同的是“访问 node”这一行放在哪里：最前是前序，中间是中序，最后是后序。递归会自动保证：子树里的每个节点都被完整地遍历完，才轮到下一句代码。所以前序里的“访问 node”只会发生在左右子树都被访问之前，后序里的“访问 node”只会发生在左右子树都被访问之后——顺序不会乱，这是递归的功劳，也是二叉树“树中有树”的回报。

把这个模板翻译成实际语言（C、Java、Python、JavaScript 都行），大约只需要十行左右。第 5 篇会在此基础上加两种进阶版本：一种是用显式栈模拟递归，避免递归过深导致栈溢出；另一种是用队列实现层序遍历。到时候你会发现，所有遍历的实现都是从这个三行模板长出来的。

一个提前想清楚的问题：为什么中序遍历二叉搜索树能输出有序序列？因为 BST 的左子树小于根、右子树大于根，而中序的顺序是“左、根、右”，正好把“小于、等于、大于”三段拼在一起；递归地对每一棵子树套用同样规则，整棵树就按从小到大排好了。这个“中序 = 有序”的对应关系，是 BST 系列文章里最常用的工具之一，现在先在脑子里种下。

7 现实例子：二叉树在计算机世界里无处不在

前面讲的都是“树的数学”，这一节来看“树的生活”。表达式树、决策树、哈夫曼树、二叉搜索树，是四个最典型的现实应用。它们共享同一个二叉树骨架，只是每个节点里装的“内容”和“规则”不同。看完这一节你会发现：二叉树不是课本里的抽象玩具，而是编译器、压缩软件、搜索引擎和人工智能背后天天运转的零件。

7.1 表达式树：把算式画成一棵树

计算机要计算 (3 + 4) × 5 - 6 这个算式，第一步不是直接按顺序算，而是先把表达式“解剖”成结构。解剖结果就是一棵表达式树（expression tree）：叶子节点放数字，内部节点放运算符，每个运算符的两个操作数分别放在它的左子树和右子树里。

表达式树完美体现了二叉树“左右有序”的意义：3 - 4 和 4 - 3 是两棵镜像不同的树，计算结果也完全不同。所以表达式树里左子树、右子树的位置绝对不能颠倒。这也解释了为什么第 2 节要反复强调“左右是语义”。

表达式树怎么“读出”结果？有三种方式，正好对应第 6 节的三种遍历。中序遍历输出 3 + 4 × 5 - 6（严格说还要按运算符优先级补括号，比如 (3 + 4) × 5 - 6），是人看的写法；后序遍历输出 3 4 + 5 × 6 -，这是计算机最喜欢的后缀表达式，可以用一个栈从左到右扫描直接求值，不需要考虑括号和优先级；前序遍历输出 - × + 3 4 5 6，常用于把表达式序列化存储。你看，上一节预告的遍历，在这一节立刻就有了实际用途——编译器把源代码变成抽象语法树（AST），再靠遍历来生成机器码或求值，整个过程和这棵小树的道理一模一样。

7.2 决策树：一路“是/否”走到结论

如果你用过“智能客服”，或者见过医疗诊断小程序，大概率已经见过决策树（decision tree）：每个内部节点是一个问题，每条边是一个答案（通常是“是/否”），每个叶子是一个结论。用户从根出发，回答一个问题走一个分支，直到抵达叶子，就得到最终答案。

为什么决策树偏爱二叉？因为“是/否”是人类和机器都能轻松回答的二选一。把一个问题拆成多个选项（比如“晴天、多云、下雨、下雪”），可以展开成多棵二叉决策树的组合（先问“下不下雨”，再问“是不是多云”），而每个节点始终保持二选一，代码和判断逻辑都最简洁。机器学习里的决策树分类器正是这个思路的规模化版本：算法自动从数据里挑出“最能区分样本”的问题作为根节点，一层层往下分裂，直到叶子里的样本足够“纯净”。一棵训练好的决策树，本质上就是一份人类能读懂的“规则说明书”，这也是它比神经网络更“可解释”的原因。

7.3 哈夫曼树：压缩文件背后的“按频率分长短”

数据压缩里有一个经典问题：一段文本里有 26 个字母，频率差别很大，怎么给每个字母设计二进制编码，让整段文本最短？如果用定长编码（每个字母固定 8 位），实现简单但浪费；如果用变长编码（高频字母用短码、低频字母用长码），就需要保证一个字母的编码不是另一个字母编码的前缀，否则解码时会产生歧义。满足这个条件的编码叫前缀码（prefix code）。

**哈夫曼树（Huffman tree）**就是构造“最优前缀码”的机器。构造方法极其简单：把每个字符当成一棵只有根节点的树，权值就是它的出现频率；重复执行“挑出权值最小的两棵树，合并成一棵新树，新树的权值等于两者之和”，直到只剩一棵树。合并的顺序保证了一个关键结论：出现频率越高的字符，离根越近、编码越短；频率越低的字符，离根越远、编码越长。整棵树的加权路径长度（每个叶子频率 × 路径长度之和）在所有前缀码方案中最小，所以哈夫曼编码是某种意义下的“最优压缩”。

合并规则是“每次挑频率最小的两棵树”：4 和 5 先合成 9，9 再和 12 合成 21，13 和 21 最后合成 34。正是因为低频字符被优先往下合并，它们离根最远、编码最长，而高频的 A、B 离根最近、编码最短。

注意哈夫曼树的形状：每个内部节点恰好有两个孩子，绝无独生子——它天然是一棵满二叉树。这并非巧合：如果某个内部节点只有一个孩子，那完全可以把它和孩子合并，让树更“扁”、编码更短，所以最优方案里不可能出现独生子。这也回应了第 3 节：满二叉树不只是一个名词，它在“最优性”证明里扮演着实质角色。zip、JPEG、PNG 等压缩格式，底层都活跃着哈夫曼编码的身影。

7.4 二叉搜索树（BST）：为“查找”而生

最后一个例子是本系列的“主角预告”：二叉搜索树（Binary Search Tree，BST）。它的规则只有一条，却威力巨大：对于任意节点，左子树里所有节点的值都小于它，右子树里所有节点的值都大于它。

在 BST 里查找一个值，过程就像走迷宫：从根出发，目标比当前节点小就向左走，比当前节点大就向右走，相等就找到了。每一次比较都排除掉一整棵子树，这正是第 1 节说的“二分”思想的树形实现。如果树长得匀称，查找一次只需要 O(log n) 步；但如果不幸长成退化形态（比如按从小到大的顺序依次插入），查找就退化成 O(n)，和链表没有区别。

为了永远保持“匀称”，人们发明了各种自平衡二叉搜索树：AVL 树通过旋转让任意节点的左右子树高度差不超过 1，红黑树用颜色规则近似平衡，B 树则让每个节点携带多个键来降低高度。这些树全都建立在二叉搜索树的地基上——而二叉搜索树又建立在本篇的“二叉树”地基上。后面第 7、8、9 篇会一栋一栋地把这栋大楼盖起来。

如果你想亲眼看看 BST 是怎么查找的，可以打开查找实验室，后面讲 BST、AVL、红黑树时都能在这里看到动画演示：每一步比较、每一条路径、每一次旋转，都会在可视化里慢慢走给你看。先把本文的概念消化掉，再去实验室“玩”，效果最佳。

7.5 更多二叉树的身影：比赛、语法与索引

除了前面四个经典例子，二叉树还在更多你未必注意过的地方出现。

比赛对阵表（tournament tree）：单败淘汰赛的赛程天然是一棵完美二叉树，选手在叶子，比赛在内部节点，冠军就是根。这类“锦标赛树”还被计算机用来做并行比较：比如在一堆数据里同时找最大值和次大值，可以先把比较过程组织成一棵比赛树，让输给冠军的那些选手互相比较，从而减少比较次数。你看，体育赛制稍加抽象，就成了算法。

语法分析树（parse tree）：编译器解析源代码时，会把 if 语句、循环、表达式组织成一棵语法树：根是语句类型，子节点是它的组成部分。表达式树只是语法树的一个特例。语法树帮助编译器回答“这段代码到底是什么意思”：优先级、结合性、作用域全都体现在树的形状里，遍历它就能生成中间代码。理解了表达式树，就理解了编译器三分之一的骨架。

二叉堆（binary heap）：第 16 篇的主角，本质就是一棵“用数组装的完全二叉树”，再加一条“父节点总比孩子大（或小）”的规则。优先队列、堆排序、Dijkstra 最短路算法都用它。它的全部操作——插入、取最值、调整——都建立在 4.4 节那两条下标公式上。可以说，没有完全二叉树，就没有堆。

B 树与 B+ 树：数据库索引常用的多叉树。它们不是二叉树，但理解二叉树的人看它们会轻松得多：B 树相当于把二叉树的“二路分裂”升级成“多路分裂”，让每个节点装多个键，从而把树的高度压得更低，减少磁盘访问次数。二叉树的“高度越低越好”这个直觉，在多叉树里得到了极致发挥。

还有网络路由用的前缀树、游戏 AI 里的行为树、JSON 和 XML 解析时隐含的树形嵌套……你会发现，一旦戴上二叉树的眼镜，世界上的分层结构几乎都带着树的影子。计算机科学选择二叉树，不是因为它漂亮，而是因为它恰好站在“简单”与“强大”的交点上：规则少到极致，表达力却不输任何树。这也是本系列把它放在“最受宠”位置的原因。

8 性质速查表：一篇浓缩成一张表

读完正文，把最重要的结论集中在一张表里。复习时先遮住“直觉与备注”一列，试着只看公式能不能想起来为什么。

性质	公式 / 结论	直觉与备注
第 k 层最多节点数	2^(k-1)	根是第 1 层；每一层最多翻一倍
h 层二叉树最多节点数	2^h - 1	等比数列求和；完美二叉树达到上限
n 个节点的高度范围（边数）	⌈log₂(n+1)⌉ - 1 到 n-1	最矮靠“每层翻倍”，最高靠“退化成链”
叶子与二度节点关系	n₀ = n₂ + 1	数边两遍即可证明；满二叉树特化为 n₀ = n₂ + 1
满二叉树	每个节点 0 或 2 个孩子	无独生子；非空时节点数为奇数
完全二叉树	除最后一层外全满，最后一层从左到右连续	可无损存进数组
完美二叉树	每一层都铺满	既是满的也是完全的；节点数恰为 2^h - 1
退化二叉树	每个节点最多一个孩子	链状，查找 O(n)，是“坏形状”的极端
数组存储（下标从 1 开始）	父 i → 左 2i、右 2i+1；子 j → 父 ⌊j/2⌋	只适用于完全二叉树；堆的地基
三种深度优先遍历	前序 DLR / 中序 LDR / 后序 LRD	“前中后”指根被访问的位置
二叉搜索树查找	平衡时 O(log n)，退化时 O(n)	左小右大；AVL、红黑树负责保持平衡

这张表不是让你背的，而是用来“自检”的：每一个条目，你都应该能用自己的话解释它为什么成立。解释不出来，就回到对应的章节再读一遍——尤其是第 4 节那三个公式，它们是整张表的心脏。

9 自测题：检验你的二叉树直觉

10 下一篇预告：《树系列第 4 篇：树的存储方式》

这一篇我们认识了二叉树的定义、形态和数学性质，但始终有一个问题没有回答：树在计算机里到底怎么存？ 指针、数组、孩子链表、孩子兄弟表示法……不同的存储方式决定了插入、删除、查找的代价，也决定了哪些树“适合”哪些场景。

下一篇《树系列第 4 篇：树的存储方式》将讲清楚：顺序存储和链式存储各有什么优劣；普通树怎么用孩子表示法、孩子兄弟表示法落地；二叉树为什么既能用指针存、也能用数组存；以及第 4.4 节埋下的“2i 和 2i+1”到底怎么写成真正的代码。到那时，你对“树”的理解就会从纸面概念变成能跑起来的数据结构。

在那之前，建议你带着这张速查表，去查找实验室里逛一圈：看看二叉搜索树的查找路径是不是真的“每走一步就排除一半”，也看看退化形态下它是不是真的慢成链表。看得越多，下一篇文章里的代码就越亲切。