计算机基础

03. 树与二叉树

系统掌握二叉树、BST、AVL 树、红黑树、B 树与 B+ 树的原理与实现，理解自平衡与多路查找树的工程应用。

spcent 5 分钟阅读 2154 字

1. 树的基本概念

1.1 术语定义

        A           ← 根节点（Root）
       /|\
      B C D         ← B、C、D 是 A 的子节点
     /|   |
    E F   G         ← 叶子节点（无子节点）

A 的深度：0（层数从 0 开始）
树的度：3（最大子节点数）
高度：3（最深路径的节点数）
术语定义
度节点拥有的子节点数
深度根到该节点的边数
高度该节点到最远叶子的边数
满二叉树每层节点数达到最大值
完全二叉树除最后一层外满，最后一层左对齐

2. 二叉树遍历

2.1 四种遍历方式

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

# 前序遍历：根 → 左 → 右
def pre_order(root):
    if not root:
        return
    print(root.val, end=' ')
    pre_order(root.left)
    pre_order(root.right)

# 中序遍历：左 → 根 → 右（BST 中得到有序序列）
def in_order(root):
    if not root:
        return
    in_order(root.left)
    print(root.val, end=' ')
    in_order(root.right)

# 后序遍历：左 → 右 → 根
def post_order(root):
    if not root:
        return
    post_order(root.left)
    post_order(root.right)
    print(root.val, end=' ')

# 层序遍历（BFS）
def level_order(root):
    if not root:
        return
    from collections import deque
    q = deque([root])
    while q:
        node = q.popleft()
        print(node.val, end=' ')
        if node.left:
            q.append(node.left)
        if node.right:
            q.append(node.right)

2.2 迭代实现

# 非递归中序遍历（栈）
def in_order_iter(root):
    stack = []
    result = []
    curr = root
    while curr or stack:
        while curr:
            stack.append(curr)
            curr = curr.left
        curr = stack.pop()
        result.append(curr.val)
        curr = curr.right
    return result

3. 二叉搜索树（BST）

3.1 定义

左子树所有节点 < 根 < 右子树所有节点。

class BST:
    def __init__(self):
        self.root = None

    def insert(self, val):
        self.root = self._insert(self.root, val)

    def _insert(self, node, val):
        if not node:
            return TreeNode(val)
        if val < node.val:
            node.left = self._insert(node.left, val)
        elif val > node.val:
            node.right = self._insert(node.right, val)
        return node

    def search(self, val):
        return self._search(self.root, val)

    def _search(self, node, val):
        if not node or node.val == val:
            return node
        return self._search(node.left if val < node.val else node.right, val)

    def delete(self, val):
        self.root = self._delete(self.root, val)

    def _delete(self, node, val):
        if not node:
            return None
        if val < node.val:
            node.left = self._delete(node.left, val)
        elif val > node.val:
            node.right = self._delete(node.right, val)
        else:
            # 找到要删除的节点
            if not node.left:
                return node.right
            if not node.right:
                return node.left
            # 有两个子节点：找后继（右子树最小值）
            min_node = self._find_min(node.right)
            node.val = min_node.val
            node.right = self._delete(node.right, min_node.val)
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

3.2 BST 的问题

退化为链表时，操作退化为 O(n)：

退化的 BST (插入 1,2,3,4,5):

1
 \
  2
   \
    3
     \
      4
       \
        5

需要自平衡树来解决！

4. AVL 树（严格平衡 BST）

4.1 平衡因子

平衡因子 = 左子树高度 - 右子树高度，绝对值 ≤ 1

4.2 四种旋转

LL（左左）：右旋
    z              y
   /             /  \
  y      →      x    z
 /
x

RR（右右）：左旋
  z                y
   \             /  \
    y    →      z    x
     \
      x

LR（左右）：先左旋再右旋
RL（右左）：先右旋再左旋

class AVLNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None
        self.height = 1

class AVLTree:
    def _height(self, node):
        return node.height if node else 0

    def _balance(self, node):
        return self._height(node.left) - self._height(node.right) if node else 0

    def _update_height(self, node):
        node.height = 1 + max(self._height(node.left), self._height(node.right))

    def _rotate_right(self, y):
        x = y.left
        t2 = x.right
        x.right = y
        y.left = t2
        self._update_height(y)
        self._update_height(x)
        return x

    def _rotate_left(self, x):
        y = x.right
        t2 = y.left
        y.left = x
        x.right = t2
        self._update_height(x)
        self._update_height(y)
        return y

    def insert(self, node, val):
        if not node:
            return AVLNode(val)
        if val < node.val:
            node.left = self.insert(node.left, val)
        elif val > node.val:
            node.right = self.insert(node.right, val)
        else:
            return node

        self._update_height(node)
        balance = self._balance(node)

        # LL
        if balance > 1 and val < node.left.val:
            return self._rotate_right(node)
        # RR
        if balance < -1 and val > node.right.val:
            return self._rotate_left(node)
        # LR
        if balance > 1 and val > node.left.val:
            node.left = self._rotate_left(node.left)
            return self._rotate_right(node)
        # RL
        if balance < -1 and val < node.right.val:
            node.right = self._rotate_right(node.right)
            return self._rotate_left(node)

        return node

