Java 树终极指南：从根到枝（还有叶子！）-java教程-PHP中文网

The Ultimate Guide to Trees in Java: From Roots to Branches (and Leaves, too!)

1. 树木简介

啊，这棵不起眼的树。不仅仅是窗外的枝繁叶茂的结构，而是计算机科学中基本的、多用途的数据结构。树无处不在——从文件系统到解析表达式和管理数据库。了解树木就像爬树一样，但别担心——我将成为你这段旅程的安全带、头盔和向导。

2. 什么是树？

树是一种分层数据结构，由通过边连接的节点组成。与您童年的树屋不同，那里充满了乐趣和游戏，计算机科学树是严肃的事情：

根节点：起点，就像公司的CEO一样——每个人最终都向他汇报。
子节点：直接连接到另一个节点（其父节点）下方的节点。
父节点：孩子正上方的节点（如监护人）。
叶节点：没有任何子节点的节点。他们是队伍的末端（又称退休前的最后一批员工）。
子树：较大结构中的一棵迷你树，可能形成自己的分裂团队。
深度：从根到特定节点的边数。
高度：从节点到最深叶子的边数。

3. 为什么是树？目的

为什么要使用树木？很高兴你问了。树木非常适合：

分层数据表示：文件系统、组织结构、决策树。
搜索和排序：二叉搜索树（BST）可以在 O(log n) 时间内进行搜索。
数据管理：高效的存储和检索，例如数据库（B 树）。
动态数据：当您需要动态更改大小或内容的结构时，树非常有用。

4. 树木的类型及其用例

4.1 二叉树

定义：每个节点最多有两个子节点（左和右）。
目的：简单高效的遍历。非常适合表示分层数据和二进制表达式。

4.2 二叉搜索树（BST）

定义：带有附加约束的二叉树 - 左子节点小于父节点，右子节点大于父节点。
用途：快速查找、插入、删除。

代码示例：

class TreeNode {
    int value;
    TreeNode left, right;

    public TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

登录后复制

4.3 平衡树（例如 AVL、红黑）

AVL树：自平衡二叉搜索树，左右子树的高度差不能大于1。
红黑树：平衡二叉搜索树，其属性确保没有路径的长度超过其他路径的两倍。
目的：保持O(log n)时间进行插入、删除和搜索操作。

4.4 N 叉树

定义：一棵树，其中每个节点最多可以有 N 个子节点。
用途：比二叉树更灵活，通常用于表示更复杂的结构，例如文件系统。

4.5 Trie（前缀树）

定义：用于存储字符串的树，其中每个节点代表一个字符。
目的：快速查找单词和前缀（例如自动完成功能）。

4.6 线段树和Fenwick树

线段树：用于高效地回答数组上的范围查询。
芬威克树：一种更简单、节省空间的树，用于累积频率表。

5. 树遍历技术

穿过一棵树，就像拜访了公司的每一位员工。你如何做很重要：

5.1 深度优先搜索（DFS）

预购：访问根，然后向左，然后向右。非常适合创建树的副本。
有序：左、根、右。对于 BST 按升序获取元素很有用。
后序：左、右、根。适合删除树（例如解雇反向层次结构中的员工）。

DFS 示例:

void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

登录后复制

5.2 广度优先搜索（BFS）

层序遍历：逐层访问节点。最短路径问题的理想选择。

使用队列实现:

class TreeNode {
    int value;
    TreeNode left, right;

    public TreeNode(int item) {
        value = item;
        left = right = null;
    }
}

登录后复制

6. 树算法及其应用

6.1 BST 中的插入和删除

插入：递归地将新节点放置在正确的位置。
删除：三种情况——叶节点删除、一个子节点和两个子节点（替换为有序后继节点）。

6.2 平衡树

旋转：用于 AVL 和红黑树以保持平衡。
- 单次右旋转（LL 旋转）
- 单向左旋转（RR 旋转）
- 左右双旋转（RL 旋转）
- 左右双旋转（LR 旋转）

6.3 最低共同祖先（LCA）问题

定义：查找作为两个给定节点的祖先的最低节点。
技术：递归检查当前节点对于两个给定节点是否是公共的。

LCA 代码示例:

void inOrder(TreeNode node) {
    if (node == null) return;
    inOrder(node.left);
    System.out.print(node.value + " ");
    inOrder(node.right);
}

登录后复制

7. 树的记忆排列

树通常使用以下方式在内存中表示：

基于节点的动态表示：每个节点都是一个带有指向其子节点的指针（引用）的对象。
数组表示：用于完全二叉树，其中左子节点位于 2*i 1 ，右子节点位于 2*i 2 （0 索引）。

视觉表现：

void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.value + " ");
        if (node.left != null) queue.add(node.left);
        if (node.right != null) queue.add(node.right);
    }
}

登录后复制