CS61B 课程笔记（Lecture 25 Advanced Trees, incl)

树的基本概念

1. 树的定义

  • 树 (Tree): 一种数据结构，由节点组成，具有层级关系。每个树都有一个根节点（root），根节点没有父节点。
  • 节点 (Node): 树的基本单位，包含数据和指向其子节点的引用。
  • 父节点 (Parent): 除根节点外，每个节点都有一个父节点。
  • 子节点 (Child): 每个节点可以有零个或多个子节点。
  • 叶子节点 (Leaf): 没有子节点的节点。

2. 树的性质

  • 在一棵树中，如果一个节点有两个父节点，则它不是树（树的定义不允许节点有多个父节点）。

树的遍历

遍历是访问树中每个节点的过程，有多种遍历方式，主要分为深度优先遍历 (Depth-First Search, DFS) 和 广度优先遍历 (Breadth-First Search, BFS)。

1. 广度优先遍历 (Level Order Traversal)

  • 方法: 按照层级从上到下、从左到右访问每个节点。
  • 实现: 使用队列 (Queue) 来存储节点。

示例代码:

1
2
3
4
5
6
7
8
9
10
11
void levelOrderTraversal(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.val + " ");
        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

2. 深度优先遍历 (DFS)

DFS 包括三种主要的遍历方式：前序 (Pre-order)、中序 (In-order) 和后序 (Post-order)。

2.1 前序遍历 (Pre-order Traversal)

  • 访问顺序: 访问根节点 → 左子树 → 右子树。
  • 实现: 递归或使用栈。

示例代码:

1
2
3
4
5
6
void preOrderTraversal(TreeNode node) {
    if (node == null) return;
    System.out.print(node.val + " ");
    preOrderTraversal(node.left);
    preOrderTraversal(node.right);
}

2.2 中序遍历 (In-order Traversal)

  • 访问顺序: 左子树 → 访问根节点 → 右子树。
  • 实现: 递归或使用栈。

示例代码:

1
2
3
4
5
6
void inOrderTraversal(TreeNode node) {
    if (node == null) return;
    inOrderTraversal(node.left);
    System.out.print(node.val + " ");
    inOrderTraversal(node.right);
}

2.3 后序遍历 (Post-order Traversal)

  • 访问顺序: 左子树 → 右子树 → 访问根节点。
  • 实现: 递归或使用栈。

示例代码:

1
2
3
4
5
6
void postOrderTraversal(TreeNode node) {
    if (node == null) return;
    postOrderTraversal(node.left);
    postOrderTraversal(node.right);
    System.out.print(node.val + " ");
}

进阶主题

1. 访问者模式 (Visitor Pattern)

为了避免为每个操作重复编写遍历代码，可以使用访问者模式，该模式允许将操作封装为对象并传递给遍历方法。

示例代码:

1
2
3
4
5
6
7
8
9
10
interface Visitor {
    void visit(TreeNode node);
}

void traverse(TreeNode node, Visitor visitor) {
    if (node == null) return;
    visitor.visit(node);
    traverse(node.left, visitor);
    traverse(node.right, visitor);
}

2. 范围查找与修剪 (Range Finding and Pruning)

在二叉搜索树 (BST) 中，可以通过修剪无关子树来提高查找效率。例如，要查找介于 A 和 B 之间的所有元素时，如果当前节点的值小于 A，则无需搜索左子树。

时间复杂度: 运行时间为 \(Θ(R + \log N)\)，其中 R 是匹配的数量，N 是节点总数。

3. 四叉树 (Quadtrees)

对于二维范围查找，可以使用四叉树结构。每个节点有四个子节点，分别代表左上、右上、右下和左下四个象限。

示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
class QuadtreeNode {
    QuadtreeNode nw, ne, sw, se; // 四个子节点
    Point point; // 存储点

    void insert(Point p) {
        // 插入逻辑，依据点的位置选择适当的子节点
    }
    
    List<Point> rangeQuery(Rectangle range) {
        // 范围查询逻辑
    }
}