【Python】階層的なデータ構造の探索（ツリー探索）
ツリー構造の紹介
ツリーは、階層的に情報を整理するためのデータ構造であり、ノード（節点）とエッジ（辺）から構成されています。ツリーの最上部のノードをルートと呼び、各ノードは他のノードとエッジで繋がっています。ツリーは、例えば、ファイルシステムのディレクトリ構造、組織図、XMLデータの構造など、さまざまな場面で利用されます。
探索手法の概要
ツリー探索には主に2つの基本的な手法が存在します。深さ優先探索（DFS）と幅優先探索（BFS）です。
DFSは、ツリーの深い部分を先に探索する手法であり、スタックを使用して実行されます。一方、BFSは、ツリーの広い部分を先に探索する手法であり、キューを使用します。
深さ優先探索 (DFS) の例
深さ優先探索（DFS）は、現在のノードからできるだけ深く探索し、行き止まりに達したら、バックトラッキングして他の経路を探索します。
# 深さ優先探索の実装例
class Node:
def __init__(self, value):
self.value = value
self.children = []
def add_child(self, node):
self.children.append(node)
def dfs(root):
# ノードを処理
print(root.value)
# 子ノードを再帰的に探索
for child in root.children:
dfs(child)
# ツリーの作成
root = Node("A")
b = Node("B")
c = Node("C")
root.add_child(b)
root.add_child(c)
b.add_child(Node("D"))
c.add_child(Node("E"))
# 深さ優先探索の実行
dfs(root)
上記のコードでは、ツリーのルートから始まり、各ノードを再帰的に探索してその値を出力します。
幅優先探索 (BFS) の例
幅優先探索（BFS）は、まず現在のノードの子ノードをすべて探索し、その後、次のレベルのノードを探索します。キューを使って探索するため、最短経路を見つける際に有用です。
# 幅優先探索の実装例
from collections import deque
def bfs(root):
queue = deque([root]) # キューに最初のノードを追加
while queue:
node = queue.popleft() # キューからノードを取り出す
print(node.value) # ノードを処理
# 子ノードをキューに追加
for child in node.children:
queue.append(child)
# 幅優先探索の実行
bfs(root)
この例では、キューにノードを追加していき、各レベルのノードを順番に処理していきます。
再帰的探索
再帰的探索では、関数が自分自身を呼び出して探索を行います。特に、深さ優先探索（DFS）は再帰的に実行されることが多いです。再帰を使うと、スタックを自分で管理する必要がなくなり、シンプルなコードになります。
例えば、深さ優先探索は以下のように再帰的に実行できます。
# 再帰的なDFSの実行例（上記と同じDFS関数を使用） dfs(root)
非再帰的探索
非再帰的探索では、明示的にスタックやキューを使用して探索を行います。再帰を使う代わりに、これらのデータ構造を用いることで、探索の流れを明示的に制御することができます。非再帰的なDFSの例は、スタックを使用して実装することができます。
# 非再帰的DFSの実装例
def non_recursive_dfs(root):
stack = [root] # スタックに最初のノードを追加
while stack:
node = stack.pop() # スタックからノードを取り出す
print(node.value) # ノードを処理
# 子ノードをスタックに追加（逆順にすることでDFS順に）
for child in reversed(node.children):
stack.append(child)
# 非再帰的DFSの実行
non_recursive_dfs(root)