Автор оригинала: Marcos Lopez Gonzalez.
1. введение
В этой статье мы рассмотрим реализацию двоичного дерева в Java.
Для этой статьи мы будем использовать отсортированное двоичное дерево , которое будет содержать int значения .
Дальнейшее чтение:
Как распечатать двоичную древовидную диаграмму
Реверсирование двоичного дерева в Java
Глубина первого поиска на Java
2. Двоичное дерево
Двоичное дерево-это рекурсивная структура данных, в которой каждый узел может иметь не более 2 дочерних элементов.
Распространенным типом двоичного дерева является двоичное дерево поиска , в котором каждый узел имеет значение, которое больше или равно значениям узлов в левом поддереве и меньше или равно значениям узлов в правом поддереве.
Вот краткое визуальное представление этого типа двоичного дерева:
Для реализации мы будем использовать вспомогательный класс Node , который будет хранить значения int и сохранять ссылку на каждый дочерний элемент:
class Node { int value; Node left; Node right; Node(int value) { this.value = value; right = null; left = null; } }
Затем давайте добавим начальный узел нашего дерева, обычно называемый root:
public class BinaryTree { Node root; // ... }
3. Общие операции
Теперь давайте рассмотрим наиболее распространенные операции, которые мы можем выполнять с двоичным деревом.
3.1. Вставка Элементов
Первая операция, которую мы рассмотрим, – это вставка новых узлов.
Во-первых, мы должны найти место, где мы хотим добавить новый узел, чтобы сохранить дерево отсортированным . Мы будем следовать этим правилам, начиная с корневого узла:
- если значение нового узла ниже, чем значение текущего узла, мы переходим к левому дочернему узлу
- если значение нового узла больше, чем значение текущего узла, мы переходим к правому дочернему узлу
- когда текущий узел равен null, мы достигли конечного узла, и мы можем вставить новый узел в эту позицию
Во-первых, мы создадим рекурсивный метод для вставки:
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); }
Здесь мы ищем значение, сравнивая его со значением в текущем узле, а затем продолжаем в левом или правом дочернем узле в зависимости от этого.
Далее, давайте создадим открытый метод, который начинается с root :
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.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;
Наконец, давайте создадим общедоступный метод, который запускает удаление из root :
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; } Queuenodes = 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 .