1. Introduction
1.介绍
In this tutorial, we’ll cover the implementation of a binary tree in Java.
在本教程中，我们将介绍Java中二叉树的实现。
For the sake of this tutorial, we’ll use a sorted binary tree that contains int values.
在本教程中，我们将使用一个包含int值的排序二叉树。
2. Binary Tree
2.二进制树
A binary tree is a recursive data structure where each node can have 2 children at most.
二叉树是一种递归数据结构，每个节点最多可以有2个孩子。
A common type of binary tree is a binary search tree, in which every node has a value that is greater than or equal to the node values in the left sub-tree, and less than or equal to the node values in the right sub-tree.
常见的二叉树类型是二叉搜索树，其中每个节点的值都大于或等于左边子树的节点值，小于或等于右边子树的节点值。
Here’s a visual representation of this type of binary tree:
下面是这种类型的二叉树的可视化表示。
For the implementation, we’ll use an auxiliary Node class that will store int values, and keep a reference to each child:
对于实现，我们将使用一个辅助的Node类，它将存储int值，并保持对每个孩子的引用。
class Node {
int value;
Node left;
Node right;
Node(int value) {
this.value = value;
right = null;
left = null;
}
}Then we’ll add the starting node of our tree, usually called the root:
然后，我们将添加我们的树的起始节点，通常称为根：。
public class BinaryTree {
Node root;
// ...
}3. Common Operations
3.常见的操作
Now let’s see the most common operations we can perform on a binary tree.
现在让我们看看我们可以在二叉树上进行的最常见的操作。
3.1. Inserting Elements
3.1.插入元素
The first operation we’re going to cover is the insertion of new nodes.
我们要介绍的第一个操作是插入新节点。
First, we have to find the place where we want to add a new node in order to keep the tree sorted. We’ll follow these rules starting from the root node:
首先，我们必须找到我们要添加新节点的地方，以保持树的排序。我们将遵循这些规则，从根节点开始。
- if the new node’s value is lower than the current node’s, we go to the left child
- if the new node’s value is greater than the current node’s, we go to the right child
- when the current node is null, we’ve reached a leaf node and we can insert the new node in that position
Then we’ll create a recursive method to do the insertion:
然后我们将创建一个递归方法来进行插入。
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 {
// value already exists
return current;
}
return current;
}Next we’ll create the public method that starts the recursion from the root node:
接下来我们将创建一个公共方法，从根节点开始递归。
public void add(int value) {
root = addRecursive(root, value);
}Let’s see how we can use this method to create the tree from our example:
让我们看看我们如何使用这个方法来创建我们例子中的树。
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. Finding an Element
3.2.寻找一个元素
Now let’s add a method to check if the tree contains a specific value.
现在让我们添加一个方法来检查树是否包含一个特定的值。
As before, we’ll first create a recursive method that traverses the tree:
和以前一样，我们首先要创建一个遍历树的递归方法。
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);
}Here we’re searching for the value by comparing it to the value in the current node; we’ll then continue in the left or right child depending on the outcome.
在这里，我们通过与当前节点中的值进行比较来搜索该值；然后根据结果，我们将继续在左边或右边的子节点中搜索。
Next we’ll create the public method that starts from the root:
接下来我们将创建从根开始的公共方法。
public boolean containsNode(int value) {
return containsNodeRecursive(root, value);
}Then we’ll create a simple test to verify that the tree really contains the inserted elements:
然后我们将创建一个简单的测试来验证树是否真的包含插入的元素。
@Test
public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements() {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(6));
assertTrue(bt.containsNode(4));
assertFalse(bt.containsNode(1));
}All the nodes added should be contained in the tree.
所有添加的节点都应该包含在树中。
3.3. Deleting an Element
3.3.删除一个元素
Another common operation is the deletion of a node from the tree.
另一个常见的操作是将一个节点从树上删除。
First, we have to find the node to delete in a similar way as before:
首先，我们必须以类似于之前的方式找到要删除的节点。
private Node deleteRecursive(Node current, int value) {
if (current == null) {
return null;
}
if (value == current.value) {
// Node to delete found
// ... code to delete the node will go here
}
if (value < current.value) {
current.left = deleteRecursive(current.left, value);
return current;
}
current.right = deleteRecursive(current.right, value);
return current;
}Once we find the node to delete, there are 3 main different cases:
一旦我们找到要删除的节点，主要有3种不同的情况。
- a node has no children – this is the simplest case; we just need to replace this node with null in its parent node
- a node has exactly one child – in the parent node, we replace this node with its only child.
- a node has two children – this is the most complex case because it requires a tree reorganization
Let’s see how we would implement the first case when the node is a leaf node:
让我们看看当节点是叶子节点时，我们将如何实现第一种情况。
if (current.left == null && current.right == null) {
return null;
}Now let’s continue with the case when the node has one child:
现在让我们继续讨论节点有一个孩子时的情况。
if (current.right == null) {
return current.left;
}
if (current.left == null) {
return current.right;
}Here we’re returning the non-null child so it can be assigned to the parent node.
这里我们要返回非空的子节点，这样它就可以被分配到父节点。
Finally, we have to handle the case where the node has two children.
最后，我们必须处理节点有两个孩子的情况。
First, we need to find the node that will replace the deleted node. We’ll use the smallest node of the soon to be deleted node’s right sub-tree:
首先，我们需要找到将取代被删除节点的节点。我们将使用即将被删除的节点的右侧子树中最小的节点。
private int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}Then we assign the smallest value to the node to delete, and after that, we’ll delete it from the right sub-tree:
然后，我们给要删除的节点分配最小的值，之后，我们将把它从右边的子树上删除。
int smallestValue = findSmallestValue(current.right);
current.value = smallestValue;
current.right = deleteRecursive(current.right, smallestValue);
return current;Finally, we’ll create the public method that starts the deletion from the root:
最后，我们将创建一个公共方法，从根开始删除。
public void delete(int value) {
root = deleteRecursive(root, value);
}Now let’s check that the deletion worked as expected:
现在让我们检查一下，删除工作是否符合预期。
@Test
public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements() {
BinaryTree bt = createBinaryTree();
assertTrue(bt.containsNode(9));
bt.delete(9);
assertFalse(bt.containsNode(9));
}4. Traversing the Tree
4.穿越树
In this section, we’ll explore different ways of traversing a tree, covering in detail the depth-first and breadth-first searches.
在这一节中，我们将探索遍历树的不同方式，详细介绍深度优先和广度优先的搜索。
We’ll use the same tree that we used before, and we’ll examine the traversal order for each case.
我们将使用与之前相同的树，我们将检查每种情况的遍历顺序。
4.1. Depth-First Search
4.1.深度优先搜索
Depth-first search is a type of traversal that goes deep as much as possible in every child before exploring the next sibling.
深度优先搜索是一种遍历类型，在探索下一个兄弟姐妹之前，尽可能地深入到每一个孩子身上。
There are several ways to perform a depth-first search: in-order, pre-order and post-order.
有几种方法可以进行深度优先搜索：顺序内搜索、顺序前搜索和顺序后搜索。
The in-order traversal consists of first visiting the left sub-tree, then the root node, and finally the right sub-tree:
内序遍历包括首先访问左侧子树，然后是根节点，最后是右侧子树：。
public void traverseInOrder(Node node) {
if (node != null) {
traverseInOrder(node.left);
System.out.print(" " + node.value);
traverseInOrder(node.right);
}
}If we call this method, the console output will show the in-order traversal:
如果我们调用这个方法，控制台的输出将显示出顺序排列的遍历。
3 4 5 6 7 8 9Pre-order traversal visits first the root node, then the left sub-tree, and finally the right sub-tree:
前序遍历首先访问根节点，然后是左侧子树，最后是右侧子树：。
public void traversePreOrder(Node node) {
if (node != null) {
System.out.print(" " + node.value);
traversePreOrder(node.left);
traversePreOrder(node.right);
}
}Let’s check the pre-order traversal in the console output:
让我们检查一下控制台输出中的预排序遍历。
6 4 3 5 8 7 9Post-order traversal visits the left sub-tree, the right subt-ree, and the root node at the end:
后序遍历访问左边的子树，右边的子树，以及最后的根节点：。
public void traversePostOrder(Node node) {
if (node != null) {
traversePostOrder(node.left);
traversePostOrder(node.right);
System.out.print(" " + node.value);
}
}Here are the nodes in post-order:
下面是按后序排列的节点。
3 5 4 7 9 8 64.2. Breadth-First Search
4.2.广度优先搜索
This is another common type of traversal that visits all the nodes of a level before going to the next level.
这是另一种常见的遍历类型，在进入下一层次之前，先访问一个层次的所有节点。
This kind of traversal is also called level-order, and visits all the levels of the tree starting from the root, and from left to right.
这种遍历方式也被称为层序遍历，从根部开始，从左到右遍历树的所有层。
For the implementation, we’ll use a Queue to hold the nodes from each level in order. We’ll extract each node from the list, print its values, then add its children to the queue:
在实现上，我们将使用一个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);
}
}
}In this case, the order of the nodes will be:
在这种情况下，节点的顺序将是。
6 4 8 3 5 7 95. Conclusion
5.结论
In this article, we learned how to implement a sorted binary tree in Java, and its most common operations.
在这篇文章中，我们学习了如何在Java中实现一个排序的二叉树，以及它最常见的操作。
The full source code for the examples is available over on GitHub.
示例的完整源代码可在GitHub上获得。