跳到主要内容

树

树（Tree）是一种特殊的图，在计算机科学中有着举足轻重的地位。文件系统的目录结构、HTML 文档的 DOM 树、编译器中的语法树、数据库的索引结构——树的身影无处不在。理解树的性质和操作，是掌握数据结构与算法的关键。

树的定义​

图论视角的定义​

树是无向连通无环图。等价地说，树是满足以下任一条件的图：

  1. 连通且无环
  2. 连通，且边数等于顶点数减一
  3. 无环，且边数等于顶点数减一
  4. 任意两个顶点之间有且仅有一条路径
  5. 连通，但删除任一边后不再连通
  6. 无环，但添加任一边后会产生环

这些等价条件从不同角度刻画了树的本质，在证明中经常用到。

基本术语​

根（Root）：有根树中指定的起始顶点。

叶子（Leaf）：度为 1 的顶点（根节点除外，如果根是唯一的度为 1 的节点）。

内部节点（Internal Node）：度大于 1 的顶点。

父节点（Parent）与子节点（Child）：在有根树中，如果从根到节点 B 的路径经过节点 A，且 A 与 B 相邻，则 A 是 B 的父节点，B 是 A 的子节点。

祖先（Ancestor）与后代（Descendant）：从根到某节点的路径上的所有节点都是该节点的祖先；某节点的后代是其子树中的所有节点。

兄弟（Sibling）：具有相同父节点的节点。

深度（Depth）：节点到根的路径长度。根的深度为 0。

高度（Height）：节点到其子树中最远叶子的路径长度。树的高度是根的高度。

层次（Level）：节点的层次等于其深度加 1。

class TreeNode:
    """树的节点类"""
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None
    
    def add_child(self, node):
        node.parent = self
        self.children.append(node)
    
    def depth(self):
        """计算节点深度"""
        d = 0
        node = self.parent
        while node:
            d += 1
            node = node.parent
        return d
    
    def height(self):
        """计算节点高度"""
        if not self.children:
            return 0
        return 1 + max(child.height() for child in self.children)

树的性质​

性质 1：nn 个顶点的树恰好有 n−1n-1 条边。

性质 2：树的任意两个顶点之间有唯一路径。

性质 3：树是二分图。

性质 4：n≥2n \geq 2 的树至少有两个叶子。

证明（性质 4）：树中所有度数之和为 2(n−1)=2n−22(n-1) = 2n - 2。假设最多 1 个叶子，则至少 n−1n-1 个顶点度数 ≥2\geq 2。度数之和 ≥1×1+(n−1)×2=2n−1>2n−2\geq 1 \times 1 + (n-1) \times 2 = 2n - 1 > 2n - 2，矛盾。

有根树​

有根树的定义​

有根树是在树中指定一个顶点作为根（Root）的数据结构。根确定了树中所有边的方向——从根向外的方向。

有根树常用于表示层次结构：文件系统、组织结构、语法分析树等。

根到叶子的路径​

在有根树中，从根到任意节点有唯一路径。这条路径确定了节点的位置。

子树​

对于有根树中的任一节点 vv，以 vv 为根的子树包含 vv 及其所有后代。

def get_subtree_nodes(node):
    """获取以 node 为根的子树的所有节点"""
    nodes = [node.value]
    for child in node.children:
        nodes.extend(get_subtree_nodes(child))
    return nodes

二叉树​

二叉树的定义​

二叉树是每个节点最多有两个子节点的有根树，这两个子节点分别称为左孩子和右孩子。

二叉树与度为 2 的普通树的区别：二叉树区分左右，即使只有一个孩子也要区分是左孩子还是右孩子。

class BinaryTreeNode:
    """二叉树节点"""
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

二叉树的性质​

性质 1：二叉树第 ii 层最多有 2i2^i 个节点（i≥0i \geq 0）。

性质 2：深度为 kk 的二叉树最多有 2k+1−12^{k+1} - 1 个节点。

