Java의 이진 트리에 대한 너비 우선 검색(BFS) 및 깊이 우선 검색(DFS)

Breadth-First Search와 Depth-First Search는 그래프와 트리를 순회하는 두 가지 기술입니다. 이 튜토리얼에서는 주로 트리의 BFS 및 DFS 순회에 중점을 둘 것입니다.

깊이 우선 검색(DFS)이란 무엇입니까?

알고리즘은 루트 노드에서 시작한 다음 역추적하기 전에 각 분기를 탐색합니다. 스택을 사용하여 구현됩니다. 종종 코드를 작성하는 동안 역추적을 위해 재귀 스택을 사용합니다. 재귀를 사용하면 왼쪽 및 오른쪽 하위 트리도 트리이고 동일한 속성을 공유한다는 사실을 활용할 수 있습니다.

이진 트리의 경우 세 가지 유형의 DFS 순회가 있습니다.

순서대로
선주문
주문 후

너비 우선 검색(BFS)이란 무엇입니까?

이 알고리즘도 루트 노드에서 시작하여 레벨별로 모든 노드를 방문합니다. 즉, 루트 이후 루트의 모든 직계 자식을 순회합니다. 루트의 모든 직계 자식이 순회된 후 자식으로 이동하는 식입니다. BFS를 구현하기 위해 대기열을 사용합니다.

이진 트리의 경우 BFS를 따르는 Level Order Traversal이 있습니다.

Java에서 BFS 및 DFS 구현

고려 중인 트리를 다음과 같이 하십시오.

TreeNode 클래스의 구조는 다음과 같습니다.

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

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

1. 선주문 순회

이진 트리의 사전 순회에서는 먼저 루트를 순회한 다음 왼쪽 하위 트리, 마지막으로 오른쪽 하위 트리를 순회합니다. 왼쪽 및 오른쪽 하위 트리도 트리라는 사실로부터 이점을 얻기 위해 이 작업을 재귀적으로 수행합니다.

선주문 순회 알고리즘은 다음과 같습니다.

루트를 통과합니다.
왼쪽 하위 트리에서 preorder()를 호출합니다.
오른쪽 하위 트리에서 preorder()를 호출합니다.

위 트리의 선주문 순회는 다음과 같습니다.

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. 순서 순회

이진 트리의 순회는 먼저 왼쪽 하위 트리를 순회한 다음 루트를 순회하고 마지막으로 오른쪽 하위 트리를 순회합니다.

순서 순회 알고리즘은 다음과 같습니다.

왼쪽 하위 트리에서 inorder()를 호출합니다.
루트를 통과합니다.
오른쪽 하위 트리에서 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. 사후 순회

이진 트리의 후위 순회는 먼저 왼쪽 하위 트리를 순회한 다음 오른쪽 하위 트리를 순회하고 마지막으로 루트를 순회합니다.

사후 순회 알고리즘은 다음과 같습니다.

왼쪽 하위 트리에서 postorder()를 호출합니다.
오른쪽 하위 트리에서 postorder()를 호출합니다.
루트를 통과합니다.

위 트리의 사후 순회는 다음과 같습니다.

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. 레벨 순서 순회

레벨 순서 순회는 대기열을 사용하여 방문할 노드를 추적합니다. 노드를 방문한 후 해당 자식이 대기열에 놓입니다. 순회할 새 노드를 얻으려면 대기열에서 요소를 꺼냅니다.

알고리즘은 다음과 같습니다.

빈 대기열 초기화
임시를 루트로 설정하여 시작

대기열이 비어 있지 않을 때까지 루프 실행\n

임시 데이터 인쇄
왼쪽에서 오른쪽 순서로 temp의 자식을 큐에 넣습니다.
대기열에서 노드를 제거하고 그 값을 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);
           }
       }
   }

Java에서 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 순회에 관한 것입니다. C++에서 DFS 구현을 얻으려면 이 자습서를 참조하십시오.