Реализация двоичного дерева в Java

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. Вставка элементов

Первая операция, которую мы рассмотрим, - это вставка новых узлов.

Во-первых, мы должны найти место, куда мы хотим добавить новый узел, чтобы дерево оставалось отсортированным . Мы будем следовать этим правилам, начиная с корневого узла:

  • если значение нового узла ниже, чем значение текущего узла, мы переходим к левому дочернему элементу
  • если значение нового узла больше, чем значение текущего узла, мы переходим к правому дочернему элементу
  • когда текущий узел равен нулю, мы достигли конечного узла и можем вставить новый узел в эту позицию

Сначала мы создадим рекурсивный метод для вставки:

private Node addRecursive(Node current, int value) { if (current == null) { return new Node(value); } if (value  current.value) { current.right = addRecursive(current.right, value); } else { // value already exists 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) { // 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; }

Когда мы находим узел, который нужно удалить, есть 3 основных разных случая:

  • узел не имеет потомков - это простейший случай; нам просто нужно заменить этот узел на нуль в его родительском узле
  • у узла есть ровно один дочерний элемент - в родительском узле мы заменяем этот узел его единственным дочерним элементом.
  • узел имеет двух потомков - это самый сложный случай, потому что он требует реорганизации дерева

Давайте посмотрим, как мы можем реализовать первый случай, когда узел является листовым узлом:

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. Поиск в глубину

Поиск в глубину - это тип обхода, который максимально углубляется в каждого ребенка, прежде чем исследовать следующего брата или сестру.

Есть несколько способов выполнить поиск в глубину: по порядку, по предварительному заказу и по запросу.

Обход по порядку состоит из первого посещения левого поддерева, затем корневого узла и, наконец, правого поддерева:

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. Поиск в ширину

Это еще один распространенный тип обхода, который посещает все узлы уровня перед переходом на следующий уровень .

Этот вид обхода также называется порядком уровней и проходит по всем уровням дерева, начиная с корня и слева направо.

Для реализации мы будем использовать очередь для упорядочивания узлов с каждого уровня. Мы извлечем каждый узел из списка, распечатаем его значения, а затем добавим его дочерние элементы в очередь:

public void traverseLevelOrder() { if (root == null) { return; } Queue 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

5. Заключение

В этой статье мы увидели, как реализовать сортированное двоичное дерево в Java и его наиболее распространенные операции.

Полный исходный код примеров доступен на GitHub.