Реализация бинарного дерева в Java
В этом руководстве мы рассмотрим реализацию двоичного дерева в Java.
Для этого руководства мы будем использовать отсортированное двоичное дерево , содержащее значения int .
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.left = addRecursive(current.left, value); > else 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 основных разных случая:
- узел не имеет потомков — это самый простой случай; нам просто нужно заменить этот узел на 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); > > Если мы вызовем этот метод, вывод консоли покажет обход по порядку:
Обход в предварительном порядке сначала посещает корневой узел, затем левое поддерево и, наконец, правое поддерево:
public void traversePreOrder(Node node) if (node != null) System.out.print(" " + node.value); traversePreOrder(node.left); traversePreOrder(node.right); > > Давайте проверим обход предварительного заказа в выводе консоли:
Обход в обратном порядке посещает левое поддерево, правое поддерево и корневой узел в конце:
public void traversePostOrder(Node node) if (node != null) traversePostOrder(node.left); traversePostOrder(node.right); System.out.print(" " + node.value); > > 4.2. Поиск в ширину
Это еще один распространенный тип обхода, который посещает все узлы уровня перед переходом на следующий уровень .
Этот вид обхода также называется порядком уровней и посещает все уровни дерева, начиная с корня и слева направо.
Для реализации мы будем использовать очередь для хранения узлов с каждого уровня по порядку. Мы извлечем каждый узел из списка, распечатаем его значения, а затем добавим его дочерние элементы в очередь:
public void traverseLevelOrder() if (root == null) return; > QueueNode> 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); > > > В этом случае порядок узлов будет следующим:
5. Вывод
В этой статье мы узнали, как реализовать отсортированное двоичное дерево в Java и его наиболее распространенные операции.
Полный исходный код примеров доступен на GitHub .