Введение
В этом практическом занятии мы научимся реализовывать двоичное дерево поиска на Java. Двоичное дерево поиска - это двоичное дерево, в котором значение каждого узла больше или равно значениям в его левом поддереве и меньше или равно значениям в его правом поддереве.
Создание класса BSTNode
Во - первых, создадим Java - класс, представляющий узел двоичного дерева поиска, и назовем его BSTNode. Узел в двоичном дереве поиска должен иметь значение и два дочерних узла - один слева и один справа.
class BSTNode {
int value;
BSTNode leftChild;
BSTNode rightChild;
BSTNode(int val) {
this.value = val;
this.leftChild = null;
this.rightChild = null;
}
}
Вставка элементов в двоичное дерево поиска
Для вставки элементов в двоичное дерево поиска мы следуем следующему алгоритму:
- Если новое значение меньше значения текущего узла, то рекурсивно вызываем метод для левого дочернего узла.
- Если новое значение больше значения текущего узла, то рекурсивно вызываем метод для правого дочернего узла.
- Если текущий узел равен 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);
// Print out the tree to verify the insertion
System.out.println("Traversal after insertion: ");
inorderTraversal(root);
}
// Function to traverse the tree inorder
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
Поиск элемента в двоичном дереве поиска
Для поиска элемента в двоичном дереве поиска мы следуем следующему алгоритму:
- Если значение текущего узла совпадает с искомым значением, то возвращаем true.
- Если значение текущего узла больше искомого значения, то рекурсивно вызываем метод для левого дочернего узла.
- Если значение текущего узла меньше искомого значения, то рекурсивно вызываем метод для правого дочернего узла.
- Если текущий узел равен null, то возвращаем false.
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);
// Search for elements
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);
// Delete some nodes
root = delete(12, root);
root = delete(20, root);
root = delete(9, root);
// Print the tree to verify the deletion
System.out.println("Traversal after deletion: ");
inorderTraversal(root);
}
Результат:
Traversal after deletion:
5 7 21
Пробег по двоичному дереву поиска
Мы можем обходить двоичное дерево поиска разными способами:
- Симметричный (Inorder) обход (Left-Root-Right)
- Префиксный (Preorder) обход (Root-Left-Right)
- Постфиксный (Postorder) обход (Left-Right-Root)
- Обход по уровням (Level-order Traversal, BFS)
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, представляющий узел в двоичном дереве поиска. Затем мы реализовали функциональность вставки, поиска и удаления с использованием алгоритмов, специфичных для двоичных деревьев поиска. Наконец, мы узнали, как обходить двоичное дерево поиска с использованием различных техник обхода, таких как симметричный (inorder), префиксный (preorder), постфиксный (postorder) и обход по уровням (level-order traversal).
С этими концепциями вы должны быть в состоянии реализовать двоичные деревья поиска в своих собственных Java-программах.
