Перейти к основному содержимому

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

· 7 мин. чтения

Задача: Сумма двух

Дано массив целых чисел и целая сумма. Нужно найти индексы двух чисел, сумма которых равна заданной ...

ANDROMEDA

1. Введение

В этом руководстве мы рассмотрим реализацию двоичного дерева в Java.

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

2. Бинарное дерево

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

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

Вот визуальное представление этого типа бинарного дерева:

./a22f4903b2c640693e64d047866f4985.jpg

Для реализации мы будем использовать вспомогательный класс 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.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<Node> 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 .