Пребарување во широчина (BFS) и пребарување на прво длабочина (DFS) за бинарни дрвја во Јава

Прво пребарување во ширина и Прво пребарување во длабочина се две техники за преминување на графикони и дрвја. Во овој туторијал, ќе се фокусираме главно на BFS и DFS премини на дрвја.

Што е Прво пребарување во длабочина (DFS)?

Алгоритмот започнува во коренскиот јазол и потоа ја истражува секоја гранка пред да се врати назад. Се спроведува со користење на стекови. Често додека го пишуваме кодот, користиме рекурзиски стекови за да се вратиме назад. Со користење на рекурзија, можеме да го искористиме фактот дека левото и десното поддрво се исто така дрвја и споделуваат исти својства.

За бинарни дрвја, постојат три типа на DFS премини.

  1. Во ред
  2. Нарачајте однапред
  3. По нарачката

Што е Breadth-First Search (BFS)?

Овој алгоритам исто така започнува во коренскиот јазол и потоа ги посетува сите јазли ниво по ниво. Тоа значи дека по коренот, ги поминува сите директни деца на коренот. Откако ќе се поминат сите директни деца од коренот, тој се движи кон нивните деца и така натаму. За имплементирање на BFS користиме редица.

За бинарни дрвја, имаме Поминување на редослед на ниво што го следи BFS.

Имплементација на BFS и DFS во Јава

Нека се разгледува дрвото:

Структурата на класата TreeNode е како што следува:

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

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

1. Преминување пред нарачка

При претходна нарачка на траверсирање на бинарно дрво, прво го поминуваме коренот, потоа левото поддрво и на крајот десното подстебло. Ова го правиме рекурзивно за да имаме корист од фактот дека левата и десната поддрва се исто така дрвја.

Алгоритмот за претходна нарачка е следен:

  1. Преминете го коренот.
  2. Повикај преднарачка() на левото поддрво.
  3. Повикај преднарачка() на десното подстебло.

Преминувањето на претходно нарачка на дрвото погоре е:

0 1 3 4 2

Јава кодот е како што следува:

 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

Јава кодот е како што следува:

 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

Јава кодот е како што следува:

 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. Започнете со поставување на температурата како root
  3. Изврши јамка додека редицата не е празна
    1. Печатете податоци од темп.
    2. Средете ги децата на temp во редоследот лево па десно.
    3. Отстранете јазол од редот и доделете ја неговата вредност на temp.

    Преминувањето на редоследот на ниво на дрвото погоре е:

    0 1 2 3 4

    Јава кодот е како што следува:

     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 код е даден подолу:

    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++ погледнете го ова упатство.