第13章二叉树

课程目录第13章二叉树

二叉树：从定义到性质，一次说透

各位同学，今天我们来聊聊二叉树。说实话，二叉树是我在数据结构里用得最多的结构之一。无论是做编译器里的语法树，还是写网络协议里的路由表，二叉树的身影无处不在。我个人习惯把二叉树看作是「链表的分叉进化版」——每个节点不再只有一个 next，而是有了 left 和 right 两个指针。

先给个严谨的定义：二叉树是每个节点最多有两个子树的树结构。注意这个「最多」，也就是说，一个节点可以有 0 个、1 个或 2 个子节点。

用 C 语言表示一个二叉树节点，我通常会这样写：

typedef struct TreeNode {
    int data;                // 数据域
    struct TreeNode *left;   // 左孩子指针
    struct TreeNode *right;  // 右孩子指针
} TreeNode;

嗯，就这么简单。每个节点存一个数据，再加两个指针。你想想看，这和双向链表是不是有点像？只不过双向链表是前后两个指针，二叉树是左右两个指针。但它们的逻辑结构完全不同——链表是线性的，二叉树是非线性的。

小提示：我在项目中见过有人把二叉树节点定义成三个指针（加一个 parent），其实大多数场景下没必要。除非你要频繁回溯父节点，否则两个指针就够了。

二叉树有很多种形态，但有三种特殊的二叉树，你必须记住。为什么？因为它们的性质直接决定了算法的效率。

说白了，斜树就是所有节点都偏向一边的二叉树。如果所有节点只有左孩子，叫左斜树；只有右孩子，叫右斜树。

你想想看，斜树长什么样？其实就是个链表。每个节点只有一个孩子，深度等于节点数。我在早期写代码时犯过一个错误——把一个二叉搜索树插成了斜树，结果查找效率从 O(log n) 直接掉到了 O(n)。

避坑指南：我曾经在项目中用二叉搜索树做字典，插入数据时没有做平衡处理，结果数据恰好是递增的，树变成了右斜树。查找一个单词花了 O(n) 时间，用户反馈说「卡死了」。后来我换成了 AVL 树才解决。所以，斜树是二叉树的退化形态，实际工程中要尽量避免。

满二叉树，也叫完美二叉树。它的定义是：除了叶子节点外，每个节点都有两个子节点，并且所有叶子节点都在同一层。

举个例子，深度为 3 的满二叉树，节点总数是 1 + 2 + 4 = 7 个。每一层的节点数都是满的，没有空缺。

满二叉树有什么好处？它的空间利用率最高，没有浪费的指针。我在做堆排序时，底层就是用满二叉树（实际上是完全二叉树）来实现的。

完全二叉树比满二叉树稍微宽松一些。它的定义是：除了最后一层外，其他层都是满的，并且最后一层的节点都靠左排列。

你想想看，满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。比如深度为 3 的完全二叉树，最后一层可以只有 1 个节点，但必须靠左放。

为什么完全二叉树这么重要？因为它可以用数组来存储，不需要指针。堆排序、优先队列的底层都是完全二叉树。我在项目中用数组实现完全二叉树时，索引计算特别方便：

// 用数组存储完全二叉树
// 父节点下标为 i，则：
// 左孩子下标 = 2*i + 1
// 右孩子下标 = 2*i + 2
// 父节点下标 = (i-1)/2

  核心记忆点：完全二叉树是「用数组存树」的基础。如果你理解了这一点，堆排序的代码你一眼就能看懂。

二叉树有 5 条重要性质，我建议你背下来。为什么？因为很多算法题和面试题都直接考这些性质。

我个人觉得性质3是最容易被忽略的。有一次我在做树的序列化时，需要判断一棵树是不是合法的二叉树，就用到了 n0 = n2 + 1 这个关系。你想想看，如果一棵树有 10 个叶子节点，那度为 2 的节点一定是 9 个，加起来就是 19 个节点。这个性质在验证树结构时特别有用。

记忆技巧：性质3可以这样理解——每增加一个度为2的节点，就会多出一个叶子节点。因为一个度为2的节点会「消耗」一个叶子节点（作为父节点），但又「产生」两个新的叶子节点，净增1个。

下面我用一张图来总结本章的核心内容。这张图展示了二叉树的分类体系以及它们之间的关系：

这张图把二叉树的知识点串起来了。你从根节点往下看，左边是定义和存储方式，中间是三种特殊形态，右边是五大性质。最下面那条总结是我特别想强调的——完全二叉树是连接「树」和「数组」的桥梁，理解了这一点，堆排序、优先队列这些高级内容你就能轻松拿下。

好了，关于二叉树的定义、特殊形态和性质，我们就聊到这里。记住，斜树是退化形态要避免，满二叉树是理想形态，完全二叉树是工程中最实用的。下一节我们会深入二叉树的遍历，到时候我会分享一些我在实际项目中踩过的坑。