数据结构｜二叉树（一）：树的基础概念与二叉树核心结构

写在前面

在前面的数据结构学习中，我们已经完整梳理了线性数据结构部分：

• 顺序表与链表：研究数据元素之间的一对一关系；
• 栈与队列：研究操作受限制的线性结构。

这些结构有一个共同特点：数据元素之间存在一条明确的线性关系，每个元素最多只有一个前驱和一个后继，形如A → B → C → D。

但在实际开发中，很多数据并不是简单的一条线：文件系统的目录结构、公司的组织架构、数据库的索引结构、搜索引擎的层级关系……它们更符合“层层向下展开”的形态。

因此，从这一篇开始，我们正式进入非线性数据结构的世界——树（Tree）。 而在所有树结构中，最经典、应用最广泛、也是整个数据结构体系核心的，就是二叉树（Binary Tree）。

前置知识推荐

在正式开始二叉树学习之前，非常建议先补一篇 C 语言底层原理内容

<a href="/#post/2026-08-20-function-stack-frame-1">C语言底层：函数栈帧的创建与销毁（一）｜从汇编视角看懂函数调用的本质简述</a>

这篇内容不属于数据结构专题，但它讲解的「函数调用栈帧机制」，是理解二叉树递归的关键底层支撑。

为什么要先懂栈帧？

后续二叉树的学习中，我们会大量接触递归遍历、深度优先搜索（DFS）、树高计算、分治思想。而这些算法的底层，本质上都在依赖函数调用栈。

比如最经典的前序遍历：

void PrevOrder(TreeNode* root)
{
    if(root == NULL)
        return;

    printf("%d ", root->data);
    PrevOrder(root->left);
    PrevOrder(root->right);
}

表面上是几行简单的递归代码，但程序真正执行时，每一次递归调用都会在系统栈中创建新的函数栈帧：

PrevOrder(A)
    ↓
PrevOrder(B)
    ↓
PrevOrder(D)
    ↓
逐层返回

每进入一层递归，系统都会保存当前函数的局部变量、下一步执行位置，开辟新栈帧继续执行；递归结束时，再按照后进先出的顺序逐层销毁，回到上一层继续执行。

理解了函数栈帧，你才能真正明白：

• 为什么递归可以独立保存每一层的数据；
• 为什么递归深度过大会导致栈溢出；
• 为什么二叉树遍历可以天然用递归实现。

如果对 C 语言内存、函数调用机制还比较陌生，建议先看完栈帧相关内容，再来学习二叉树递归会顺畅很多。

一、树的概念与基础特点

1.1 什么是树

树是由n（n ≥ 0）个有限节点组成的非线性数据结构，节点之间通过连接形成清晰的层次关系。当 n=0 时称为空树。

比如一棵简单的树：

          A
       /  |  \
      B   C   D
     / \
    E   F

其中 A 是根节点，B、C、D 是 A 的子节点，E、F 是 B 的子节点。

数据结构里的树和现实中的树形态一致，只不过是倒过来画的：根在上，叶子在下。

1.2 树的三个核心特点

1. 有且仅有一个根节点：它是整棵树的最顶层节点，没有父节点。
2. 除根节点外，每个节点有且仅有一个父节点：不存在一个节点有多个上层节点。
3. 不存在环：树中任意两个节点之间有且只有一条路径。如果出现闭环结构，就不再属于树，而是图。

二、树的核心术语

这些术语是树结构的基础语言，必须逐个理解：

• 节点的度：一个节点直接拥有的子节点数量，称为该节点的度。
• 叶节点（终端节点）：度为 0 的节点，也就是没有子节点、处于最底层的节点。
• 分支节点（非终端节点）：度不为 0 的节点，也就是有子节点、可以继续分叉的节点。
• 父节点（双亲节点）：如果一个节点包含子节点，该节点就是其子节点的父节点。
• 子节点（孩子节点）：一个节点直接下属的节点，称为该节点的子节点。
• 兄弟节点：拥有同一个父节点的节点，互称为兄弟节点。
• 堂兄弟节点：父节点位于同一层的节点，互称为堂兄弟节点。
• 树的度：整棵树中，所有节点度的最大值。
• 节点的层次：从根节点开始计数，根为第 1 层，根的子节点为第 2 层，以此类推。
• 树的高度（深度）：树中节点的最大层次数，也就是这棵树总共有多少层。
• 节点的祖先：从根节点到该节点的路径上，所有经过的节点都是它的祖先。
• 子孙：以某个节点为根的子树中，所有节点都称为该节点的子孙。
• 森林：由 m（m≥0）棵互不相交的树组成的集合，称为森林。

