二叉树入门：性质、存储与代码实现

从生活中的例子引入

假设你们班要选出班长，老师让每个人做自我介绍，然后全班投票。为了让投票过程公平又高效，老师想了一个办法：每次把班级分成两组，每组再继续分成两个小组，直到每个小组只有一个人。这样层层分组的结构，就像一棵“二叉树”——每个节点最多分出两个叉（两个分支）。再比如，一场网球比赛，每一场比赛淘汰一个人，最后的冠军就是树的根，每一轮的对阵图就是一棵二叉树。

树结构在生活中随处可见：学校的行政体系从校长到年级组长到班主任；电脑里的文件夹一层套一层；甚至你手机里的通讯录分组——但它们大多允许一个节点有任意多个子节点。而二叉树是所有树结构里最重要的一种，因为它足够简单：每个节点最多只有两个子节点，分别叫做“左孩子”和“右孩子”。这种约束让很多运算变得非常简单，像堆排序、二叉搜索树、哈夫曼树等都用到了它。

二叉树是什么？为什么它这么重要？

什么是二叉树？

二叉树（Binary Tree） 是每个节点最多有两个子树的树结构。这两个子树通常称为左子树和右子树，并且左右顺序是固定的，不能随意交换。也就是说，如果你把左孩子和右孩子互换了，这棵树就变成了另一棵不同的二叉树。下图是一棵标准的二叉树：

         A
       /   \
      B     C
     / \   / \
    D   E F   G

在这个图中，A有两个孩子B和C；B有两个孩子D和E；C有两个孩子F和G；D、E、F、G都没有孩子，是叶子节点。

特点：

每个节点最多只有两个分支（所以叫“二叉”）。
左孩子和右孩子是有序的：即使你交换了B和C的位置，也代表不同的树（除非不考虑顺序，但通常二叉树都是有序的）。
树中不能有环（这是所有树的基本要求）。

特殊形态的二叉树

满二叉树：所有叶子节点都在同一层，并且每个非叶子节点都有两个子节点。上面这棵树有3层，最后一层有4个叶子，就是一棵满二叉树。满二叉树长得非常“对称”，它的节点总数是固定的：如果深度为k，那么有 (2^k) - 1 个节点。
完全二叉树：除最后一层外，其他层都是满的，并且最后一层的叶子从左到右依次排列，中间没有空缺。比如下面这棵树就是完全二叉树：

注意：第3层（最后一层）的最右边缺少一个节点G，但节点F紧挨着E，中间没有空位。完全二叉树可以用数组非常紧凑地存储，因为它的节点编号和数组下标有很直接的对应关系。下节课我们会专门讲完全二叉树。

二叉树的重要性质（数学家们发现的规律）

这些性质就像乘法口诀一样，记住它们能帮你快速解题、设计算法。

性质1：第i层上最多有 2^(i-1) 个节点（i >= 1）。 推导：根节点在第1层，最多1个 = 2^0；第2层最多2个 = 2^1；第3层最多4个 = 2^2；所以第i层最多 2^(i-1) 个。你可以想象，每一层最多比上一层多一倍，就像细胞分裂一样。

性质2：深度为k的二叉树最多有 (2^k) - 1 个节点（k >= 1）。 推导：每层节点数加起来：2^0 + 2^1 + ... + 2^(k-1) = 2^k - 1。这就是满二叉树的节点总数。比如深度为3，最多有 2^3 - 1 = 7 个节点。如果一棵树有100个节点，你就能算出它最深可能是多少层（用性质4）。

性质3：对于任何二叉树，叶子节点数 = 度为2的节点数 + 1。 用公式表示：n0 = n2 + 1（n0是叶子数，n2是有两个孩子的节点数）。这个性质很有趣，你可能觉得“为什么会有这个关系？”我们一步步来推理：

设总节点数为 n，度为0的节点数 n0，度为1的节点数 n1，度为2的节点数 n2，那么：

n = n0 + n1 + n2 （总人数 = 三种不同“孩子数”的节点之和）
所有节点的度数之和 = 0×n0 + 1×n1 + 2×n2 = n1 + 2n2
而度数之和等于边数（每条边连接一个父节点和一个子节点），边数又等于总节点数 - 1（因为根节点没有入边）： n1 + 2n2 = n - 1
将第一个式子 n = n0 + n1 + n2 代入第二个式子： n1 + 2n2 = (n0 + n1 + n2) - 1
化简得： 2n2 = n0 + n2 - 1 → n0 = n2 + 1

你可以试着在上面的满二叉树中验证：n0 = 4（D、E、F、G），n2 = 3（A、B、C），4 = 3 + 1，成立。再试试完全二叉树：叶子节点D、E、F共3个，有两个孩子的节点A、B共2个（C只有一个孩子），3 = 2 + 1，也成立。

