CC++ & Algorithm

二叉树的定义与性质

中等6
语言版本：C++
概述：二叉树是每个节点最多有两个子节点的树，它有特殊的数学性质，比如第k层最多有2^(k-1)个节点。

二叉树：计算机里的“家族树”

你有没有想过，学校里的年级班级、计算机里的文件目录、甚至体育比赛的淘汰赛，背后都藏着一个共同的结构——树？而在所有“树”中，二叉树是最简单、最常用的。它就像每个家长最多只能有两个孩子（一左一右）的家族树，用这种结构我们可以高效地组织数据、快速查找和排序。今天我们就来把它彻底搞明白。

什么是二叉树？

二叉树是每个节点最多有两个子节点的树结构。这两个子节点分别叫左孩子和右孩子。就像你的爸爸最多只可能有你和你弟弟/妹妹（左和右），再多了就不行啦！

  • 如果一个节点没有孩子，它就是叶子节点（相当于没有孙子的爷爷）。
  • 如果一个节点有左孩子但没有右孩子（或者反过来），它依然是二叉树，只是“缺了一个位置”。

生活中的例子：学校运动会，每个班级派两个同学参加接力赛——一个跑左边赛道，一个跑右边赛道。如果一个班级只有一个同学报名，那就只能占一个位置；如果一个班级没人报名，那这个班级就是叶子（不参赛）。

二叉树的特殊形态

1. 满二叉树

如果二叉树中每个节点都有两个孩子（除了叶子），而且所有叶子都在同一层，我们就叫它满二叉树。
比如一个大家庭，每一代人都结婚生两个孩子（一直生到第h代），那第h代的每个人都是叶子，上面每一层都有两个孩子。这种树结构特别对称，数学性质很好算。

2. 完全二叉树

如果二叉树除了最后一层外，其他层都是满的，并且最后一层的节点从左到右连续排列（不能中间缺一个），就叫完全二叉树。
想象一下，班级排队做操，要求第一排站满，第二排站满……最后一排的人必须从左边开始一个个站，不能跳着站。如果最后排中间空了一个位置，那就不算完全二叉树。

注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

二叉树的重要数学性质（考试必背！）

下面这几个公式就像乘法口诀一样重要，多看几遍，最好自己画棵树验证一下。

  1. 第 k 层最多有多少个节点？

    • 答案是：2k−12^{k-1}（根算第1层，最多1个；第2层最多2个，第3层最多4个……）
    • 例子：第3层最多有 23−1=42^{3-1}=4 个节点。

  2. 深度为 h 的二叉树最多有多少个节点？

    • 答案是：2h−12^{h} - 1（深度从1开始算，根深度为1）
    • 例子：深度为4的满二叉树，总节点数 = 24−1=152^4 - 1 = 15。

  3. 叶子节点数 = 度为2的节点数 + 1

    • “度”是指一个节点有几个孩子。度为2就是有左、右两个孩子的节点。
    • 这个公式在考试中经常用来解方程。比如：一棵二叉树有10个度为2的节点，那么它的叶子节点数就是 10+1=1110 + 1 = 11。
    • 怎么来的？可以理解成：每个度为2的节点贡献了两个孩子（即“制造”了一个叶子背后的空缺），最终叶子总数比这类节点多1。

常见考试题：已知叶子节点数，求度为2的节点数；或者已知总节点数和叶子数，求深度等。

生活中的例子：亲子运动会

假设学校举办亲子运动会，每个家长最多带两个孩子（一左一右）。

  • 如果家长有2个孩子，那就是度为2的节点。
  • 如果家长只有1个孩子，那就是度为1的节点。
  • 如果家长一个孩子都没带（自己参加），那就是叶子节点。

整个运动会的家长和孩子组成了一个二叉树。
利用上面的公式，如果我知道有几个家长带了两个孩子，就能算出有多少个家长是叶子（只身一人）。

再比如：一个文件目录，文件夹相当于节点，文件夹里最多可以包含两个子文件夹（左和右）。虽然实际目录可以有很多子文件夹，但二叉树简化了问题，让我们先学会基本概念。

在C++中如何表示二叉树？

二叉树通常用结构体或类来表示，每个节点包含三个部分：

  • 存储的值（比如数字、字符串）
  • 指向左孩子的指针
  • 指向右孩子的指针

C++代码中常用 nullptr 表示没有孩子（空指针）。

#include <iostream>
using namespace std;

struct TreeNode {
    int val;                 // 节点存储的值
    TreeNode* left;          // 左孩子指针
    TreeNode* right;         // 右孩子指针
    // 构造函数：创建节点时给值，左右孩子初始为空
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

这样，我们就可以像搭积木一样，把节点一个个连接起来。

递归：处理二叉树的神器

因为二叉树是递归定义的（每个子树也是一棵二叉树），所以很多操作用递归写起来特别自然。

计算节点总数（原有代码）

// 递归计算节点总数
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;               // 空树返回0
    int leftCount = countNodes(root->left);      // 左子树节点数
    int rightCount = countNodes(root->right);    // 右子树节点数
    return 1 + leftCount + rightCount;           // 加上自身
}

计算二叉树深度（高度）

// 递归计算二叉树深度（根深度为1，空树深度为0）
int treeDepth(TreeNode* root) {
    if (root == nullptr) return 0;               // 空树深度0
    int leftDepth = treeDepth(root->left);       // 左子树深度
    int rightDepth = treeDepth(root->right);     // 右子树深度
    return 1 + max(leftDepth, rightDepth);       // 取较大者加1
}

生活中的例子：计算你家族里最长的一支有多少代？从你爷爷算起，沿着爸爸、爷爷、曾祖父……一直往上，看哪条分支最长。这就是深度。

