Java二叉树的实现 | Baeldung中文网

1. 简介

本教程将介绍如何在Java中实现二叉树。

为便于演示，我们将使用一个存储int值的有序二叉树（即二叉搜索树）。

2. 二叉树

二叉树是一种递归数据结构，每个节点最多有2个子节点。

常见类型是二叉搜索树，其特点是：每个节点的值都大于或等于左子树所有节点的值，且小于或等于右子树所有节点的值。

以下是这类二叉树的直观表示：

实现时，我们定义一个辅助Node类存储int值，并持有左右子节点的引用：

class Node {
    int value;
    Node left;
    Node right;

    Node(int value) {
        this.value = value;
        right = null;
        left = null;
    }
}

然后添加树的起始节点（通常称为根节点）：

public class BinaryTree {

    Node root;

    // ...
}

3. 常见操作

下面介绍二叉树最常用的操作。

3.1. 插入元素

第一个操作是插入新节点。关键点在于：必须找到合适位置插入，以保持树的有序性。从根节点开始，遵循以下规则：

新节点值小于当前节点 → 移动到左子节点
新节点值大于当前节点 → 移动到右子节点
当前节点为null → 到达叶子节点，在此位置插入

用递归方法实现插入逻辑：

private Node addRecursive(Node current, int value) {
    if (current == null) {
        return new Node(value);
    }

    if (value < current.value) {
        current.left = addRecursive(current.left, value);
    } else if (value > current.value) {
        current.right = addRecursive(current.right, value);
    } else {
        // 值已存在
        return current;
    }

    return current;
}

再创建一个公共方法从根节点启动递归：

public void add(int value) {
    root = addRecursive(root, value);
}

用以下代码构建示例中的树：

private BinaryTree createBinaryTree() {
    BinaryTree bt = new BinaryTree();

    bt.add(6);
    bt.add(4);
    bt.add(8);
    bt.add(3);
    bt.add(5);
    bt.add(7);
    bt.add(9);

    return bt;
}

3.2. 查找元素

添加一个方法检查树是否包含特定值。

先创建递归方法遍历树：

private boolean containsNodeRecursive(Node current, int value) {
    if (current == null) {
        return false;
    } 
    if (value == current.value) {
        return true;
    } 
    return value < current.value
      ? containsNodeRecursive(current.left, value)
      : containsNodeRecursive(current.right, value);
}

通过比较目标值与当前节点值，决定继续搜索左子树还是右子树。

再创建公共方法从根节点开始：

public boolean containsNode(int value) {
    return containsNodeRecursive(root, value);
}

用简单测试验证插入的元素是否在树中：

@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(6));
    assertTrue(bt.containsNode(4));
 
    assertFalse(bt.containsNode(1));
}

✅ 所有插入的节点都应存在于树中。

3.3. 删除元素

另一个常见操作是删除节点。

首先用类似方式定位待删除节点：

private Node deleteRecursive(Node current, int value) {
    if (current == null) {
        return null;
    }

    if (value == current.value) {
        // 找到待删除节点
        // 删除逻辑将在此处实现
    } 
    if (value < current.value) {
        current.left = deleteRecursive(current.left, value);
        return current;
    }
    current.right = deleteRecursive(current.right, value);
    return current;
}

找到待删除节点后，需处理三种情况：

无子节点 → 最简单，直接用null替换该节点
只有一个子节点 → 用其子节点替换该节点
有两个子节点 → 最复杂，需要重构树

先处理叶子节点（无子节点）的情况：

if (current.left == null && current.right == null) {
    return null;
}

再处理只有一个子节点的情况：

if (current.right == null) {
    return current.left;
}

if (current.left == null) {
    return current.right;
}

这里返回非空的子节点，使其被父节点引用。

最后处理有两个子节点的情况。首先找到替代节点（右子树中的最小值）：

private int findSmallestValue(Node root) {
    return root.left == null ? root.value : findSmallestValue(root.left);
}

将最小值赋给待删除节点，然后从右子树中删除该最小值：

int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;

创建公共方法从根节点启动删除：

public void delete(int value) {
    root = deleteRecursive(root, value);
}

验证删除是否生效：

@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
    BinaryTree bt = createBinaryTree();

    assertTrue(bt.containsNode(9));
    bt.delete(9);
    assertFalse(bt.containsNode(9));
}

❌ 删除后节点应不存在于树中。

4. 遍历树

本节探索不同遍历方式，重点介绍深度优先搜索和广度优先搜索。

使用前文的树结构，分析每种遍历顺序。

4.1. 深度优先搜索

深度优先搜索（DFS）会尽可能深地访问每个子节点，再访问兄弟节点。

DFS有三种实现方式：中序、前序和后序。

中序遍历顺序：左子树 → 根节点 → 右子树

public void traverseInOrder(Node node) {
    if (node != null) {
        traverseInOrder(node.left);
        System.out.print(" " + node.value);
        traverseInOrder(node.right);
    }
}

控制台输出结果：

3 4 5 6 7 8 9

前序遍历顺序：根节点 → 左子树 → 右子树

public void traversePreOrder(Node node) {
    if (node != null) {
        System.out.print(" " + node.value);
        traversePreOrder(node.left);
        traversePreOrder(node.right);
    }
}

控制台输出结果：

6 4 3 5 8 7 9

后序遍历顺序：左子树 → 右子树 → 根节点

public void traversePostOrder(Node node) {
    if (node != null) {
        traversePostOrder(node.left);
        traversePostOrder(node.right);
        System.out.print(" " + node.value);
    }
}

控制台输出结果：

3 5 4 7 9 8 6

4.2. 广度优先搜索

广度优先搜索（BFS）逐层访问节点，处理完当前层所有节点后才进入下一层。

这种遍历也称层序遍历，从根节点开始，从左到右访问每一层。

实现时使用Queue按序存储每层节点。从队列中取出节点，打印其值，再将其子节点加入队列：

public void traverseLevelOrder() {
    if (root == null) {
        return;
    }

    Queue<Node> nodes = new LinkedList<>();
    nodes.add(root);

    while (!nodes.isEmpty()) {

        Node node = nodes.remove();

        System.out.print(" " + node.value);

        if (node.left != null) {
            nodes.add(node.left);
        }

        if (node.right != null) {
            nodes.add(node.right);
        }
    }
}

节点访问顺序：

6 4 8 3 5 7 9

⚠️ 注意：BFS需借助队列实现，DFS则依赖递归或栈。

5. 总结

本文介绍了如何在Java中实现有序二叉树及其核心操作。关键点包括：

✅ 节点插入需保持有序性
✅ 删除操作需处理三种子节点情况
✅ 遍历方式决定节点访问顺序
❌ 递归实现需注意栈溢出风险（深度过大时）

完整示例代码可在GitHub仓库获取。实际开发中，直接使用TreeMap等集合类可能更高效，但理解底层实现有助于应对复杂场景。

Persistence

REST

Security

1. 简介

2. 二叉树

3. 常见操作

3.1. 插入元素

3.2. 查找元素

3.3. 删除元素

4. 遍历树

4.1. 深度优先搜索

4.2. 广度优先搜索

5. 总结