性质4：具有n个节点的完全二叉树，深度为 floor(log₂ n) + 1。 比如 n=5，log₂5≈2.32，floor=2，+1=3，深度为3。你可以画一棵有5个节点的完全二叉树验证。

这些性质在做题和设计算法时很有用。比如给你一棵二叉树的节点总数，你就能算出最多有多少层（性质2反过来）。或者给你一些节点度数信息，就能求出叶子节点数量。

二叉树的存储方式

二叉树有两种常见的存储方式：顺序存储（数组）和链式存储（指针）。它们各有优缺点。

1. 链式存储

每个节点是一个结构体，里面包含数据域、左孩子指针、右孩子指针。这种存储方式非常灵活，适合动态插入和删除节点。你可以在程序中任意时刻添加或删除节点，而不用担心数组大小不够。缺点是需要额外的指针空间（尤其在32位系统上，每个指针占4字节），而且访问随机节点（比如第k个节点）需要沿着指针走，不如数组快。

2. 顺序存储

用一个数组来存储二叉树节点，数组下标与节点位置有对应关系。对于完全二叉树，顺序存储特别节省空间，而且能通过下标快速找到父子关系。具体做法是：根节点放在下标1（或0），左孩子放在2i（或2i+1），右孩子放在2i+1（或2i+2）。对于非完全二叉树，顺序存储会浪费大量空间（因为要留空位给缺失的节点）。这种存储我们在讲完全二叉树时会详细展示。

下面我们先实现链式存储，因为通用性最强，也最容易理解。

C++代码实现：链式存储二叉树

我们定义一个BinaryTreeNode结构体，包含data, left, right三个成员。然后手动创建上面那棵树（满二叉树，3层）。代码中每一步都有中文注释，方便你对照。

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct BinaryTreeNode {
    char data;                          // 节点数据，用字符表示
    BinaryTreeNode *left;               // 左孩子指针
    BinaryTreeNode *right;              // 右孩子指针

    // 构造函数：初始化数据和左右指针为空
    BinaryTreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    // 创建叶子节点
    BinaryTreeNode* nodeA = new BinaryTreeNode('A');
    BinaryTreeNode* nodeB = new BinaryTreeNode('B');
    BinaryTreeNode* nodeC = new BinaryTreeNode('C');
    BinaryTreeNode* nodeD = new BinaryTreeNode('D');
    BinaryTreeNode* nodeE = new BinaryTreeNode('E');
    BinaryTreeNode* nodeF = new BinaryTreeNode('F');
    BinaryTreeNode* nodeG = new BinaryTreeNode('G');

    // 连接节点构建二叉树
    nodeA->left = nodeB;                // A的左孩子是B
    nodeA->right = nodeC;               // A的右孩子是C
    nodeB->left = nodeD;                // B的左孩子是D
    nodeB->right = nodeE;               // B的右孩子是E
    nodeC->left = nodeF;                // C的左孩子是F
    nodeC->right = nodeG;               // C的右孩子是G

    // 验证：输出根节点的左右孩子
    cout << "根节点: " << nodeA->data << endl;
    cout << "左孩子: " << nodeA->left->data << endl;
    cout << "右孩子: " << nodeA->right->data << endl;
    cout << "左孩子的左孩子: " << nodeA->left->left->data << endl;

    // 释放内存（递归删除略，这里手动释放所有节点）
    delete nodeD; delete nodeE; delete nodeB;
    delete nodeF; delete nodeG; delete nodeC;
    delete nodeA;
    return 0;
}

⚠️ 新手常犯错误：

忘记将节点的 left 和 right 初始化为 nullptr（C++中未初始化的指针是野指针，访问会崩溃）。我们已经在构造函数中初始化了，但如果你手动赋值时忘了，就会出问题。

在访问 nodeA->left->data 之前没有检查 nodeA->left 是否为 nullptr。如果 nodeA 没有左孩子，程序会崩溃。本例中我们已经确保有左孩子，但实际编程中一定要先判断。

释放内存时容易重复 delete 或漏 delete。例如上面我们手动删除了所有节点，但如果你用递归删除函数会更安全（后面会讲）。另外，如果使用了 new，一定要配套 delete，否则会造成内存泄漏。

混淆 left 和 right 的顺序：比如把左孩子挂到了右指针上，树的结构就变形了。在构建时一定要仔细核对。

Python代码实现：链式存储二叉树

Python同样使用类，每个节点保存左、右子节点的引用。不需要手动管理内存，更简单。

class BinaryTreeNode:
    def __init__(self, data):
        self.data = data          # 节点数据
        self.left = None          # 左孩子
        self.right = None         # 右孩子

# 创建节点
nodeA = BinaryTreeNode('A')
nodeB = BinaryTreeNode('B')
nodeC = BinaryTreeNode('C')
nodeD = BinaryTreeNode('D')
nodeE = BinaryTreeNode('E')
nodeF = BinaryTreeNode('F')
nodeG = BinaryTreeNode('G')

