二叉树

二叉树（Binary Tree）是计算机科学中最基础且重要的数据结构之一，广泛应用于算法设计、数据库索引、文件系统等领域。它是一种每个节点最多有两个子节点的树形结构，这两个子节点通常被称为左子节点和右子节点。

基本概念

定义

二叉树是满足以下条件的树：

• 每个节点最多有两个子节点（左子节点和右子节点）。
• 子节点有明确的左右顺序之分（即使只有一个子节点，也必须指明是左还是右）。

数学上可以递归定义为： $T=\{\begin{array}{ll}\mathrm{\varnothing }& \text{空树}\\ (r,T_L,T_R)& \text{根节点为 }r\text{，左子树为 }{T}_L\text{，右子树为 }{T}_R\end{array}$

术语

• 根节点（Root）：没有父节点的顶层节点
• 叶节点（Leaf）：没有子节点的节点
• 内部节点：至少有一个子节点的非根节点
• 深度：从根到该节点的唯一路径的边数
• 高度：从该节点到最深叶节点的最长路径的边数

graph TD A((根节点)) --> B((左子节点)) A --> C((右子节点)) B --> D((叶节点)) B --> E((叶节点)) C --> F((叶节点))

二叉树类型

满二叉树

每一层的节点都达到最大数量，即第$i$层有$2^{i-1}$个节点。

完全二叉树

除最后一层外，其他层节点都满，且最后一层节点从左向右连续排列。

二叉搜索树（BST）

对于任意节点：

• 左子树所有节点的值 < 当前节点的值
• 右子树所有节点的值 > 当前节点的值

基本操作

遍历方式

二叉树有四种基本遍历方式（以下示例代码使用Python实现）：

前序遍历

def preorder(root):
    if root:
        print(root.val)      # 访问根节点
        preorder(root.left)   # 遍历左子树
        preorder(root.right)  # 遍历右子树

中序遍历

def inorder(root):
    if root:
        inorder(root.left)    # 遍历左子树
        print(root.val)      # 访问根节点
        inorder(root.right)   # 遍历右子树

后序遍历

def postorder(root):
    if root:
        postorder(root.left)  # 遍历左子树
        postorder(root.right) # 遍历右子树
        print(root.val)      # 访问根节点

层序遍历

from collections import deque

def level_order(root):
    if not root:
        return
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.val)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

插入与删除

以二叉搜索树为例：

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

def insert(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def delete(root, val):
    if not root:
        return None
    if val < root.val:
        root.left = delete(root.left, val)
    elif val > root.val:
        root.right = delete(root.right, val)
    else:
        if not root.left:
            return root.right
        if not root.right:
            return root.left
        # 找到右子树的最小节点
        temp = root.right
        while temp.left:
            temp = temp.left
        root.val = temp.val
        root.right = delete(root.right, temp.val)
    return root

实际应用

表达式树

用于表示数学表达式，其中：

• 内部节点是运算符
• 叶节点是操作数

graph TD *((*)) --> +((+)) * --> 3((3)) + --> 2((2)) + --> 5((5))

表示表达式：(2 + 5) * 3

哈夫曼编码

用于数据压缩，通过构建最优二叉树实现高效编码。

数据库索引

许多数据库系统使用B树、B+树（二叉树的扩展）来加速数据检索。

复杂度分析

二叉树操作时间复杂度

操作	平均情况	最坏情况
查找	$O(\log n)$	$O(n)$
插入	$O(\log n)$	$O(n)$
删除	$O(\log n)$	$O(n)$
遍历	$O(n)$	$O(n)$

进阶话题

• 平衡二叉树：AVL树、红黑树等，通过旋转操作保持平衡
• 线索二叉树：利用空指针存储遍历信息
• 二叉堆：用于实现优先队列

练习题

1. 实现一个函数判断两棵二叉树是否相同 2. 计算二叉树的最大深度 3. 将有序数组转换为平衡二叉搜索树 4. 实现二叉树的序列化与反序列化