Обход дерева постпорядков — итеративный и рекурсивный
Для заданного двоичного дерева напишите итеративное и рекурсивное решение для обхода дерева с использованием обратного обхода в C++, Java и Python.
В отличие от связанных списков, одномерных массивов и других линейных структур данных, обход которых осуществляется в линейном порядке, по деревьям можно перемещаться несколькими способами. глубина первого порядка (предварительный заказ, в целях, а также постзаказ) или же ширина первого порядка (обход порядка уровней). Помимо этих основных обходов, возможны различные более сложные или гибридные схемы, такие как поиск с ограничением по глубине, например итеративный поиск в глубину с углублением. В этом посте подробно обсуждается обход дерева в обратном порядке.
Обход дерева включает в себя итерацию по всем узлам тем или иным образом. Поскольку дерево не является линейной структурой данных, может быть более одного возможного следующего узла от данного узла, поэтому некоторые узлы должны быть отложены, т. е. каким-то образом сохранены для последующего посещения. Обход может выполняться итеративно, когда отложенные узлы хранятся в stack, или это можно сделать с помощью рекурсия, где отложенные узлы неявно хранятся в стек вызовов.
Для обхода (непустого) бинарного дерева в обратном порядке мы должны сделать эти три вещи для каждого узла. n начиная с корня дерева:
(L) Рекурсивно обходим его левое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.
(R) Рекурсивно обходим его правое поддерево. Когда этот шаг будет завершен, мы вернемся к n опять таки.
(N) Процесс n сам.
В обычном обходе в обратном порядке посетите левое поддерево перед правым поддеревом. Если мы посещаем правое поддерево до посещения левого поддерева, это называется обходом в обратном порядке.
Рекурсивная реализация
Как мы видим, перед обработкой любого узла сначала обрабатывается левое поддерево, затем правое поддерево, а узел обрабатывается последним. Эти операции могут быть определены рекурсивно для каждого узла. Рекурсивная реализация называется Поиск в глубину (DFS), так как дерево поиска максимально углубляется для каждого дочернего элемента, прежде чем перейти к следующему родственному элементу.
Ниже приведена программа на C++, Java и Python, которая демонстрирует это:
Источник
Реализация бинарного дерева в Java
В этой статье мы рассмотрим реализацию двоичного дерева на Java.
Для этой статьиwe’ll use a sorted binary tree that will contain int values.
2. Бинарное дерево
Двоичное дерево — это рекурсивная структура данных, в которой каждый узел может иметь не более 2 дочерних элементов.
Распространенным типом двоичного дерева является двоичное дерево поиска, в котором каждый узел имеет значение, которое больше или равно значениям узла в левом поддереве и меньше или равно значениям узла в правом поддереве. дерево.
Вот краткое визуальное представление этого типа двоичного дерева:
Для реализации мы будем использовать вспомогательный классNode, который будет хранить значенияint и ссылаться на каждого потомка:
Затем давайте добавим начальный узел нашего дерева, обычно называемыйroot:
3. Общие операции
Теперь давайте посмотрим, какие операции мы можем выполнять с двоичным деревом.
3.1. Вставка элементов
Первая операция, которую мы рассмотрим, — это вставка новых узлов.
Во-первых,we have to find the place where we want to add a new node in order to keep the tree sorted. Мы будем следовать этим правилам, начиная с корневого узла:
- если значение нового узла ниже, чем значение текущего узла, мы переходим к левому дочернему элементу
- если значение нового узла больше, чем значение текущего узла, мы переходим к правому дочернему элементу
- когда текущий узел равен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; >Затем мы создадим общедоступный метод, который запускает рекурсию с узлаroot:
Теперь давайте посмотрим, как мы можем использовать этот метод для создания дерева из нашего примера:
private BinaryTree createBinaryTree()
3.2. Поиск элемента
Давайте теперь добавим метод, чтобы проверить, содержит ли дерево определенное значение.
Как и раньше, сначала мы создадим рекурсивный метод для обхода дерева:
private boolean containsNodeRecursive(Node current, int value) < if (current == null) < return false; >if (value == current.value) < return true; >return value
Здесь мы ищем значение, сравнивая его со значением в текущем узле, а затем продолжаем в левом или правом дочернем элементе в зависимости от этого.
Затем давайте создадим общедоступный метод, который начинается сroot:
public boolean containsNode(int value)
Теперь давайте создадим простой тест, чтобы убедиться, что дерево действительно содержит вставленные элементы:
@Test public void givenABinaryTree_WhenAddingElements_ThenTreeContainsThoseElements()
Все добавленные узлы должны содержаться в дереве.
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 основных случая:
- a node has no children – это простейший случай; нам просто нужно заменить этот узел наnull в его родительском узле
- a node has exactly one child – в родительском узле, мы заменяем этот узел его единственным дочерним узлом.
- a node has two children — это самый сложный случай, потому что он требует реорганизации дерева
Давайте посмотрим, как мы можем реализовать первый случай, когда узел является листовым:
if (current.left == null && current.right == null)
Теперь давайте продолжим случай, когда у узла есть один дочерний элемент:
if (current.right == null) < return current.left; >if (current.left == null)
Здесь мы возвращаем дочерний элементnon-null, чтобы его можно было назначить родительскому узлу.
Наконец, мы должны обработать случай, когда узел имеет двух детей.
Во-первых, нам нужно найти узел, который заменит удаленный узел. Мы будем использовать самый маленький узел из правого поддерева удаляемого узла:
private int findSmallestValue(Node root)
Затем мы присваиваем наименьшее значение удаляемому узлу, и после этого мы удалим его из правого поддерева:
int smallestValue = findSmallestValue(current.right); current.value = smallestValue; current.right = deleteRecursive(current.right, smallestValue); return current;Наконец, давайте создадим общедоступный метод, который начнет удаление изroot:
public void delete(int value)
Теперь давайте проверим, что удаление работает должным образом:
@Test public void givenABinaryTree_WhenDeletingElements_ThenTreeDoesNotContainThoseElements()
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. Поиск в ширину
Это еще один распространенный тип обходаvisits all the nodes of a level before going to the next level.
Этот вид обхода также называется уровнем порядка и охватывает все уровни дерева, начиная с корня и слева направо.
Для реализации мы будем использоватьQueue для упорядочивания узлов каждого уровня. Мы извлечем каждый узел из списка, распечатаем его значения, а затем добавим его дочерние элементы в очередь:
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); >> >В этом случае порядок узлов будет:
Источник