Java中的二叉树算法

⚡ 二叉树:Java算法体系的核心基石

在Java开发的进阶之路上,二叉树(Binary Tree)作为最基础却最具扩展性的非线性数据结构,不仅是算法面试中的高频考点,更是理解更复杂树形结构(如AVL树、红黑树、B+树)的理论根基。本文将从零基础出发,系统梳理Java中二叉树的定义、特性、遍历方式、典型操作、自平衡机制及实际应用场景,辅以大量可运行的代码示例与深度解析,助您构建完整的树形结构知识体系。

与线性结构(数组、链表)不同,二叉树具有天然的层次性与分支性,其每个节点最多拥有两个子节点(左子节点与右子节点),这种结构天然适配“分治思想”,在查找、排序、表达式求值、文件系统路径管理等场景中展现出卓越性能。尤其在JDK源码中,如TreeMap、TreeSet、ConcurrentSkipListMap等核心集合类,其底层实现均深度依赖二叉搜索树(BST)及其变种——自平衡二叉搜索树(如红黑树),因此深入掌握二叉树,是理解Java高级特性的必经之路。

值得注意的是,二叉树本身并非Java原生类库的一部分,开发者需通过自定义类(Node/TreeNode)或使用第三方库(如Apache Commons Collections、JGraphT)构建。本文将采用纯Java原生代码实现所有数据结构,确保逻辑清晰、易于迁移与调试。

⚙️ 二叉树基础:定义、类型与核心属性

1. 定义与基本构成

二叉树是n(n≥0)个节点的有限集合,该集合或为空树(n=0),或由一个根节点及两棵互不相交的、分别称为左子树与右子树的二叉树组成。其递归定义强调了“左/右子树”的独立性与有序性——即左子树与右子树不可交换,这是与普通树的本质区别。

Java中典型节点类定义如下:

class TreeNode {
    int val;                // 节点存储的值
    TreeNode left;          // 左子节点引用
    TreeNode right;         // 右子节点引用
    TreeNode(int val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

2. 关键术语与图示说明

3. 二叉树的五种基本形态

  1. 空树
  2. 仅含根节点
  3. 根节点 + 左子树
  4. 根节点 + 右子树
  5. 根节点 + 左子树 + 右子树

4. 特殊二叉树类型

⑴ 满二叉树(Full Binary Tree)

所有分支节点均存在左右子树,且所有叶子节点位于同一层。高度为h的满二叉树共有2h - 1个节点。其节点编号具有严格规律:第i层有2i-1个节点(i从1开始)。

⑵ 完全二叉树(Complete Binary Tree)

除最后一层外,其余层均被填满;最后一层节点从左到右连续填充。完全二叉树可用数组高效存储(索引i的左子为2i+1,右子为2i+2),堆结构即基于此。JDK中PriorityQueue底层即为最小堆的数组实现。

⑶ 二叉搜索树(Binary Search Tree, BST)

满足如下性质的二叉树:对任一节点,其左子树所有节点值 < 当前节点值 < 右子树所有节点值。BST支持O(log n)时间复杂度的查找、插入、删除操作(最坏退化为O(n))。TreeMap与TreeSet即基于红黑树(一种自平衡BST)实现。

⑷ 平衡二叉树(Balanced Binary Tree)

任意节点左右子树高度差不超过1。典型代表为AVL树与红黑树,二者通过旋转操作维持平衡,确保操作复杂度稳定在O(log n)。

⚡ 二叉树遍历:递归与迭代的完整实现

遍历是二叉树操作的基础,指按某种策略访问所有节点且不重复。Java中常见遍历方式包括前序、中序、后序、层序四种,每种又可分为递归与非递归(迭代)实现,后者常需借助栈或队列模拟系统调用栈。

1. 前序遍历(Preorder:根 → 左 → 右)

应用场景:复制二叉树、表达式树求值(前缀表达式)

// 递归实现
public static void preorderRecursive(TreeNode root) {
    if (root == null) return;
    System.out.print(root.val + " ");
    preorderRecursive(root.left);
    preorderRecursive(root.right);
}
// 迭代实现(用栈)
public static 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)进行中序遍历,结果必为递增序列。常用于验证BST合法性或获取有序数据。

// 递归实现
public static void inorderRecursive(TreeNode root) {
    if (root == null) return;
    inorderRecursive(root.left);
    System.out.print(root.val + " ");
    inorderRecursive(root.right);
}
// 迭代实现(用栈模拟递归)
public static 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 static void postorderRecursive(TreeNode root) {
    if (root == null) return;
    postorderRecursive(root.left);
    postorderRecursive(root.right);
    System.out.print(root.val + " ");
}
// 迭代实现(双栈法)
public static void postorderIterative(TreeNode root) {
    if (root == null) return;
    Stack<TreeNode> s1 = new Stack<>(), s2 = new Stack<>();
    s1.push(root);
    while (!s1.isEmpty()) {
        TreeNode node = s1.pop();
        s2.push(node);
        if (node.left != null) s1.push(node.left);
        if (node.right != null) s1.push(node.right);
    }
    while (!s2.isEmpty()) {
        System.out.print(s2.pop().val + " ");
    }
}

4. 层序遍历(Level Order:逐层从左到右)

本质是广度优先搜索(BFS),使用队列实现。常用于求树的最大深度、按层打印节点。

public static List<List<Integer>> levelOrder(TreeNode root) {
    List<List<Integer>> result = new ArrayList<>();
    if (root == null) return result;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while (!queue.isEmpty()) {
        int size = queue.size();
        List<Integer> level = new ArrayList<>();
        for (int i = 0; i < size; i++) {
            TreeNode node = queue.poll();
            level.add(node.val);
            if (node.left != null) queue.offer(node.left);
            if (node.right != null) queue.offer(node.right);
        }
        result.add(level);
    }
    return result;
}

⚡ 二叉搜索树(BST):高效动态查找表

1. BST核心操作详解

在BST中,查找、插入、删除操作的时间复杂度均为O(h),其中h为树高。平均情况下h≈log n,最坏(退化为链表)为O(n)。以下为标准实现:

// 查找目标值
public static TreeNode searchBST(TreeNode root, int target) {
    if (root == null || root.val == target) return root;
    return target < root.val ? searchBST(root.left, target) : searchBST(root.right, target);
}
// 插入新值(保持BST性质)
public static TreeNode insertBST(TreeNode root, int val) {
    if (root == null) return new TreeNode(val);
    if (val < root.val) root.left = insertBST(root.left, val);
    else if (val > root.val) root.right = insertBST(root.right, val);
    return root;
}
// 删除值为key的节点
public static TreeNode deleteNode(TreeNode root, int key) {
    if (root == null) return null;
    if (key < root.val) root.left = deleteNode(root.left, key);
    else if (key > root.val) root.right = deleteNode(root.right, key);
    else { // 找到目标节点
        if (root.left == null) return root.right;
        if (root.right == null) return root.left;
        // 两子树均存在:找右子树最小值(或左子树最大值)替换
        TreeNode minRight = findMin(root.right);
        root.val = minRight.val;
        root.right = deleteNode(root.right, minRight.val);
    }
    return root;
}
private static TreeNode findMin(TreeNode node) {
    while (node.left != null) node = node.left;
    return node;
}

2. BST的局限性与自平衡必要性

若插入序列有序(如1→2→3→4→5),BST将退化为单链表,查找效率降至O(n)。例如:连续插入升序整数后,树结构如下:

    1
     \
      2
       \
        3
         \
          4
           \
            5

此问题催生了自平衡二叉搜索树家族——通过旋转操作(左旋、右旋)动态维持平衡,确保任意节点左右子树高度差≤1(AVL)或高度比≤2(红黑树)。

⚙️ AVL树:严格的自平衡二叉搜索树

1. 平衡因子与旋转原理

AVL树要求每个节点的平衡因子(左子树高度 - 右子树高度)∈ {-1, 0, 1}。插入/删除后若失衡,需通过旋转调整:

2. AVL树核心操作(伪代码级说明)

// 右旋(LL型调整)
TreeNode rotateRight(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;
    x.right = y;
    y.left = T2;
    // 更新高度
    y.height = max(height(y.left), height(y.right)) + 1;
    x.height = max(height(x.left), height(x.right)) + 1;
    return x; // 新根节点
}
// 左旋(RR型调整)
TreeNode rotateLeft(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;
    y.left = x;
    x.right = T2;
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;
    return y;
}

3. AVL树 vs 红黑树:性能对比

特性 AVL树 红黑树
平衡条件 高度差 ≤ 1 任意路径黑高相等;无双红节点
插入/删除调整 最多O(log n)次旋转 最多2次旋转 + O(log n)次变色
查找效率 更优(高度更低) 略逊于AVL
更新效率 较慢(旋转频繁) 更快(调整开销小)
典型应用 读多写少场景(如数据库索引) Java集合(TreeMap/TreeSet)、Linux进程调度

⚡ 红黑树:Java集合框架的基石

1. 红黑树五条基本性质