性质 3：对于任何非空二叉树，如果叶子数为 n0n_0，度为 2 的节点数为 n2n_2，则 n0=n2+1n_0 = n_2 + 1。

证明：设度为 1 的节点数为 n1n_1。总节点数 n=n0+n1+n2n = n_0 + n_1 + n_2。边数 e=n−1=n1+2n2e = n - 1 = n_1 + 2n_2（每个度为 1 的节点贡献 1 条边，度为 2 的贡献 2 条）。因此 n0+n1+n2−1=n1+2n2n_0 + n_1 + n_2 - 1 = n_1 + 2n_2，化简得 n0=n2+1n_0 = n_2 + 1。

满二叉树与完全二叉树​

满二叉树（Full Binary Tree）：每个节点要么是叶子，要么有两个孩子。所有叶子在同一层。

完全二叉树（Complete Binary Tree）：除最后一层外，每层都被完全填满；最后一层的节点从左到右连续排列。

满二叉树是完全二叉树的特例。

def is_complete_binary_tree(root):
    """检查是否为完全二叉树"""
    if not root:
        return True
    
    queue = [root]
    seen_null = False
    
    while queue:
        node = queue.pop(0)
        
        if node is None:
            seen_null = True
        else:
            if seen_null:
                return False
            queue.append(node.left)
            queue.append(node.right)
    
    return True

二叉树的遍历​

前序遍历（Pre-order）：根 → 左子树 → 右子树

def preorder(node, result=None):
    """前序遍历"""
    if result is None:
        result = []
    if node:
        result.append(node.value)
        preorder(node.left, result)
        preorder(node.right, result)
    return result

中序遍历（In-order）：左子树 → 根 → 右子树

def inorder(node, result=None):
    """中序遍历"""
    if result is None:
        result = []
    if node:
        inorder(node.left, result)
        result.append(node.value)
        inorder(node.right, result)
    return result

后序遍历（Post-order）：左子树 → 右子树 → 根

def postorder(node, result=None):
    """后序遍历"""
    if result is None:
        result = []
    if node:
        postorder(node.left, result)
        postorder(node.right, result)
        result.append(node.value)
    return result

层次遍历（Level-order）：按层次从上到下，每层从左到右

from collections import deque

def levelorder(root):
    """层次遍历"""
    if not root:
        return []
    
    result = []
    queue = deque([root])
    
    while queue:
        node = queue.popleft()
        result.append(node.value)
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)
    
    return result

遍历序列的关系：

  • 已知前序遍历和中序遍历，可以唯一确定一棵二叉树
  • 已知后序遍历和中序遍历，可以唯一确定一棵二叉树
  • 仅知道前序和后序，无法唯一确定二叉树

二叉搜索树​

二叉搜索树的定义​

二叉搜索树（BST）是一种特殊的二叉树，满足以下性质：

  • 左子树所有节点的值小于根节点的值
  • 右子树所有节点的值大于根节点的值
  • 左右子树也是二叉搜索树

BST 支持高效的查找、插入和删除操作。

class BST:
    def __init__(self):
        self.root = None
    
    def search(self, value):
        """查找值"""
        node = self.root
        while node:
            if value == node.value:
                return node
            elif value < node.value:
                node = node.left
            else:
                node = node.right
        return None
    
    def insert(self, value):
        """插入值"""
        if not self.root:
            self.root = BinaryTreeNode(value)
            return
        
        node = self.root
        while True:
            if value < node.value:
                if not node.left:
                    node.left = BinaryTreeNode(value)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = BinaryTreeNode(value)
                    return
                node = node.right

BST 的时间复杂度​

  • 最好情况（树平衡）：查找、插入、删除均为 O(log⁡n)O(\log n)
  • 最坏情况（树退化为链表）：O(n)O(n)

为了保持平衡，发展出了 AVL 树、红黑树等自平衡二叉搜索树。

