Javaで二分木の幅優先探索（BFS）と深さ優先探索（DFS）
幅優先探索（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()を呼び出します。
- 右部分木に対して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() を呼び出します。
-
- 根をトラバースします。
- 右のサブツリーに 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. 後行順序の探索
二分木の後行順走査は、まず左の部分木を走査し、次に右の部分木を走査し、最後に根を走査します。
後行順序走査のアルゴリズムは以下の通りです:
-
- – 左の部分木にpostorder()を呼び出す。
-
- – 右の部分木にpostorder()を呼び出す。
- – ルートを走査する。
上記の木のポストオーダートラバーサルは次の通りです。
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の子を左から右の順番でキューに追加する
キューからノードをデキューし、その値を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++実装方法については、このチュートリアルを参照してください。
