背景

本文是《Java 后端从小白到大神》修仙系列第五篇，正式进入Java后端世界，本篇文章主要聊Java基础。若想详细学习请点击首篇博文，我们开始把。

文章概览

数据结构

数据结构（续）

1. 堆（Heap）

定义：一种完全二叉树，满足父节点与子节点的特定顺序关系（最小堆/最大堆）。默认情况下，PriorityQueue是按照自然顺序（即元素的自然大小顺序）实现的，对于数值类型，这意味着它是一个最小堆。如果要实现最大堆，则需要提供一个自定义的Comparator。
Java 实现：通过 PriorityQueue 类实现。
代码示例：

// 最小堆（默认）
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.add(5);
minHeap.add(3);
System.out.println(minHeap.poll()); // 输出 3

// 最大堆（需自定义 Comparator）
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
maxHeap.add(5);
maxHeap.add(3);
System.out.println(maxHeap.poll()); // 输出 5

2. 树（Tree）

1.树结构（Tree）

定义：树是一种分层数据结构，由节点（Node）和边（Edge）组成，满足以下条件：
- 每个节点有零个或多个子节点。
- 只有一个根节点（Root），无父节点。
- 除根节点外，其他节点有且仅有一个父节点。
代码示例

// 树节点定义
class TreeNode<T> {
    T data;
    List<TreeNode<T>> children; // 子节点列表

    public TreeNode(T data) {
        this.data = data;
        this.children = new ArrayList<>();
    }
}

// 遍历树 方法1：
public static <T> void traverseTree(TreeNode<T> root) {
    if (root == null) {
        return;
    }
    Stack<TreeNode<T>> stack = new Stack<>();
    stack.push(root);

    while (!stack.isEmpty()) {
        TreeNode<T> node = stack.pop();
        System.out.print(node.data + " ");
        for (int i = node.children.size() - 1; i >= 0; i--) {
            stack.push(node.children.get(i));
        }
    }
}

// 递归遍历树 方法2：
public static <T> void traverseTree(TreeNode<T> node) {
    if (node == null) {
        return;
    }
    System.out.print(node.data + " ");
    for (TreeNode<T> child : node.children) {
        traverseTree(child);
    }
}

// 创建树
TreeNode<String> root = new TreeNode<String>("Root");
TreeNode<String> child1 = new TreeNode<String>("Child1");
TreeNode<String> child2 = new TreeNode<String>("Child2");
TreeNode<String> grandchild1 = new TreeNode<String>("Grandchild1");
TreeNode<String> grandchild2 = new TreeNode<String>("Grandchild2");
root.children.add(child1);
root.children.add(child2);
child1.children.add(grandchild1);
child1.children.add(grandchild2);

2. 二叉树（Binary Tree）

定义：二叉树的每个节点最多有两个子节点，称为左子节点（Left Child）和右子节点（Right Child）。
二叉搜索树（BST）：左子树所有节点值 < 根节点值 < 右子树所有节点值。
完全二叉树：除最后一层外，其他层节点数达到最大，且最后一层节点向左对齐。

代码示例：

// 二叉树节点定义
class BinaryTreeNode<T> {
    T data;
    BinaryTreeNode<T> left;
    BinaryTreeNode<T> right;

    public BinaryTreeNode(T data) {
        this.data = data;
    }
}

// 遍历二叉树
public static <T> void traverseBinaryTree(BinaryTreeNode<T> broot) {
    if (broot == null) {
        return;
    }
    System.out.print(broot.data + " ");
    traverseBinaryTree(broot.left);
    traverseBinaryTree(broot.right);
}

// 创建二叉树
BinaryTreeNode<Integer> root = new BinaryTreeNode<>(10);
root.left = new BinaryTreeNode<>(5);
root.right = new BinaryTreeNode<>(15);
root.left.right = new BinaryTreeNode<>(7);

3. 红黑树（Red-Black Tree）

定义：红黑树（Red-Black Tree）是一种自平衡二叉搜索树（Self-Balancing Binary Search Tree）。它通过引入一组规则来确保树的高度始终保持在对数级别（O(log n)），从而保证插入、删除和查找操作的时间复杂度为 O(log n)。

红黑树的性质：红黑树的每个节点都有一个颜色属性，可以是红色或黑色。为了保持树的平衡性，红黑树遵循以下规则：

根叶黑：
- 根节点和叶子节点必须是黑色，这里叶子节点是指树最底层的叶子节点。
黑路同：
- 每个结点到任意叶结点的所有路径上的黑色结点数量都是相同的。
左根右：
- 满足二叉搜索树(BST)，即:左<根<右。
不红红：不存在两个连续的红色节点。

红黑树插入节点规则：