  1. 节点非红即黑
  2. 根节点为黑
  3. 叶子节点(null)为黑
  4. 红节点的子节点必为黑
  5. 任一节点到其子孙叶子的简单路径上,黑节点数相同(黑高一致)

由性质4、5可推得:红黑树高度 ≤ 2log(n+1),确保O(log n)时间复杂度。

2. Java中TreeMap的红黑树实现要点

JDK 1.8中,TreeMap的Entry类定义如下:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left;
    Entry<K,V> right;
    Entry<K,V> parent;
    boolean color = BLACK; // 默认黑色
}

插入/删除操作后通过fixAfterInsertion与fixAfterDeletion方法进行旋转与变色调整,核心策略包括:

3. 红黑树 vs AVL树:实际选型建议

在读写均衡的通用场景下,红黑树因更新性能更优而被广泛采用。例如:

而AVL树适用于读多写少场景,如:

⚡ 堆结构:优先队列的高效实现

1. 堆的定义与性质

堆是满足以下性质的完全二叉树:

堆通常用数组存储,索引i的父节点为(i-1)/2,左右子为2i+1与2i+2。

2. 堆操作实现(以最小堆为例)

class MinHeap {
    private List<Integer> heap = new ArrayList<>();
    // 插入:尾部添加 + 上浮
    public void insert(int val) {
        heap.add(val);
        siftUp(heap.size() - 1);
    }
    // 弹出最小值:首元素替换为尾元素 + 下沉
    public int poll() {
        if (heap.isEmpty()) throw new IllegalStateException();
        int min = heap.get(0);
        heap.set(0, heap.remove(heap.size() - 1));
        if (!heap.isEmpty()) siftDown(0);
        return min;
    }
    private void siftUp(int i) {
        while (i > 0 && heap.get(parent(i)) > heap.get(i)) {
            swap(parent(i), i);
            i = parent(i);
        }
    }
    private void siftDown(int i) {
        int minIndex = i;
        int left = leftChild(i);
        int right = rightChild(i);
        if (left < heap.size() && heap.get(left) < heap.get(minIndex))
            minIndex = left;
        if (right < heap.size() && heap.get(right) < heap.get(minIndex))
            minIndex = right;
        if (i != minIndex) {
            swap(i, minIndex);
            siftDown(minIndex);
        }
    }
    private int parent(int i) { return (i - 1) / 2; }
    private int leftChild(int i) { return 2 * i + 1; }
    private int rightChild(int i) { return 2 * i + 2; }
    private void swap(int i, int j) {
        Integer temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }
}

3. 堆在Java中的典型应用

⚡ 二叉树算法实战:高频场景与典型题目

1. 二叉树最大深度

递归解法:maxDepth(root) = 1 + max(maxDepth(left), maxDepth(right))

public int maxDepth(TreeNode root) {
    if (root == null) return 0;
    return 1 + Math.max(maxDepth(root.left), maxDepth(root.right));
}

2. 对称二叉树判断

递归比较左右子树是否镜像:左子树左孩子 = 右子树右孩子,左子树右孩子 = 右子树左孩子

public boolean isSymmetric(TreeNode root) {
    return root == null || isMirror(root.left, root.right);
}
private boolean isMirror(TreeNode t1, TreeNode t2) {
    if (t1 == null && t2 == null) return true;
    if (t1 == null || t2 == null) return false;
    return (t1.val == t2.val) && isMirror(t1.left, t2.right) && isMirror(t1.right, t2.left);
}

3. 二叉树路径总和

判断是否存在从根到叶子节点路径上节点值之和等于目标值targetSum

public boolean hasPathSum(TreeNode root, int targetSum) {
    if (root == null) return false;
    if (root.left == null && root.right == null) return root.val == targetSum;
    return hasPathSum(root.left, targetSum - root.val) ||
           hasPathSum(root.right, targetSum - root.val);
}

4. 重建二叉树(前序+中序)

前序遍历首元素为根节点,在中序遍历中定位根节点后,左侧为左子树,右侧为右子树,递归构建

public TreeNode buildTree(int[] preorder, int[] inorder) {
    Map<Integer, Integer> inMap = new HashMap<>();
    for (int i = 0; i < inorder.length; i++) inMap.put(inorder[i], i);
    return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, inMap);
}
private TreeNode build(int[] pre, int preL, int preR, int[] in, int inL, int inR, Map<Integer, Integer> inMap) {
    if (preL > preR || inL > inR) return null;
    TreeNode root = new TreeNode(pre[preL]);
    int rootIdx = inMap.get(pre[preL]);
    int leftSize = rootIdx - inL;
    root.left = build(pre, preL + 1, preL + leftSize, in, inL, rootIdx - 1, inMap);
    root.right = build(pre, preL + leftSize + 1, preR, in, rootIdx + 1, inR, inMap);
    return root;
}

⚡ 网友们还关心的问题