ウェブサイト検索

Javaにおける二分木の幅優先探索（BFS）と深さ優先探索（DFS）

幅優先探索と深さ優先探索は、グラフと木を横断するための二つの技術です。このチュートリアルでは、主に木におけるBFSとDFSの横断に焦点を当てます。

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

アルゴリズムはルートノードから始まり、次に各ブランチを探索してからバックトラックします。スタックを使用して実装されています。コーディング中に、バックトラックのために再帰スタックを使用することがよくあります。再帰を使用することによって、左と右のサブツリーも木であり、同じ特性を共有しているという事実を活用できるようになります。

二分木には、深さ優先探索の3つのタイプがあります。

  1. 昇順
  2. 予約注文
  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. 前順巡回

二分木の先行遍歴では、まず根を訪れ、次に左部分木、最後に右部分木を訪れます。左部分木と右部分木も木であるという事実を利用するために、これを再帰的に行います。

前順走査のアルゴリズムは次のとおりです:

  1. 根を横断する。
  2. 左の部分木で preorder() を呼び出します。
  3. 右の部分木で preorder() を呼び出します。

上記の木の前順 traversal は次の通りです:

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を設定することから始めます。

  3. キューが空でない限りループを実行する

    1. テンプレートからデータを印刷します。
    2. 一時的なノードの子ノードを左から右の順序でキューに追加します。
    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);
           }
       }
   }

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実装についてはこのチュートリアルを参照してください。C++のレベルオーダートラバーサルの実装についてはこのチュートリアルを参照してください。

関連記事: