Бинарное дерево равные значения

Проверьте, идентичны ли два бинарных дерева или нет — итеративное и рекурсивное

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

Input:
1 1
/ \ / \
2 3 2 3
/ \ / \ / \ / \
4 5 6 7 4 5 6 7

Output: True
Explanation: Both binary trees have the same structure and contents.

Input:
1 1
/ \ / \
2 3 2 3
/ \ / \ / \ /
4 5 6 7 4 5 6

Output: False
Explanation: Both binary trees have different structures.

Input:
1 1
/ \ / \
2 3 2 3
/ \ / \ / \ / \
4 5 6 7 4 5 6 8

Output: False
Explanation: Both binary trees have the same structure but differ in nodes’ values.

Рекурсивное решение

Идея состоит в том, чтобы обойти оба дерева и сравнить значения в их корневом узле. Если значение совпадает, рекурсивно проверьте, идентично ли левое поддерево первого дерева левому поддереву второго дерева, а правое поддерево первого дерева идентично правому поддереву второго дерева. Если значение в их корневом узле отличается, деревья нарушают свойство данных. Если в какой-то момент рекурсии первое дерево пусто, а второе дерево непусто, или второе дерево пусто, а первое дерево непусто, деревья нарушают структурное свойство и не могут быть идентичными.

Алгоритм может быть реализован следующим образом на C++, Java и Python:

Источник

Реализация бинарного дерева в 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 .

Источник