生成树与最小生成树​

生成树​

给定连通无向图 GG，其生成树是包含 GG 所有顶点的树。

生成树的性质：

  • 包含原图所有顶点
  • 是一棵树（无环连通）
  • 边数为 n−1n-1

生成树的存在性：每个连通图都有生成树。可以通过 BFS 或 DFS 得到生成树。

最小生成树​

在带权连通图中，最小生成树（MST）是边权之和最小的生成树。

应用：网络设计、电路布线、管道铺设等。

算法：Prim 算法和 Kruskal 算法（详见图论章节）。

树的计数​

Cayley 公式​

nn 个标号顶点的不同树的数量为 nn−2n^{n-2}。

这个公式由 Arthur Cayley 于 1889 年提出，是图论中最著名的计数公式之一。

证明思路（Prüfer 序列）：每个标号树可以唯一编码为一个长度为 n−2n-2 的 Prüfer 序列，每个序列元素可以是 nn 个标号中的任意一个，故共有 nn−2n^{n-2} 个不同的序列，也就有 nn−2n^{n-2} 棵不同的树。

例子：n=3n = 3 时，有 33−2=33^{3-2} = 3 棵不同的树：

  • 1-2-3
  • 1-3-2
  • 2-1-3

（这里用 a−b−ca-b-c 表示边为 {a,b}\{a,b\} 和 {b,c}\{b,c\} 的树）

# Cayley 公式验证
def cayley(n):
    return n ** (n - 2)

for n in range(2, 8):
    print(f"n={n}: {cayley(n)} 棵树")
# n=2: 1
# n=3: 3
# n=4: 16
# n=5: 81
# n=6: 256
# n=7: 625

无标号树的计数​

无标号树（不考虑顶点名称，只考虑结构）的计数复杂得多，没有简单的闭式公式。

n=1n = 1 到 n=10n = 10 的无标号树数量：1, 1, 1, 2, 3, 6, 11, 23, 47, 106

树的应用​

文件系统​

操作系统的文件系统是树结构的典型应用。目录是内部节点，文件是叶子节点。

root/
├── home/
│   ├── user1/
│   │   └── documents/
│   └── user2/
├── etc/
│   └── config
└── var/
    └── log/

表达式树​

算术表达式可以用二叉树表示。内部节点是运算符，叶子是操作数。

例如，表达式 (a+b)∗(c−d)(a + b) * (c - d) 的表达式树：

        *
       / \
      +   -
     / \ / \
    a  b c  d
def evaluate_expression_tree(node):
    """计算表达式树的值"""
    if not node.left and not node.right:
        return node.value  # 叶子节点，返回数值
    
    left_val = evaluate_expression_tree(node.left)
    right_val = evaluate_expression_tree(node.right)
    
    if node.value == '+':
        return left_val + right_val
    elif node.value == '-':
        return left_val - right_val
    elif node.value == '*':
        return left_val * right_val
    elif node.value == '/':
        return left_val / right_val

哈夫曼编码​

哈夫曼编码是一种最优前缀编码方法，用于数据压缩。它构建一棵哈夫曼树，频率高的字符离根近，频率低的离根远。

构建过程：

  1. 每个字符作为叶子节点，权重为出现频率
  2. 选择权重最小的两个节点，合并为新节点，权重为两者之和
  3. 重复直到只剩一个节点，即为根

编码：从根到叶子的路径确定编码，左分支为 0，右分支为 1。

决策树​

决策树是机器学习中的一种模型，用于分类和回归。

  • 内部节点表示特征测试
  • 分支表示测试结果
  • 叶子节点表示决策结果
        年龄>30?
       /        \
      是         否
      |          |
   收入>50k?   学生?
   /    \      /   \
  是    否    是    否
  |     |     |     |
 贷款  拒绝  拒绝   贷款

树在计算机科学中的深入应用​