AVL 树保证严格平衡，查找 O(log n)，但插入/删除旋转次数较多。

5. 红黑树（实用平衡 BST）

5.1 五条性质

#性质
1节点是红色或黑色
2根是黑色
3所有叶子（NIL）是黑色
4红色节点的子节点必须是黑色
5从任一节点到其叶子的所有路径包含相同数目的黑色节点

Java TreeMap、C++ std::map、Linux 内核调度器均使用红黑树。

5.2 与 AVL 对比

特性AVL 树红黑树
平衡严格度严格宽松（最长路径 ≤ 2×最短）
查找略快略慢（但差距很小）
插入旋转最多 2 次最多 2 次
删除旋转最多 O(log n)最多 3 次
适用场景读多写少读写均衡

6. B 树与 B+ 树

6.1 为什么需要多路查找树

磁盘 I/O 是数据库的瓶颈。二叉树节点数多、高度高，导致磁盘访问次数多。

6.2 B 树（B-Tree）

m 阶 B 树定义：

  • 每个节点最多 m 个子节点
  • 除根外，每个节点至少 ⌈m/2⌉ 个子节点
  • 所有叶子在同一层
        [20, 50]
       /    |    \
  [5,10] [30,40] [60,70,80]

6.3 B+ 树（数据库索引首选）

特性B 树B+ 树
数据存储内部节点和叶子仅在叶子
叶子节点相互独立形成有序链表
范围查询需要中序遍历顺序扫描叶子
命中点可能在内部节点总是到叶子
空间利用率较低更高
B+ 树结构：

       [20, 50]              ← 内部节点只存键，不存数据
      /    |    \
[5,10,15]→[20,30,40]→[50,60,70,80]→NULL
   数据      数据       数据

叶子节点通过指针连接，支持高效范围查询

MySQL InnoDB 主键索引、文件系统（Ext4/XFS）均使用 B+ 树。

7. 树的应用场景总结

结构典型应用
普通二叉树表达式解析、哈夫曼编码
BST小型有序数据集合
AVL内存中读多写少的索引
红黑树TreeMap、进程调度、内存管理
B+ 树数据库索引、文件系统
Trie（字典树）搜索引擎自动补全、IP 路由前缀匹配
线段树区间查询、区间更新
树状数组（Fenwick）前缀和、点更新

8. 树的深度实战：Top-K 问题与 Morris 遍历

8.1 二叉搜索树中的第 K 大元素

class BSTKthLargest:
    """利用二叉搜索树中序遍历的有序性寻找第 K 大元素。"""
    def kthLargest(self, root: TreeNode, k: int) -> int:
        # 反向中序遍历：右 → 根 → 左
        self.count = 0
        self.result = None
        self._reverse_inorder(root, k)
        return self.result

    def _reverse_inorder(self, node: TreeNode, k: int):
        if not node or self.result is not None:
            return
        self._reverse_inorder(node.right, k)
        self.count += 1
        if self.count == k:
            self.result = node.val
            return
        self._reverse_inorder(node.left, k)

8.2 Morris 遍历（O(1) 空间复杂度）

def morris_inorder(root: TreeNode) -> list[int]:
    """不借助栈或递归，利用线索遍历二叉树，空间复杂度 O(1)。"""
    result = []
    curr = root
    while curr:
        if not curr.left:
            result.append(curr.val)
            curr = curr.right
        else:
            # 找到左子树的最右节点（前驱）
            predecessor = curr.left
            while predecessor.right and predecessor.right != curr:
                predecessor = predecessor.right

            if not predecessor.right:
                # 建立临时线索
                predecessor.right = curr
                curr = curr.left
            else:
                # 线索已存在，遍历完左子树，断开线索
                predecessor.right = None
                result.append(curr.val)
                curr = curr.right
    return result

Morris 遍历的适用范围：内存受限的嵌入式系统、百万级节点的树遍历，但会短暂修改树结构，不适用于多线程并发访问场景。

8.3 二叉树序列化与反序列化

# LeetCode 297 经典题
class Codec:
    """前序遍历序列化，空节点标记为 #。"""
    def serialize(self, root):
        def dfs(node):
            if not node:
                vals.append('#')
                return
            vals.append(str(node.val))
            dfs(node.left)
            dfs(node.right)
        vals = []
        dfs(root)
        return ','.join(vals)

    def deserialize(self, data):
        def dfs():
            val = next(vals)
            if val == '#':
                return None
            node = TreeNode(int(val))
            node.left = dfs()
            node.right = dfs()
            return node
        vals = iter(data.split(','))
        return dfs()

序列化方案对比：

方案格式示例优点缺点
前序+空标记1,2,#,#,3,#,#简单、唯一冗余标记
层序（BFS）[1,2,3,#,#,4,5]直观需要全树扫描
BST 压缩前序即可（值范围确定位置）空间最优仅适用于 BST

参考文章

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「计算机基础」更多文章

  1. 46. 排队论与容量估算：利特尔法则与尾延迟
  2. 45. 编译器优化与中间表示：SSA、内联与循环优化
  3. 44. 并发模型对比：Actor、CSP 与数据并行