【Java】階層的なデータ構造の探索（ツリー探索）
ツリー探索の概要
ツリー探索は、階層的なデータ構造であるツリーの各ノードを探索する方法を指します。ツリーは親子関係を持つノードが階層的に繋がった構造であり、データ構造の中でもよく使われます。探索アルゴリズムは、ツリーのノードを辿って、特定の条件に合致するノードを見つけるために使用されます。
ツリー構造の基本
ツリー構造にはいくつかの重要な要素があります。
- ルートノード（根）: ツリーの最上部にあるノードで、親を持たない唯一のノード。
- 子ノード: 親ノードに直結しているノード。
- 葉ノード: 子を持たないノード。
- 親ノード: 1つ以上の子ノードを持つノード。
例えば、以下のようなツリー構造があります：
A
/ \
B C
/ \ \
D E F
このツリーでは、Aがルートノードで、BとCはAの子ノード、DとEはBの子ノード、FはCの子ノードです。
深さ優先探索（DFS）
深さ優先探索（DFS）は、ツリーまたはグラフの探索方法の一つで、ノードを深く掘り下げてから戻る方式です。具体的には、まず最も深いノードを探索し、そこから親ノードに戻り、未探索のノードがあれば再度深く探索します。DFSは再帰的に実装されることが多いです。
DFSの実装の基本的な流れは以下のようになります：
- スタートノードから探索を始める。
- ノードを訪問し、子ノードがあればその子ノードを訪問する。
- 全ての子ノードを訪問したら親ノードに戻り、別の子ノードを訪問する。
- 全てのノードを訪問したら終了する。
以下はDFSの簡単なJava実装例です：
public class DFS {
class Node {
int value;
Node left, right;
Node(int item) {
value = item;
left = right = null;
}
}
void DFS(Node root) {
if (root == null) return;
System.out.print(root.value + " ");
DFS(root.left);
DFS(root.right);
}
public static void main(String[] args) {
DFS tree = new DFS();
Node root = tree.new Node(1);
root.left = tree.new Node(2);
root.right = tree.new Node(3);
root.left.left = tree.new Node(4);
root.left.right = tree.new Node(5);
tree.DFS(root);
}
}
このコードは、深さ優先でノードを探索し、ノードの値を表示します。
幅優先探索（BFS）
幅優先探索（BFS）は、ツリーまたはグラフの探索方法の一つで、最初に親ノードを訪問し、その後に子ノードを訪問していきます。BFSはキューを使用して、現在探索中のノードの隣接ノードを順次キューに追加し、探索を続けます。
BFSの実装の基本的な流れは以下の通りです：
- スタートノードをキューに追加する。
- キューからノードを取り出して、そのノードの全ての子ノードをキューに追加する。
- キューが空になるまで、次のノードをキューから取り出し続ける。
以下はBFSの簡単なJava実装例です：
import java.util.LinkedList;
import java.util.Queue;
public class BFS {
class Node {
int value;
Node left, right;
Node(int item) {
value = item;
left = right = null;
}
}
void BFS(Node root) {
if (root == null) return;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.poll();
System.out.print(node.value + " ");
if (node.left != null) queue.add(node.left);
if (node.right != null) queue.add(node.right);
}
}
public static void main(String[] args) {
BFS tree = new BFS();
Node root = tree.new Node(1);
root.left = tree.new Node(2);
root.right = tree.new Node(3);
root.left.left = tree.new Node(4);
root.left.right = tree.new Node(5);
tree.BFS(root);
}
}
このコードは、幅優先でノードを探索し、ノードの値を表示します。
二分探索木（BST）
二分探索木（BST）は、各ノードが最大2つの子ノードを持ち、左の子ノードは親ノードより小さく、右の子ノードは親ノードより大きいという特性を持つツリーです。これにより、効率的に探索を行うことができます。
BSTの探索は、ターゲットノードの値を比較し、左か右のサブツリーを再帰的に探索する方法です。
実際のJavaコード例
実際の二分探索木（BST）における探索例を示します。以下のコードでは、挿入と探索の操作を行います：
class BST {
class Node {
int value;
Node left, right;
Node(int item) {
value = item;
left = right = null;
}
}
Node root;
BST() {
root = null;
}
void insert(int value) {
root = insertRec(root, value);
}
Node insertRec(Node root, int value) {
if (root == null) {
root = new Node(value);
return root;
}
if (value < root.value)
root.left = insertRec(root.left, value);
else if (value > root.value)
root.right = insertRec(root.right, value);
return root;
}
boolean search(Node root, int value) {
if (root == null) return false;
if (root.value == value) return true;
if (value < root.value)
return search(root.left, value);
else
return search(root.right, value);
}
public static void main(String[] args) {
BST tree = new BST();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
tree.insert(80);
System.out.println(tree.search(tree.root, 40)); // true
System.out.println(tree.search(tree.root, 100)); // false
}
}