# 连接
nodeA.left = nodeB                # A的左孩子是B
nodeA.right = nodeC               # A的右孩子是C
nodeB.left = nodeD                # B的左孩子是D
nodeB.right = nodeE               # B的右孩子是E
nodeC.left = nodeF                # C的左孩子是F
nodeC.right = nodeG               # C的右孩子是G

# 验证
print("根节点:", nodeA.data)
print("左孩子:", nodeA.left.data)
print("右孩子:", nodeA.right.data)
print("左孩子的左孩子:", nodeA.left.left.data)

Python版本代码更简洁，不需要管理内存。注意None表示空指针。在访问 nodeA.left.data 之前，理论上也应该先判断 left 是否为 None，但这里已知不为空，所以直接访问。实际编程中建议先判断：

if nodeA.left is not None:
    print(nodeA.left.data)

完整可运行示例（C++版，增加遍历和递归删除）

为了让代码更实用，我们加入一个简单的前序遍历函数（先访问根节点，再遍历左子树，最后遍历右子树），以及一个递归删除所有节点的函数。这样你可以看到整棵树的结构，并安全释放内存。

#include <iostream>
using namespace std;

// 二叉树节点结构体
struct BinaryTreeNode {
    char data;
    BinaryTreeNode *left;
    BinaryTreeNode *right;
    BinaryTreeNode(char val) : data(val), left(nullptr), right(nullptr) {}
};

// 前序遍历（根左右）
void preOrder(BinaryTreeNode* node) {
    if (node == nullptr) return;        // 空节点直接返回
    cout << node->data << " ";          // 访问根节点
    preOrder(node->left);               // 遍历左子树
    preOrder(node->right);              // 遍历右子树
}

// 递归删除整棵树
void deleteTree(BinaryTreeNode* node) {
    if (node == nullptr) return;
    deleteTree(node->left);             // 先删除左子树
    deleteTree(node->right);            // 再删除右子树
    delete node;                        // 最后删除自己
}

int main() {
    // 创建节点
    BinaryTreeNode* nodeA = new BinaryTreeNode('A');
    BinaryTreeNode* nodeB = new BinaryTreeNode('B');
    BinaryTreeNode* nodeC = new BinaryTreeNode('C');
    BinaryTreeNode* nodeD = new BinaryTreeNode('D');
    BinaryTreeNode* nodeE = new BinaryTreeNode('E');
    BinaryTreeNode* nodeF = new BinaryTreeNode('F');
    BinaryTreeNode* nodeG = new BinaryTreeNode('G');

    // 构建树
    nodeA->left = nodeB;
    nodeA->right = nodeC;
    nodeB->left = nodeD;
    nodeB->right = nodeE;
    nodeC->left = nodeF;
    nodeC->right = nodeG;

    // 前序遍历输出
    cout << "前序遍历结果: ";
    preOrder(nodeA);  // 输出: A B D E C F G
    cout << endl;

    // 递归删除整棵树
    deleteTree(nodeA);
    nodeA = nullptr;   // 避免野指针
    cout << "树已删除完毕。" << endl;
    return 0;
}

运行结果：

前序遍历结果: A B D E C F G 
树已删除完毕。

? 小贴士：在 deleteTree 之后，我们手动将 nodeA 设为 nullptr，防止后续误用。这是良好的编程习惯。

总结要点

二叉树的定义：每个节点最多有两个子节点（左孩子和右孩子），左右顺序固定。
重要性质（背下来，做题常用）：
- 第i层最多 2^(i-1) 个节点。
- 深度为k的二叉树最多 (2^k)-1 个节点。
- n0 = n2 + 1（叶子数 = 有2个孩子的节点数 + 1）。
- 完全二叉树深度为 floor(log₂ n) + 1。
存储方式：
- 链式存储：灵活，适合动态增删，每个节点有左右指针。
- 顺序存储：用数组表示，适合完全二叉树，下标找父子关系方便。
代码实现：C++用结构体+指针，注意内存管理；Python用类+对象引用，注意空指针检查。
新手常见错误：
- 忘记初始化左右指针（C++野指针）。
- 访问空指针（例如 node->left 为 nullptr 时仍访问 node->left->data）。
- 混淆左右孩子顺序。
- C++内存泄漏或重复释放。
应用举例：二叉搜索树（快速查找）、堆（优先队列）、表达式树（计算表达式）、哈夫曼树（数据压缩）、编译器语法树（解析代码）。这些高级数据结构都是在二叉树性质的基础上构建的。

掌握这些基础，接下来的二叉树遍历（前序、中序、后序、层序）、二叉搜索树、平衡二叉树等就不再是难事了。如果你对完全二叉树的顺序存储感兴趣，下一篇文章会专门讲解。继续加油！

二叉树的性质与存储