Поиск по сайту:

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

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

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

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

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

  1. По порядку
  2. Предварительный заказ
  3. Постзаказ

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

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

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

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

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

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

 static class TreeNode {
        int data;
        TreeNode left, right;

        public TreeNode(int key) {
            data = key;
            left = right = null;
        }
    }

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

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

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

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

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

0 1 3 4 2

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() для правого поддерева.

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

3 1 4 0 2

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. Обход корня.

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

3 4 1 2 0

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.

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

    0 1 2 3 4

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

     static void printLevelOrder(TreeNode root) {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       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) {
       Queue<TreeNode> queue = new LinkedList<TreeNode>();
       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++, обратитесь к этому руководству.