简介
在本实验中,我们将学习如何在 Java 中实现一个二叉搜索树(Binary Search Tree)。二叉搜索树是一种二叉树数据结构,其中每个节点的值大于或等于其左子树中的所有值,且小于或等于其右子树中的所有值。
在本实验中,我们将学习如何在 Java 中实现一个二叉搜索树(Binary Search Tree)。二叉搜索树是一种二叉树数据结构,其中每个节点的值大于或等于其左子树中的所有值,且小于或等于其右子树中的所有值。
BSTNode
类首先,让我们创建一个 Java 类来表示二叉搜索树的节点,并将其命名为 BSTNode
。二叉搜索树中的一个节点应该包含一个值以及两个子节点——一个左子节点和一个右子节点。
class BSTNode {
int value;
BSTNode leftChild;
BSTNode rightChild;
BSTNode(int val) {
this.value = val;
this.leftChild = null;
this.rightChild = null;
}
}
要向二叉搜索树中插入元素,我们遵循以下算法:
public static BSTNode insert(int value, BSTNode current) {
if (current == null) {
BSTNode newNode = new BSTNode(value);
return newNode;
} else {
if (value < current.value)
current.leftChild = insert(value, current.leftChild);
else
current.rightChild = insert(value, current.rightChild);
}
return current;
}
为了测试这个方法,创建二叉搜索树并插入一些元素:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// 打印树以验证插入
System.out.println("Traversal after insertion: ");
inorderTraversal(root);
}
// 中序遍历树的函数
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}
输出:
Traversal after insertion:
5 7 9 12 20 21
要在二叉搜索树中搜索元素,我们遵循以下算法:
public static boolean search(int key, BSTNode current) {
if (current == null)
return false;
if (current.value == key)
return true;
else {
if (key < current.value)
return search(key, current.leftChild);
else
return search(key, current.rightChild);
}
}
为了测试这个方法,搜索一些元素:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// 搜索元素
System.out.println(search(7, root));
System.out.println(search(9, root));
System.out.println(search(17, root));
}
输出:
true
true
false
从二叉搜索树中删除元素比之前的步骤稍微复杂一些,因为我们需要根据节点的类型处理不同的情况:
public static BSTNode delete(int value, BSTNode current) {
if (current == null)
return current;
if (value < current.value)
current.leftChild = delete(value, current.leftChild);
else if (value > current.value)
current.rightChild = delete(value, current.rightChild);
else if (value == current.value) {
if (current.leftChild != null && current.rightChild != null) {
int min = current.rightChild.value;
BSTNode temp = current.rightChild;
while (temp.leftChild != null) {
min = temp.leftChild.value;
temp = temp.leftChild;
}
current.value = min;
current.rightChild = delete(min, current.rightChild);
} else if (current.leftChild == null)
return current.rightChild;
else if (current.rightChild == null)
return current.leftChild;
}
return current;
}
为了测试这个方法,删除一些节点并打印树:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
// 删除一些节点
root = delete(12, root);
root = delete(20, root);
root = delete(9, root);
// 打印树以验证删除
System.out.println("Traversal after deletion: ");
inorderTraversal(root);
}
输出:
Traversal after deletion:
5 7 21
我们可以通过不同的方式遍历二叉搜索树:
public static void inorderTraversal(BSTNode current) {
if (current == null)
return;
inorderTraversal(current.leftChild);
System.out.print(current.value + " ");
inorderTraversal(current.rightChild);
}
public static void preorderTraversal(BSTNode current) {
if (current == null)
return;
System.out.print(current.value + " ");
preorderTraversal(current.leftChild);
preorderTraversal(current.rightChild);
}
public static void postorderTraversal(BSTNode current) {
if (current == null)
return;
postorderTraversal(current.leftChild);
postorderTraversal(current.rightChild);
System.out.print(current.value + " ");
}
public static void levelOrderTraversal(BSTNode root) {
Queue<BSTNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
BSTNode temp = queue.poll();
System.out.print(temp.value + " ");
if (temp.leftChild != null)
queue.add(temp.leftChild);
if (temp.rightChild != null)
queue.add(temp.rightChild);
}
}
为了测试这些方法,使用每种遍历技术打印树:
public static void main(String[] args) {
BSTNode root = new BSTNode(12);
root = insert(7, root);
root = insert(20, root);
root = insert(5, root);
root = insert(9, root);
root = insert(21, root);
System.out.print("Inorder Traversal: ");
inorderTraversal(root);
System.out.print("\nPreorder Traversal: ");
preorderTraversal(root);
System.out.print("\nPostorder Traversal: ");
postorderTraversal(root);
System.out.print("\nLevel-order Traversal: ");
levelOrderTraversal(root);
}
输出:
Inorder Traversal: 5 7 9 12 20 21
Preorder Traversal: 12 7 5 9 20 21
Postorder Traversal: 5 9 7 21 20 12
Level-order Traversal: 12 7 20 5 9 21
在本实验中,我们学习了如何在 Java 中创建二叉搜索树、插入元素、搜索元素、删除元素以及遍历二叉搜索树。
我们首先创建了 BSTNode
类,它表示二叉搜索树中的一个节点。然后,我们使用二叉搜索树特有的算法实现了插入、搜索和删除功能。最后,我们学习了如何使用不同的遍历技术(如中序、前序、后序和层序遍历)来遍历二叉搜索树。
通过这些概念,你应该能够在自己的 Java 程序中实现二叉搜索树。