三、树的常见表示方法

普通树最大的特点是：一个节点可能有任意多个孩子。因此不同的表示方法，本质上都是在解决「如何存储多个孩子指针」的问题。

3.1 指针数组表示法（C 语言基础写法）

最直观的思路：每个节点存放数据，再用一个固定长度的指针数组，存储所有孩子节点的地址。

#define MAX_CHILD 10  // 预设最大孩子数量

typedef struct TreeNode
{
    int data;
    struct TreeNode* child[MAX_CHILD]; // 孩子指针数组
    int childNum;                      // 实际孩子个数
} TreeNode;

优点：结构简单，容易理解。 缺点：孩子数量有上限，固定数组会造成空间浪费；树的度不确定时很难设定合适的数组大小。

3.2 动态数组表示法（C++ vector 写法）

为了解决固定数组的缺陷，C++ 中通常用vector动态数组来存放孩子指针，底层逻辑和指针数组完全一致，只是数组可以按需自动扩容。

struct TreeNode
{
    int data;
    vector<TreeNode*> child; // 动态数组存储孩子指针
};

优点：无需提前预估孩子数量，空间利用率更高。 本质上仍然是「孩子指针数组」的思路。

3.3 孩子兄弟表示法（最经典通用）

孩子兄弟表示法，也叫「左孩子右兄弟」表示法，是工业界最通用的树表示方式。它的核心思想是：把任意多叉树，统一转换成二叉结构。

每个节点只保存两个指针：

• firstChild：指向第一个孩子节点
• nextBrother：指向右边第一个兄弟节点

typedef struct TreeNode
{
    int data;
    struct TreeNode* firstChild;  // 第一个孩子
    struct TreeNode* nextBrother; // 下一个兄弟
} TreeNode;

比如一棵普通树：

        A
     /  |  \
    B   C   D

用孩子兄弟表示法转换后，结构变为：

        A
        |
        B
         \
          C
           \
            D

这种写法的优势非常突出：

1. 无论树的度是多少，每个节点都只存两个指针，空间固定无浪费；
2. 可以表示任意度数的树；
3. 也是多叉树转二叉树的核心方法——这正是我们重点研究二叉树的原因：只要把二叉树吃透，所有普通树都可以通过这种方式转化后处理。

四、二叉树的概念与特殊结构

4.1 什么是二叉树

二叉树是树的特殊形式：每个节点最多有两棵子树，节点的度最大为 2。 两个子节点有严格的左右顺序，分别称为左孩子和右孩子，次序不能颠倒。即使节点只有一个孩子，也要明确区分是左还是右。

比如下面两棵树，是完全不同的二叉树：

    A          A
   /            \
  B              B

4.2 满二叉树

如果一棵二叉树的每一层节点数都达到最大值，所有叶子节点都在最底层，所有分支节点的度都为 2，这就是满二叉树。

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

核心特点：

• 第 i 层的节点数为2^(i-1)
• 高度为 h 的满二叉树，总节点数为2^h - 1
• 没有度为 1 的节点，叶子全部在最底层

这里有一个很直观的结论：满二叉树的节点数量是指数级增长的。比如高度只有 30 的满二叉树，总节点数就超过了 10 亿。看似不高的层数，能容纳的数据量极其庞大，这也是树结构查询效率极高的底层原因。

4.3 完全二叉树

完全二叉树是满二叉树的“前半段”：

前 h-1 层全部填满，最后一层的节点从左到右连续排列，中间没有空缺。

          A
       /     \
      B       C
     / \     /
    D   E   F

核心特点：

• 前 h-1 层一定是满的；
• 最后一层节点从左向右连续，不能有空隙；
• 满二叉树是特殊的完全二叉树，但完全二叉树不一定是满二叉树。

完全二叉树最大的意义，就是它非常适合用数组顺序存储——空间利用率高，并且可以通过下标公式快速定位父子节点。

五、二叉树的核心性质

性质1：每层最大节点数

二叉树的第 i 层上，最多有2^(i-1)个节点（i ≥ 1）。

性质2：整棵树最大节点数

高度为 h 的二叉树，最多有2^h - 1个节点，对应满二叉树的总节点数。

性质3：叶子节点与度为2节点的关系

对任意一棵二叉树，设度为 0 的叶子节点数为n₀，度为 2 的节点数为n₂，则一定满足：n₀ = n₂ + 1

叶子节点的数量，永远比度为 2 的节点多 1 个。

