跳到主要内容

数据结构：二叉树

· 阅读需 6 分钟
tanzhuo

链表和数组解决的是"线性"数据的存放问题,但一旦涉及层级关系或者快速查找,线性结构就显得力不从心了。树形结构正是为此而生,而二叉树是其中最基础、也最常被考察的一种——堆、BST、红黑树全都建立在它之上。

二叉树（Binary Tree） 是一种常见的数据结构,它由若干节点组成,每个节点最多只有 两个子节点：

  • 左子节点（Left Child）
  • 右子节点（Right Child）

因此称为 二叉树

"最多两个"这个限制看似简单,却带来一个重要性质：树的形态可以用递归定义——每棵二叉树都由根节点、左子树、右子树三部分组成,左右子树本身也是二叉树。后面几乎所有关于二叉树的算法（遍历、查找、插入）都是围绕这个递归结构展开的。

每个节点通常包含三个部分：

Node {
    value   // 节点存储的数据
    left    // 指向左子节点的引用,没有则为空
    right   // 指向右子节点的引用,没有则为空
}

也就是说,二叉树在内存里并不要求连续存放,节点之间靠引用（指针）串联,这一点和链表类似,只是每个节点从"一个后继"变成了"最多两个孩子"。

简单结构示例：

        A
       / \
      B   C
     / \   \
    D   E   F

其中：

  • A 是 根节点（Root）
  • B、C 是 A 的 子节点
  • D、E 是 B 的 子节点

没有子节点的节点（如 D、E、F）称为 叶子节点（Leaf）。从根到叶子经过的层数称为树的 高度,它直接决定了大多数树上操作的耗时。

按照形态的不同,二叉树有几个常见的特殊类别,下面依次来看。

满二叉树（Full Binary Tree）​

如果一棵树的 所有节点要么有两个子节点,要么没有子节点,则称为满二叉树。

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

特点：

  • 每个节点要么 0 个子节点
  • 要么 2 个子节点

换句话说,满二叉树里不存在"只有一个孩子"的节点。这种形态最"饱满",在层数相同的情况下能容纳的节点数最多。

完全二叉树（Complete Binary Tree）​

完全二叉树要求：

  • 除最后一层外,其余层全部填满
  • 最后一层节点从 左往右连续排列

示例：

        1
       / \
      2   3
     / \  /
    4  5 6

这种结构非常适合 数组存储,因此 堆（Heap） 就是完全二叉树。

为什么完全二叉树适合数组存储？因为节点"从上到下、从左到右"编号后中间没有空洞：把根放在下标 0,那么下标为 i 的节点,其左子节点在 2i + 1,右子节点在 2i + 2,父节点在 (i - 1) / 2（向下取整）。不需要存任何指针,靠下标运算就能在父子之间跳转,既省内存又对缓存友好——堆排序和优先级队列正是利用了这一点。

二叉搜索树（BST）​

前面两种分类关注的是"形状",二叉搜索树关注的则是"节点值的排列规则"。二叉搜索树（Binary Search Tree）满足：

左子树 < 根节点 < 右子树

注意这个约束是递归生效的：不只是左右孩子,而是整棵左子树的所有值都小于根,整棵右子树的所有值都大于根。

示例：

        8
       / \
      3   10
     / \    \
    1   6    14

特点：

  • 查询效率高
  • 平均时间复杂度：O(log n)

查找的过程和二分查找如出一辙：从根开始,目标值比当前节点小就往左走,比它大就往右走,每走一层就排除掉大约一半的候选节点。插入也是同理——沿着查找路径走到空位,把新节点挂上去即可。

但如果树退化成链表：

1
 \
  2
   \
    3

时间复杂度会退化为：

O(n)

退化最典型的触发场景,就是按 有序序列 依次插入：每个新节点都比之前的大,只能一路挂在右边,树"长歪"成了一条链,查找时每层只能排除一个节点,BST 的优势荡然无存。为了解决这个问题,才有了 AVL 树、红黑树这类 自平衡二叉搜索树——它们在插入、删除时通过旋转调整结构,保证树高始终维持在 O(log n) 级别。

遍历方式​

访问二叉树所有节点的方式称为遍历,常见的有四种：

  1. 前序遍历：根 → 左子树 → 右子树,常用于复制或序列化一棵树
  2. 中序遍历：左子树 → 根 → 右子树,对 BST 而言,中序遍历得到的正是 升序序列
  3. 后序遍历：左子树 → 右子树 → 根,适合"先处理孩子再处理自己"的场景,比如释放整棵树
  4. 层序遍历：逐层从左到右访问,借助队列实现,也就是树上的广度优先搜索

前三种用递归写起来非常自然,这也印证了前面说的——二叉树本身就是一个递归定义的结构。

踩坑与注意​

结合上面的内容,有几点在实际使用和刷题时容易栽跟头：

  • 别默认 BST 是平衡的。分析复杂度时要区分"平均 O(log n)"和"最坏 O(n)",面试中被追问的往往就是退化场景。
  • 中序遍历验证 BST。判断一棵树是否为合法 BST,不能只比较节点和它的直接孩子,要保证整棵子树都满足大小关系;用中序遍历检查序列是否严格递增是最不容易出错的写法。
  • 递归深度。树退化成链表时,递归遍历的调用栈深度也是 O(n),数据量大时可能栈溢出,必要时改用显式栈的迭代写法。
  • 区分"满"与"完全"。两者定义容易混淆:满二叉树不允许单孩子节点,完全二叉树则要求最后一层左对齐,判断题里经常拿这两个概念互相设坑。

总结​

二叉树是最基础也是最重要的数据结构之一,其核心特点是

  • 每个节点最多 两个子节点
  • 支持 高效搜索
  • 可以扩展为多种高级数据结构

常见变种包括：

  • 二叉搜索树（BST）
  • AVL 树
  • 红黑树
  • 堆（Heap）

理解二叉树是学习 算法与数据结构 的重要基础。掌握了它的递归定义、几种形态的区别以及遍历套路,再去看平衡树和堆,会发现那些"高级"结构不过是在二叉树上叠加了额外的约束而已。

评论 / COMMENTS