树是计算机科学中最核心的数据结构之一，几乎所有复杂的软件系统都依赖树结构来组织数据或控制流程。

文件系统的树结构​

文件系统是树结构最直观的应用。理解文件系统的树结构，有助于设计高效的文件操作算法。

路径问题本质是树的遍历：

import os

class FileSystemTree:
    """文件系统树结构分析"""
    
    @staticmethod
    def list_all(path):
        """递归列出所有文件（前序遍历）"""
        result = []
        if os.path.isfile(path):
            return [path]
        for item in os.listdir(path):
            full_path = os.path.join(path, item)
            result.append(full_path)
            if os.path.isdir(full_path):
                result.extend(FileSystemTree.list_all(full_path))
        return result
    
    @staticmethod
    def find_largest_files(path, n=10):
        """找出最大的 n 个文件（树的后序遍历收集信息）"""
        file_sizes = []
        
        def collect_sizes(current_path):
            if os.path.isfile(current_path):
                file_sizes.append((current_path, os.path.getsize(current_path)))
            elif os.path.isdir(current_path):
                for item in os.listdir(current_path):
                    collect_sizes(os.path.join(current_path, item))
        
        collect_sizes(path)
        return sorted(file_sizes, key=lambda x: x[1], reverse=True)[:n]
    
    @staticmethod
    def calculate_directory_size(path):
        """计算目录大小（后序遍历）"""
        if os.path.isfile(path):
            return os.path.getsize(path)
        
        total = 0
        for item in os.listdir(path):
            total += FileSystemTree.calculate_directory_size(
                os.path.join(path, item)
            )
        return total

抽象语法树（AST）​

编译器将源代码解析为抽象语法树，这是编译原理的核心概念。

表达式求值：将算术表达式解析为 AST，然后遍历求值。

class ASTNode:
    """抽象语法树节点"""
    pass

class NumberNode(ASTNode):
    def __init__(self, value):
        self.value = value
    
    def evaluate(self):
        return self.value
    
    def __str__(self):
        return str(self.value)

class BinaryOpNode(ASTNode):
    def __init__(self, left, op, right):
        self.left = left
        self.op = op
        self.right = right
    
    def evaluate(self):
        left_val = self.left.evaluate()
        right_val = self.right.evaluate()
        if self.op == '+':
            return left_val + right_val
        elif self.op == '-':
            return left_val - right_val
        elif self.op == '*':
            return left_val * right_val
        elif self.op == '/':
            return left_val / right_val
        elif self.op == '^':
            return left_val ** right_val
    
    def __str__(self):
        return f"({self.left} {self.op} {self.right})"

def parse_expression(tokens):
    """简单的表达式解析器（递归下降）"""
    # 解析加减法（最低优先级）
    def parse_additive(index):
        left, index = parse_multiplicative(index)
        while index < len(tokens) and tokens[index] in ['+', '-']:
            op = tokens[index]
            right, index = parse_multiplicative(index + 1)
            left = BinaryOpNode(left, op, right)
        return left, index
    
    # 解析乘除法
    def parse_multiplicative(index):
        left, index = parse_power(index)
        while index < len(tokens) and tokens[index] in ['*', '/']:
            op = tokens[index]
            right, index = parse_power(index + 1)
            left = BinaryOpNode(left, op, right)
        return left, index
    
    # 解析幂运算
    def parse_power(index):
        left, index = parse_primary(index)
        if index < len(tokens) and tokens[index] == '^':
            right, index = parse_power(index + 1)  # 右结合
            left = BinaryOpNode(left, '^', right)
        return left, index
    
    # 解析基本元素
    def parse_primary(index):
        token = tokens[index]
        if token == '(':
            node, index = parse_additive(index + 1)
            return node, index + 1  # 跳过 ')'
        else:
            return NumberNode(float(token)), index + 1
    
    ast, _ = parse_additive(0)
    return ast