插入结点默认是红色结点
如果插入后性质被破坏，则根据下面三种情况做调整:
- 插入结点是根结点，颜色直接变黑。
- 插入结点的叔叔节点是红色，叔父爷变色，爷爷变插入结点，继续判断爷爷是否满足红黑树性质，如果满足则结束，如果不满足则继续调整。
- 插入结点的叔叔节点是黑色，根据LL\RR\LR\RL四种情况调整。
  - 若LL，则右旋：向右转爷爷节点，父亲为旋转中心点，将爷爷和父亲变色。
  - 若RR，则左旋：向左转爷爷节点，父亲为旋转中心点，将爷爷和父亲变色。
  - 若LR，则先左旋父亲节点，再右旋爷爷节点，父亲为旋转中心点，将爷爷和父亲变色。
  - 若RL，则先右旋父亲节点，再左旋爷爷节点，父亲为旋转中心点，将爷爷和父亲变色。

红黑树的作用：红黑树的主要作用是提供一种高效的动态数据结构，用于存储和检索有序数据。相比于普通的二叉搜索树，红黑树通过自平衡机制避免了退化成链表的情况，从而保证了操作的高效性。它适用于需要高效动态数据管理的场景，如 Java 的 TreeMap 和 TreeSet

Java 集合框架：
- TreeMap 和 TreeSet 的底层实现基于红黑树。
操作系统：
- 文件系统中的目录管理。
数据库：
- 索引结构（如 B+ 树的变体）。
语言运行时：
- Java 的 ConcurrentHashMap 在桶中使用红黑树优化链表性能。

红黑树的操作：
1. 插入操作：插入新节点时，可能会破坏红黑树的规则，因此需要通过一系列旋转和重新着色操作来恢复平衡。

步骤：
- 将新节点插入到树中，并将其颜色设置为红色。
- 检查是否违反红黑树规则。
- 如果违反规则，执行旋转和重新着色操作以恢复平衡。
旋转类型：
- 左旋（Left Rotation）：将右子节点提升为父节点。
- 右旋（Right Rotation）：将左子节点提升为父节点。

2. 删除操作：删除节点时，可能会导致树失去平衡，因此需要调整树的结构。

步骤：
- 找到要删除的节点。
- 如果删除的是黑色节点，可能会违反红黑树规则。
- 通过旋转和重新着色操作恢复平衡。

代码示例：

class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;

    class Node {
        int key;
        Node left, right;
        boolean color;

        Node(int key, boolean color) {
            this.key = key;
            this.color = color;
        }
    }

    private Node root;

    public void insert(int key) {
        root = insert(root, key);
        root.color = BLACK; // 根节点始终为黑色
    }

    private Node insert(Node node, int key) {
        if (node == null) {
            return new Node(key, RED); // 新插入的节点为红色
        }

        if (key < node.key) {
            node.left = insert(node.left, key);
        } else if (key > node.key) {
            node.right = insert(node.right, key);
        } else {
            node.key = key; // 更新键值
        }

        // 平衡调整
        if (isRed(node.right) && !isRed(node.left)) {
            node = rotateLeft(node); // 左旋
        }
        if (isRed(node.left) && isRed(node.left.left)) {
            node = rotateRight(node); // 右旋
        }
        if (isRed(node.left) && isRed(node.right)) {
            flipColors(node); // 重新着色
        }

        return node;
    }

    private boolean isRed(Node node) {
        if (node == null) return false;
        return node.color == RED;
    }

    private Node rotateLeft(Node node) {
        Node x = node.right;
        node.right = x.left;
        x.left = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    private Node rotateRight(Node node) {
        Node x = node.left;
        node.left = x.right;
        x.right = node;
        x.color = node.color;
        node.color = RED;
        return x;
    }

    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }
}

对比总结：

特性	树（Tree）	二叉树（Binary Tree）	红黑树（Red-Black Tree）
子节点数量	任意	最多2个	最多2个（自平衡二叉搜索树）
主要用途	分层数据（如目录结构）	高效查找/插入（如BST）	保证动态操作的高效性（O(log n)）
Java实现	需自定义	需自定义	`TreeMap`, `TreeSet`

选择建议：

需要有序键值对 → 红黑树（TreeMap）。
简单分层数据 → 普通树或二叉树。
高频动态插入/删除 → 红黑树（避免普通BST退化为链表）。

4. 树的遍历（Tree Traversal）

1. 前序遍历（Preorder）：

顺序：根节点 → 左子树 → 右子树
应用场景：复制二叉树、前缀表达式（波兰表达式）
代码示例：

递归实现：

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
}

public void preorder(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " "); // 访问根节点
    preorder(root.left);              // 遍历左子树
    preorder(root.right);             // 遍历右子树
}

迭代实现（栈）：

public void preorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root);
    while (!stack.isEmpty()) {
        TreeNode node = stack.pop();
        System.out.print(node.val + " ");
        if (node.right != null) stack.push(node.right); // 右子先入栈
        if (node.left != null) stack.push(node.left);    // 左子后入栈
    }
}

2. 中序遍历（Inorder）：

顺序：左子树 → 根节点 → 右子树
应用场景：二叉搜索树（BST）的有序输出
代码示例：

递归实现：

