1. 简介

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

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

2. 二叉树

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

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

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

Tree-1

实现时,我们定义一个辅助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等集合类可能更高效,但理解底层实现有助于应对复杂场景。


原始标题:Implementing a Binary Tree in Java

« 上一篇: 在Gradle中创建Fat Jar
» 下一篇: Java 内置注解详解