前序遍历（先访问根，再左子树，再右子树）

void preOrder(TreeNode* root) {
    if (root == nullptr) return;                 // 空节点返回
    cout << root->val << " ";                    // 先访问根
    preOrder(root->left);                        // 再左子树
    preOrder(root->right);                       // 最后右子树
}

常见错误与注意事项

❌ 错误1：忘记处理空指针（nullptr）

递归函数中，每次调用子节点前必须判断是否为空。比如 root->left 如果为空，再访问 root->left->val 就会程序崩溃。

正确做法：递归函数开头先判断 if (root == nullptr) return; 或者返回0。

❌ 错误2：混淆深度和高度

  • 深度（Depth）：从根到某个节点的路径长度（根深度为1或0，不同书中定义不同，通常CSP-J中使用根深度为1）。
  • 高度（Height）：从某个节点到最远叶子节点的路径长度（叶子高度为1或0）。 考试中要根据题目定义来，一般题目会说明“根节点在第1层”。

❌ 错误3：忘记释放内存

用 new 创建的节点，最好用 delete 释放，否则会造成内存泄漏。在竞赛中通常不需手动释放（程序结束会自动回收），但学习时要养成好习惯。

❌ 错误4：认为二叉树必须严格区分左右

虽然左右是区分的（左孩子和右孩子不同），但有些题目中“二叉树”只要求不超过两个孩子，无需区分左右。具体看题目描述。

完整示例：创建一棵二叉树，并计算节点数和深度

下面是一个完整可运行的程序，构建一棵小二叉树，输出节点数和深度，并展示前序遍历。

#include <iostream>
#include <algorithm>   // 用于 max 函数
using namespace std;

struct TreeNode {
    int val;                 // 节点的值
    TreeNode* left;          // 左孩子指针
    TreeNode* right;         // 右孩子指针
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} // 构造函数
};

// 递归计算节点总数
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;               // 空树返回0
    int leftCount = countNodes(root->left);      // 左子树节点数
    int rightCount = countNodes(root->right);    // 右子树节点数
    return 1 + leftCount + rightCount;           // 加上自身
}

// 递归计算深度（根深度为1）
int treeDepth(TreeNode* root) {
    if (root == nullptr) return 0;               // 空树深度0
    int leftDepth = treeDepth(root->left);       // 左子树深度
    int rightDepth = treeDepth(root->right);     // 右子树深度
    return 1 + max(leftDepth, rightDepth);       // 取较大者加1
}

// 前序遍历
void preOrder(TreeNode* root) {
    if (root == nullptr) return;                 // 空节点返回
    cout << root->val << " ";                    // 输出根的值
    preOrder(root->left);                        // 遍历左子树
    preOrder(root->right);                       // 遍历右子树
}

int main() {
    // 构建一棵小二叉树
    TreeNode* root = new TreeNode(10);
    root->left = new TreeNode(20);
    root->right = new TreeNode(30);
    root->left->left = new TreeNode(40);
    root->left->right = new TreeNode(50);
    // 结构：
    //        10
    //       /  \
    //      20  30
    //     /  \
    //    40  50

    cout << "前序遍历结果: ";
    preOrder(root);
    cout << endl;

    cout << "节点总数: " << countNodes(root) << endl;
    cout << "树的深度: " << treeDepth(root) << endl;

    // 释放内存（竞赛中有时不写，但好习惯）
    delete root->left->left;
    delete root->left->right;
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

运行结果：

前序遍历结果: 10 20 40 50 30 
节点总数: 5
树的深度: 3

注意：前序遍历的顺序是根→左→右，所以10之后是左子树20，然后左子树的左子树40，左子树的右子树50，最后回到右子树30。

相关知识点指引

学完二叉树的基础，你还可以继续探索：

  • 二叉树的遍历：除了前序，还有中序（左-根-右）、后序（左-右-根）和层序（按层从上到下、从左到右）。
  • 二叉搜索树：左孩子 < 根 < 右孩子，可以快速查找数据，像“猜数字”游戏。
  • 堆：一种特殊的完全二叉树，用于实现优先队列（比如医院急诊排队）。
  • 哈夫曼树：用于数据压缩，比如把文章中的字母用最短的二进制编码表示。
  • 平衡树：如AVL树、红黑树，让树保持“匀称”，避免变成一条直线（即退化）。

如果你对递归感到吃力，可以复习“函数递归”的基础知识，因为二叉树的操作几乎都离不开递归。

小总结：二叉树是每个节点最多两个孩子，满二叉树和完全二叉树是两种重要特例。记住三个常用数学公式（第k层最多2^(k-1)、总节点最多2^h-1、叶子数=度为2节点数+1），结合递归实现节点数、深度等计算，你就掌握了二叉树的核心。下次看到文件目录、比赛对阵图，你都能用二叉树的眼光去分析它们！

例题精讲

1单选题

一棵二叉树中，第k层（k≥1）最多有多少个节点？

A2^k
B2^(k-1)
C2^(k+1)
D2^k - 1
2单选题

一棵深度为h的满二叉树（即每层节点数都达到最大值）的节点总数是多少？

A2^h
B2^h - 1
C2^(h+1) - 1
Dh^2
3判断题

在任意一棵二叉树中，叶子节点（度为0的节点）的个数等于度为2的节点个数加1。

4判断题

一棵深度为5的二叉树，其节点总数最多为31个。

5填空题
给定二叉树的节点定义以及统计节点个数的函数，请补充空白处代码。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
};
int countNodes(TreeNode* root) {
    if (root == nullptr) return 0;
    return ___;
}