public void inorder(TreeNode root) {
    if (root == null) return;
    inorder(root.left);               // 遍历左子树
    System.out.print(root.val + " "); // 访问根节点
    inorder(root.right);              // 遍历右子树
}

迭代实现（栈）：

public void inorderIterative(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode curr = root;
    while (curr != null || !stack.isEmpty()) {
        while (curr != null) {
            stack.push(curr);         // 左子节点入栈
            curr = curr.left;
        }
        curr = stack.pop();
        System.out.print(curr.val + " ");
        curr = curr.right;            // 转向右子树
    }
}

3. 后序遍历（Postorder）：

顺序：左子树 → 右子树 → 根节点
应用场景：释放二叉树内存、后缀表达式（逆波兰表达式）
代码示例：

递归实现：

public void postorder(TreeNode root) {
    if (root == null) return;
    postorder(root.left);             // 遍历左子树
    postorder(root.right);            // 遍历右子树
    System.out.print(root.val + " "); // 访问根节点
}

迭代实现（双栈）：

public void postorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    while (!stack1.isEmpty()) {
        TreeNode node = stack1.pop();
        stack2.push(node);             // 根节点先压入 stack2
        if (node.left != null) stack1.push(node.left);
        if (node.right != null) stack1.push(node.right);
    }
    while (!stack2.isEmpty()) {
        System.out.print(stack2.pop().val + " ");
    }
}

4. 层序遍历（Level Order）：

顺序：按层从上到下、每层从左到右访问
应用场景：按层次处理数据（如二叉树深度、广度优先搜索）
代码示例（队列实现）：

public void levelOrder(TreeNode root) {
    if (root == null) return;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int levelSize = queue.size();
        for (int i = 0; i < levelSize; i++) {
            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);
        }
        System.out.println(); // 按层换行（可选）
    }
}

总结：

遍历方式	顺序	递归时间复杂度	迭代辅助结构
前序遍历	根 → 左 → 右	O(n)	栈
中序遍历	左 → 根 → 右	O(n)	栈
后序遍历	左 → 右 → 根	O(n)	双栈
层序遍历	按层从左到右	O(n)	队列

根据需求选择遍历方式：

前序：快速复制二叉树结构。
中序：BST 输出有序序列。
后序：释放内存避免野指针。
层序：按层次分析数据（如求二叉树深度）。

3. 图（Graphs）

定义：由顶点（Vertex）和边（Edge）组成的非线性结构。
Java 实现：无内置类，一般用邻接表或邻接矩阵表示。

代码示例（邻接表）：

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.put(1, Arrays.asList(2, 3)); // 顶点1连接顶点2和3
graph.put(2, Arrays.asList(3));
graph.put(3, Arrays.asList(1));
System.out.println(graph.get(1)); // 输出 [2, 3]

4. 其他数据结构

1. 枚举（Enumeration）

定义：固定常量的集合。
Java 实现：通过 enum 关键字定义。

代码示例：

1
2
3

enum Day { MONDAY, TUESDAY, WEDNESDAY }
Day today = Day.MONDAY;
System.out.println(today); // 输出 MONDAY

2. 位集合（BitSet）

定义：动态大小的位数组，支持位运算。
Java 实现：BitSet 类。

代码示例：

BitSet bits = new BitSet(8);
bits.set(2);      // 设置第2位为1
bits.set(4);
System.out.println(bits.get(2)); // 输出 true

3. 字典（Dictionary）

定义：键值对的抽象类（已过时，推荐使用 Map 接口）。
Java 实现：Hashtable 是其子类。

代码示例：

1
2
3

Dictionary<Integer, String> dict = new Hashtable<>();
dict.put(1, "One");
System.out.println(dict.get(1)); // 输出 One

4. 哈希表（Hashtable）

定义：线程安全的键值对存储（键和值均不可为 null）。
Java 实现：Hashtable 类。

代码示例：

Hashtable<String, Integer> table = new Hashtable<>();
table.put("A", 1);
table.put("B", 2);
System.out.println(table.get("A")); // 输出 1

5. 属性（Properties）

定义：继承自 Hashtable，专用于处理配置文件（.properties）。
Java 实现：Properties 类。

代码示例：

1
2
3

Properties props = new Properties();
props.setProperty("user", "admin");
props.store(new FileWriter("config.properties"), "User Settings");

总结

数据结构	用途	典型实现类
堆	优先级任务调度	`PriorityQueue`
树	有序数据存储（如排序、查找）	`TreeMap`, `TreeSet`
图	网络关系建模（如社交网络）	自定义邻接表/邻接矩阵
枚举	定义固定常量集合	`enum`
位集合	高效位操作（如权限管理）	`BitSet`
哈希表	线程安全的键值存储	`Hashtable`
属性	配置文件读写	`Properties`

根据需求选择合适的数据结构：

高频增删 → LinkedList（链表）。
快速查找 → HashMap（哈希表）。
有序数据 → TreeMap（红黑树）。
线程安全 → ConcurrentHashMap 或 Hashtable。