性质4：顺序存储下的父子下标关系

这是完全二叉树数组实现最核心的公式，也是后续堆结构的基础。

把完全二叉树按层序遍历存入数组，根节点下标为 0 时：

• 若父节点下标为i左孩子下标 =**2i + 1右孩子下标 =2i + 2**

反过来，已知孩子节点下标为i：

• 父节点下标 =(i - 1) / 2（整数除法，向下取整）

正是因为有这个公式，我们不需要指针，仅凭数组下标就能快速定位任意节点的父子关系，这也是完全二叉树适合顺序存储的根本原因。

六、二叉树的存储结构简介

二叉树主要有两种存储方式，分别对应不同的场景，选择的核心依据是：空间利用率 + 操作效率。

6.1 顺序存储（数组实现）

实现方式：将二叉树按层序遍历的顺序，依次存入一个连续数组中，通过下标公式计算父子节点的位置。

适用场景：满二叉树、完全二叉树

对于满二叉树和完全二叉树来说，节点是连续排布的，数组中几乎没有空位，空间利用率极高：

• 满二叉树：数组空间 100% 利用，没有任何浪费；
• 完全二叉树：只有最后一层右侧可能有空缺，浪费极少。

同时配合父子下标公式，定位父节点、子节点都只需要一次算术运算，效率极高。这也是堆选择数组作为底层实现的核心原因。

不适用场景：普通二叉树

如果是形态不规则的普通二叉树，用数组存储会造成极其严重的空间浪费。 举个极端例子：一棵只有左孩子的单支树（斜树），高度为 h，按照满二叉树的数组长度需要开辟2^h - 1个空间，但实际有效节点只有 h 个，绝大多数位置都是空的。

因此普通二叉树几乎不会采用顺序存储，更适合用链式结构。

6.2 链式存储（指针实现）

实现方式：每个节点存储数据 + 左孩子指针 + 右孩子指针，和链表的思路类似。

typedef struct TreeNode
{
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

适用场景：普通二叉树

对于形态不确定、节点分布不规则的二叉树，链式存储按需申请节点，没有多余的空间浪费，灵活性极高。 后续我们学习的二叉树遍历、二叉搜索树、平衡树等内容，基本都采用链式存储实现。

七、初识堆（Heap）

既然完全二叉树的顺序存储兼具空间紧凑和父子定位高效的优势，工业界就基于这种结构设计出了一种非常经典实用的数据结构——堆（Heap）。

7.1 什么是堆

堆是一种特殊的完全二叉树，它除了满足完全二叉树的结构要求，还额外满足父子节点之间的大小关系。

主要分为两类：

小根堆

满足：父节点的值 ≤ 所有子节点的值

          1
        /   \
       3     5
      /
     7

根节点一定是整棵堆中的最小值。

大根堆

满足：父节点的值 ≥ 所有子节点的值

          9
        /   \
       7     8
      /
     3

根节点一定是整棵堆中的最大值。

7.2 常见误区：堆不是排序结构

这是学习堆最容易踩的坑：堆 ≠ 有序结构。

堆只保证父节点和子节点之间的大小关系，并不保证：

• 左子树全部小于右子树；
• 同一层的节点有序；
• 遍历结果有序。

比如下面这棵小根堆：

          1
        /   \
       5     3
      /
     8

它满足1<5、1<3、5<8，完全符合小根堆规则；但5 > 3，兄弟节点之间并没有顺序关系。

一句话总结：堆的核心目标是快速获取最大值或最小值，而不是让所有数据有序。

7.3 堆的典型应用

1. 优先级队列：普通队列是先进先出，而优先级队列让优先级高的元素先出队，底层通常由堆实现，常用于操作系统任务调度、网络请求处理等场景。
2. 堆排序：利用堆的特性实现的排序算法，时间复杂度 O(NlogN)。注意：堆本身不是排序结构，堆排序是通过反复删除堆顶元素的过程完成排序。
3. Top K 问题：比如找出海量数据中最大的前 K 个数，用堆可以把复杂度优化到 O(NlogK)，是面试高频考点。

写在最后

本篇作为二叉树专题的开篇，我们沿着「 线性结构 → 树结构 → 二叉树 → 完全二叉树 → 顺序存储 → 堆」的脉络，把基础概念、术语、性质和应用场景完整串了一遍。

理解这些前置知识后，再去学堆的实现、二叉树的递归遍历，就不会只是机械地背代码，而是能明白“为什么这么设计”。

下一篇，我们继续学习堆相关的知识，进一步熟悉完全二叉树在工程上的实际运用。