# 示例
tokens = ['2', '+', '3', '*', '4', '^', '2']
ast = parse_expression(tokens)
print(f"表达式: {ast}")        # (2 + (3 * (4 ^ 2)))
print(f"结果: {ast.evaluate()}")  # 50.0

数据库索引：B 树与 B+ 树​

数据库索引使用平衡树结构实现高效查询。B 树和 B+ 树是 BST 的推广，每个节点可以有多个子节点。

B 树的核心思想：

  • 每个节点存储多个键值
  • 所有叶子节点在同一层
  • 保持平衡，查找时间复杂度稳定在 O(log n)
class BTreeNode:
    """B 树节点（简化版）"""
    def __init__(self, leaf=False):
        self.keys = []       # 键列表
        self.children = []   # 子节点列表
        self.leaf = leaf     # 是否为叶子节点

class BTree:
    """B 树实现（教学用简化版）"""
    def __init__(self, t=3):
        self.t = t  # 最小度数，节点最多 2t-1 个键
        self.root = BTreeNode(leaf=True)
    
    def search(self, key, node=None):
        """搜索键"""
        if node is None:
            node = self.root
        
        i = 0
        while i < len(node.keys) and key > node.keys[i]:
            i += 1
        
        if i < len(node.keys) and key == node.keys[i]:
            return (node, i)  # 找到
        elif node.leaf:
            return None  # 未找到
        else:
            return self.search(key, node.children[i])
    
    def insert(self, key):
        """插入键"""
        root = self.root
        if len(root.keys) == 2 * self.t - 1:
            # 根节点已满，分裂
            new_root = BTreeNode()
            new_root.children.append(self.root)
            self._split_child(new_root, 0)
            self.root = new_root
            self._insert_non_full(new_root, key)
        else:
            self._insert_non_full(root, key)
    
    def _split_child(self, parent, index):
        """分裂子节点"""
        t = self.t
        y = parent.children[index]
        z = BTreeNode(leaf=y.leaf)
        
        # 将 y 的后半部分移到 z
        z.keys = y.keys[t:]
        if not y.leaf:
            z.children = y.children[t:]
        
        # 中间键上移到父节点
        parent.keys.insert(index, y.keys[t-1])
        parent.children.insert(index + 1, z)
        
        # 调整 y
        y.keys = y.keys[:t-1]
        if not y.leaf:
            y.children = y.children[:t]
    
    def _insert_non_full(self, node, key):
        """向非满节点插入键"""
        if node.leaf:
            # 叶子节点：直接插入
            i = len(node.keys) - 1
            node.keys.append(0)
            while i >= 0 and key < node.keys[i]:
                node.keys[i + 1] = node.keys[i]
                i -= 1
            node.keys[i + 1] = key
        else:
            # 内部节点：找到合适的子节点
            i = len(node.keys) - 1
            while i >= 0 and key < node.keys[i]:
                i -= 1
            i += 1
            
            if len(node.children[i].keys) == 2 * self.t - 1:
                self._split_child(node, i)
                if key > node.keys[i]:
                    i += 1
            
            self._insert_non_full(node.children[i], key)

# 使用示例
btree = BTree(t=3)
for key in [10, 20, 5, 6, 12, 30, 7, 17]:
    btree.insert(key)

print(btree.search(6))   # 找到
print(btree.search(99))  # None

前缀树（Trie）​

前缀树是处理字符串的专用树结构，在自动补全、拼写检查、IP 路由中有广泛应用。

class TrieNode:
    """前缀树节点"""
    def __init__(self):
        self.children = {}  # 字符到子节点的映射
        self.is_end = False  # 是否是单词结尾
        self.count = 0      # 经过此节点的单词数

