二叉树

二叉树

二叉树（Binary Tree）是计算机科学中最基础且重要的非线性数据结构之一，由节点（Node）组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树广泛应用于搜索、排序、数据库索引和编译器设计等领域。

基本概念

定义

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

• 每个节点最多有两个子节点。
• 子节点有明确的左右之分（即使只有一个子节点，也必须区分左或右）。

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

术语

• 根节点（Root）：没有父节点的顶层节点。
• 叶子节点（Leaf）：没有子节点的节点。
• 内部节点：至少有一个子节点的节点。
• 深度（Depth）：从根节点到该节点的路径长度（根节点深度为0）。
• 高度（Height）：从该节点到最远叶子节点的路径长度（叶子节点高度为0）。

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

二叉树类型

满二叉树（Full Binary Tree）

每个节点都有0个或2个子节点。

完全二叉树（Complete Binary Tree）

除最后一层外，其他层节点数达到最大值，且最后一层节点靠左排列。

完美二叉树（Perfect Binary Tree）

所有叶子节点在同一层，且每个非叶子节点都有两个子节点。

二叉搜索树（BST）

左子树所有节点值小于根节点，右子树所有节点值大于根节点。

存储方式

链式存储

通过节点对象和指针实现（或引用）：

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

# 示例构建
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)

顺序存储（数组表示）

适用于完全二叉树，索引规则：

• 父节点索引：$i$
• 左子节点索引：$2i+1$
• 右子节点索引：$2i+2$

遍历算法

深度优先遍历（DFS）

遍历方式对比

遍历方式	顺序	递归实现示例（Python）
前序遍历	根 → 左 → 右	def preorder(root): if root: print(root.value) preorder(root.left) preorder(root.right)
中序遍历	左 → 根 → 右	def inorder(root): if root: inorder(root.left) print(root.value) inorder(root.right)
后序遍历	左 → 右 → 根	def postorder(root): if root: postorder(root.left) postorder(root.right) print(root.value)

广度优先遍历（BFS/层序遍历）

from collections import deque

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

实际应用案例

案例1：表达式树

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

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

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

表示表达式：

$(2+5)*3$

案例2：哈夫曼编码树

用于数据压缩，频率高的字符使用短编码，频率低的字符使用长编码。

复杂度分析

操作时间复杂度（n为节点数）

操作	平均情况	最坏情况
查找	$O(\log n)$（BST）	$O(n)$（退化为链表）
插入/删除	$O(\log n)$	$O(n)$
遍历	$O(n)$	$O(n)$

进阶话题

• 平衡二叉树（AVL树/红黑树）：通过旋转保持平衡，确保操作效率。
• 线索二叉树：利用空指针存储遍历信息。
• B树/B+树：数据库索引使用的多路平衡树。

练习问题

1. 实现二叉树的反转（镜像） 2. 计算二叉树的最大深度 3. 验证二叉搜索树的有效性

# 问题1解答示例
def invert_tree(root):
    if root:
        root.left, root.right = invert_tree(root.right), invert_tree(root.left)
    return root