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