元数据卡

• 前置知识：链表（第2章）、递归（Vol 1 ch05）
• 预计时间：12 分钟
• 完成标志：能实现二叉树遍历和 BST 查找

---

树是什么

数组和链表是一维的——每个元素只有一个"下一个"。树是二维的：每个节点可以有多个"孩子"。

二叉树就是每个节点最多有两个子节点（左和右）。

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

二叉树的遍历

# 前序遍历：根 → 左 → 右
def preorder(root):
    if root is None:
        return
    print(root.val)   # 先访问根
    preorder(root.left)   # 再左子树
    preorder(root.right)  # 最后右子树

# 中序遍历：左 → 根 → 右（对 BST，就是从小到大输出）
def inorder(root):
    if root is None:
        return
    inorder(root.left)
    print(root.val)
    inorder(root.right)

# 后序遍历：左 → 右 → 根
def postorder(root):
    if root is None:
        return
    postorder(root.left)
    postorder(root.right)
    print(root.val)

遍历方式	顺序	用途
前序	根→左→右	复制树、序列化
中序	左→根→右	BST 排序输出
后序	左→右→根	删除树、计算目录大小

二叉搜索树（BST）

BST 的核心性质：左子树所有节点 < 根节点 < 右子树所有节点。

class BST:
    def search(self, root, target):
        if root is None or root.val == target:
            return root
        if target < root.val:
            return self.search(root.left, target)
        return self.search(root.right, target)
    
    def insert(self, root, val):
        if root is None:
            return TreeNode(val)
        if val < root.val:
            root.left = self.insert(root.left, val)
        else:
            root.right = self.insert(root.right, val)
        return root

BST 的查找复杂度：平均 O(log n)，最差 O(n)（退化成链表时）。

---

旅人笔记

二叉树是递归定义的数据结构。前/中/后序遍历分别适合不同场景。BST 利用左小右大的性质实现 O(log n) 查找——但需要树是平衡的。

→ 下一步：树的遍历

深度优先 vs 广度优先——两种截然不同的探索方式。

看遍历详解 →