class Trie:
    """前缀树"""
    def __init__(self):
        self.root = TrieNode()
    
    def insert(self, word):
        """插入单词"""
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.count += 1
        node.is_end = True
    
    def search(self, word):
        """搜索单词是否存在"""
        node = self.root
        for char in word:
            if char not in node.children:
                return False
            node = node.children[char]
        return node.is_end
    
    def starts_with(self, prefix):
        """检查是否有以 prefix 开头的单词"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return False
            node = node.children[char]
        return True
    
    def get_words_with_prefix(self, prefix):
        """获取所有以 prefix 开头的单词"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return []
            node = node.children[char]
        
        # 从 node 开始收集所有单词
        words = []
        self._collect(node, prefix, words)
        return words
    
    def _collect(self, node, prefix, words):
        if node.is_end:
            words.append(prefix)
        for char, child in node.children.items():
            self._collect(child, prefix + char, words)
    
    def count_prefix(self, prefix):
        """统计以 prefix 开头的单词数量"""
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.count

# 自动补全示例
trie = Trie()
words = ["apple", "app", "application", "apply", "banana", "band"]
for word in words:
    trie.insert(word)

print(trie.get_words_with_prefix("app"))  # ['app', 'apple', 'application', 'apply']
print(trie.count_prefix("app"))           # 4

堆与优先队列​

堆是一种特殊的完全二叉树，用于实现优先队列。堆的性质保证了根节点总是最大（大顶堆）或最小（小顶堆）。

class MinHeap:
    """最小堆实现"""
    def __init__(self):
        self.heap = []
    
    def parent(self, i):
        return (i - 1) // 2
    
    def left_child(self, i):
        return 2 * i + 1
    
    def right_child(self, i):
        return 2 * i + 2
    
    def push(self, value):
        """插入元素"""
        self.heap.append(value)
        self._sift_up(len(self.heap) - 1)
    
    def pop(self):
        """弹出最小元素"""
        if not self.heap:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()
        
        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._sift_down(0)
        return min_val
    
    def peek(self):
        """查看最小元素"""
        return self.heap[0] if self.heap else None
    
    def _sift_up(self, i):
        """上浮调整"""
        while i > 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = \
                self.heap[self.parent(i)], self.heap[i]
            i = self.parent(i)
    
    def _sift_down(self, i):
        """下沉调整"""
        min_index = i
        left = self.left_child(i)
        right = self.right_child(i)
        
        if left < len(self.heap) and self.heap[left] < self.heap[min_index]:
            min_index = left
        if right < len(self.heap) and self.heap[right] < self.heap[min_index]:
            min_index = right
        
        if i != min_index:
            self.heap[i], self.heap[min_index] = self.heap[min_index], self.heap[i]
            self._sift_down(min_index)
    
    def heapify(self, arr):
        """从数组构建堆（O(n)）"""
        self.heap = arr[:]
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self._sift_down(i)

# 使用示例：堆排序
def heap_sort(arr):
    """堆排序"""
    heap = MinHeap()
    heap.heapify(arr)
    return [heap.pop() for _ in range(len(arr))]

print(heap_sort([5, 2, 8, 1, 9, 3]))  # [1, 2, 3, 5, 8, 9]

决策树算法​

决策树是机器学习中的一种分类和回归模型，其结构就是一棵树。

class DecisionTreeNode:
    """决策树节点"""
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature    # 划分特征
        self.threshold = threshold # 划分阈值
        self.left = left          # 左子树
        self.right = right        # 右子树
        self.value = value        # 叶节点的预测值

