Обход бинарных деревьев java

Поиск в ширину (BFS) и поиск в глубину (DFS) для двоичных деревьев в Java

Поиск в ширину и поиск в глубину — это два метода обхода графов и деревьев. В этом руководстве мы сосредоточимся в основном на обходах BFS и DFS в деревьях.

Что такое поиск в глубину (DFS)?

Алгоритм начинается с корневого узла, а затем исследует каждую ветвь перед возвратом. Он реализован с помощью стеков. Часто при написании кода мы используем стеки рекурсии для возврата. Используя рекурсию, мы можем воспользоваться тем фактом, что левое и правое поддеревья также являются деревьями и имеют одни и те же свойства.

Для двоичных деревьев существует три типа обхода DFS.

Что такое поиск в ширину (BFS)?

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

Для бинарных деревьев у нас есть обход порядка уровней, который следует за BFS.

Реализация BFS и DFS на Java

Пусть рассматриваемое дерево:

Структура класса TreeNode выглядит следующим образом:

1. Обход предварительного заказа

При предварительном обходе бинарного дерева мы сначала обходим корень, затем левое поддерево и, наконец, правое поддерево. Мы делаем это рекурсивно, чтобы воспользоваться тем фактом, что левое и правое поддеревья также являются деревьями.

Алгоритм обхода предварительного заказа следующий:

1. Обход корня.
2. Вызов preorder() для левого поддерева.
3. Вызов preorder() для правого поддерева.

Обход предварительного заказа дерева выше:

Java-код выглядит следующим образом:

 static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.item + "->"); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); > 

2. Обход по порядку

Обход двоичного дерева по порядку сначала проходит через левое поддерево, затем корень и, наконец, правое поддерево.

Алгоритм обхода по порядку следующий:

1. Вызов inorder() для левого поддерева.
2. Обход корня.
3. Вызовите inorder() для правого поддерева.

Порядок обхода дерева выше:

Java-код выглядит следующим образом:

 static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.item + "->"); // Traverse right inorder(TreeNode.right); > 

3. Обход после заказа

Обход двоичного дерева в обратном порядке сначала проходит по левому поддереву, затем по правому поддереву и, наконец, по корню.

Алгоритм обхода после заказа следующий:

1. Вызов postorder() для левого поддерева.
2. Вызов postorder() для правого поддерева.
3. Обход корня.

Пост-порядковый обход дерева выше:

Java-код выглядит следующим образом:

 static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.item + "->"); > 

4. Обход по уровням

Обход по порядку уровней использует очередь для отслеживания посещаемых узлов. После посещения узла его потомки помещаются в очередь. Чтобы получить новый узел для обхода, мы удаляем элементы из очереди.

1. Инициализировать пустую очередь
2. Начните с установки temp от имени пользователя root
3. Запускать цикл до тех пор, пока очередь не станет пустой
   1. Печатать данные из временного файла.
   2. Поставить дочерние элементы temp в порядке слева и справа.
   3. Удалить узел из очереди и присвоить его значение переменной temp.

   Обход по порядку уровней дерева выше:

   Java-код выглядит следующим образом:

    static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode temp = queue.poll(); System.out.print(temp.data + " "); /*add left child to the queue */ if (temp.left != null) < queue.add(temp.left); >/*add right right child to the queue */ if (temp.right != null) < queue.add(temp.right); >> > 

   Полная реализация кода BFS и DFS на Java

   Полный код Java приведен ниже:

   package com.JournalDev; import java.util.LinkedList; import java.util.Queue; public class Main < static class TreeNode < int data; TreeNode left, right; public TreeNode(int key) < data = key; left = right = null; >> static void preorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse root System.out.print(TreeNode.data + " "); // Traverse left preorder(TreeNode.left); // Traverse right preorder(TreeNode.right); >static void inorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left inorder(TreeNode.left); // Traverse root System.out.print(TreeNode.data + " "); // Traverse right inorder(TreeNode.right); >static void postorder(TreeNode TreeNode) < if (TreeNode == null) return; // Traverse left postorder(TreeNode.left); // Traverse right postorder(TreeNode.right); // Traverse root System.out.print(TreeNode.data + " "); >static void printLevelOrder(TreeNode root) < Queuequeue = new LinkedList(); queue.add(root); while (!queue.isEmpty()) < TreeNode tempNode = queue.poll(); System.out.print(tempNode.data + " "); /*add left child to the queue */ if (tempNode.left != null) < queue.add(tempNode.left); >/*add right right child to the queue */ if (tempNode.right != null) < queue.add(tempNode.right); >> > public static void main(String args[]) < TreeNode root = new TreeNode(0); root.left = new TreeNode(1); root.right = new TreeNode(2); root.left.left = new TreeNode(3); root.left.right = new TreeNode(4); System.out.println("Inorder traversal"); inorder(root); System.out.println("\nPreorder traversal "); preorder(root); System.out.println("\nPostorder traversal"); postorder(root); System.out.println("\nLevelorder traversal"); printLevelOrder(root); >> 

   Output : Inorder traversal 3 1 4 0 2 Preorder traversal 0 1 3 4 2 Postorder traversal 3 4 1 2 0 Levelorder traversal 0 1 2 3 4 

   

   Заключение

   Это руководство было посвящено обходам BFS и DFS в двоичных деревьях. Чтобы получить реализацию DFS на C++, обратитесь к этому руководству.

   Источник

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

   В этом случае порядок узлов будет:

   Источник