Javaで二分木の幅優先探索（BFS）と深さ優先探索（DFS）

2年 ago

3 minutes

幅優先探索（Breadth-First Search）と深さ優先探索（Depth-First Search）は、グラフや木を探索するための二つの手法です。このチュートリアルでは、主に木におけるBFSとDFSの探索に焦点を当てます。

深さ優先探索（DFS）とは何ですか？

アルゴリズムはルートノードから始まり、それぞれの枝を探索した後にバックトラックします。スタックを使用して実装されます。コードを書く際には、再帰スタックを使用してバックトラックします。再帰を使用することで、左右の部分木も木であり、同じプロパティを共有できる利点を活用することができます。

バイナリツリーには、DFSトラバーサルには3種類あります。

後行注文 (こうこうちゅうもん)

ノードを横断する最初の隣接ノードを訪問し、隣接ノードを優先して探索するアルゴリズム、それが「幅優先探索（BFS）」です。

このアルゴリズムは、ルートノードから始まり、レベルごとにすべてのノードを訪問します。つまり、ルートの後、ルートの直接の子ノードを順に移動します。ルートの直接の子ノードがすべて訪問された後、その子ノードに移動し、その後も続けます。BFSを実装するためには、キューを使用します。

二分木では、BFSに従うレベル順探索があります。

JavaでのBFSとDFSの実装

考慮している木を以下にしましょう。

TreeNodeクラスの構造は、以下のようになっています。

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

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

1. 先行順序の走査 (Sengo-junjo no sōsa)

二分木の先行順巡回では、まず根を巡回し、次に左の部分木、最後に右の部分木を巡回します。これは再帰的に行うことで、左右の部分木も木であるという特性を活かすためです。

前順位走査のアルゴリズムは次のようになります：

右部分木に対してpreorder()を呼び出します。

上記の木のPre-Orderトラバーサルは次のとおりです。

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. インオーダートラバーサル

二分木の中間順走査は、最初に左部分木を走査し、次に根、最後に右部分木を走査します。

中間順序走査のアルゴリズムは次のようになります：

右のサブツリーに 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. 後行順序の探索

二分木の後行順走査は、まず左の部分木を走査し、次に右の部分木を走査し、最後に根を走査します。

後行順序走査のアルゴリズムは以下の通りです:

– ルートを走査する。

上記の木のポストオーダートラバーサルは次の通りです。

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. レベル順トラバーサル (Reberu jun torabāsaru)

レベル順トラバーサルは、訪れるノードを追跡するためにキューを使用します。ノードを訪れた後、その子ノードはキューに入れます。新しいノードをトラバースするために、キューから要素を取り出します。

アルゴリズムは次の通りです。 (Arugorizumu wa tsugi no tōridesu.)

tempのデータを表示する
tempの子を左から右の順番でキューに追加する
キューからノードをデキューし、その値を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の走査について説明しました。C++でDFSの実装方法については、このチュートリアルを参照してください。また、レベル順走査のC++実装方法については、このチュートリアルを参照してください。