class DecisionTree:
    """简单的决策树分类器"""
    def __init__(self, max_depth=3):
        self.max_depth = max_depth
        self.root = None
    
    def fit(self, X, y):
        """训练决策树"""
        self.root = self._build_tree(X, y, depth=0)
    
    def predict(self, X):
        """预测"""
        return [self._predict_one(x, self.root) for x in X]
    
    def _build_tree(self, X, y, depth):
        """递归构建树"""
        # 停止条件
        if depth >= self.max_depth or len(set(y)) == 1:
            return DecisionTreeNode(value=max(set(y), key=y.count))
        
        # 找最佳划分
        best_feature, best_threshold = self._find_best_split(X, y)
        if best_feature is None:
            return DecisionTreeNode(value=max(set(y), key=y.count))
        
        # 划分数据
        left_indices = [i for i, x in enumerate(X) if x[best_feature] <= best_threshold]
        right_indices = [i for i, x in enumerate(X) if x[best_feature] > best_threshold]
        
        if not left_indices or not right_indices:
            return DecisionTreeNode(value=max(set(y), key=y.count))
        
        left_X = [X[i] for i in left_indices]
        left_y = [y[i] for i in left_indices]
        right_X = [X[i] for i in right_indices]
        right_y = [y[i] for i in right_indices]
        
        return DecisionTreeNode(
            feature=best_feature,
            threshold=best_threshold,
            left=self._build_tree(left_X, left_y, depth + 1),
            right=self._build_tree(right_X, right_y, depth + 1)
        )
    
    def _find_best_split(self, X, y):
        """找最佳划分（信息增益）"""
        best_gain = 0
        best_feature = None
        best_threshold = None
        
        for feature in range(len(X[0])):
            thresholds = set(x[feature] for x in X)
            for threshold in thresholds:
                gain = self._information_gain(X, y, feature, threshold)
                if gain > best_gain:
                    best_gain = gain
                    best_feature = feature
                    best_threshold = threshold
        
        return best_feature, best_threshold
    
    def _information_gain(self, X, y, feature, threshold):
        """计算信息增益"""
        # 简化实现
        def entropy(labels):
            from math import log2
            if not labels:
                return 0
            probs = [labels.count(c) / len(labels) for c in set(labels)]
            return -sum(p * log2(p) for p in probs if p > 0)
        
        left_y = [y[i] for i, x in enumerate(X) if x[feature] <= threshold]
        right_y = [y[i] for i, x in enumerate(X) if x[feature] > threshold]
        
        n = len(y)
        return entropy(y) - (len(left_y) / n * entropy(left_y) + 
                            len(right_y) / n * entropy(right_y))
    
    def _predict_one(self, x, node):
        """预测单个样本"""
        if node.value is not None:
            return node.value
        if x[node.feature] <= node.threshold:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)

# 示例
X = [[1, 2], [1, 4], [2, 2], [3, 4], [4, 5]]
y = [0, 0, 0, 1, 1]
tree = DecisionTree(max_depth=2)
tree.fit(X, y)
print(tree.predict([[1, 3], [4, 4]]))  # [0, 1]

小结​

本章介绍了树的基础知识：

  1. 树的定义：无向连通无环图，及其等价刻画
  2. 基本术语：根、叶子、深度、高度、子树
  3. 二叉树：定义、性质、遍历方式（前序、中序、后序、层次）
  4. 二叉搜索树：定义、查找、插入操作
  5. 生成树：定义、存在性、最小生成树
  6. 树的计数：Cayley 公式
  7. 树的应用：文件系统、表达式树、哈夫曼编码、决策树
  8. 高级应用：抽象语法树、B 树索引、前缀树、堆、决策树算法

树是数据结构的核心，也是算法设计的重要工具。理解树的性质和操作，是学习高级数据结构（如堆、平衡树、B 树）的基础。树结构的递归特性也使其成为递归算法的理想载体。

练习​

  1. 证明：n≥2n \geq 2 的树至少有两个叶子。

  2. 给定二叉树的前序遍历序列 [1, 2, 4, 5, 3, 6, 7] 和中序遍历序列 [4, 2, 5, 1, 6, 3, 7]，画出这棵二叉树。

  3. 实现 BST 的删除操作，处理三种情况：删除叶子、删除有一个孩子的节点、删除有两个孩子的节点。

  4. 计算 5 个标号顶点的树的数量，并列举其中的 5 棵。

  5. 设计一个算法，判断一棵二叉树是否为二叉搜索树。