1. 要約
- 木構造の探索として、深さ優先探索（Depth First Search）と、幅優先探索（Breadth First Search）がある
- 深さ優先探索は、探索できるところまで深く潜る戦略で、再帰またはスタックを使って実装される
- 幅優先探索は、各階層を広く横断的に探索する戦略で、キューを使って実装される
2. 幅優先探索
2.1. 幅優先探索とは？
幅優先探索は、各階層のノードを順番に探索していく。最短経路を求める問題などに使われる。
画像はhackerearthより
2.2. 幅優先探索の実装
幅優先探索の実装を行う。問題はLeetCodeの112. Path Sumを使う。
問題文
Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
二分木の根と、整数のtargetSumが与えられるので、もしその木に根から葉へのパスがあり、そのパス上の全ての値を合計するとtargetSumと等しくなる場合はTrueを返す。葉とは、子を持たないノードです。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
# 根がNoneである（=二分木が存在しない）場合は、Falseを返す
if root is None:
return False
# queueを利用して、幅優先択を行う
# (現在探索しているノード, ノード探索時点での合計値)を保持している
queue = deque([(root, root.val)])
while queue:
node, sum = queue.popleft()
# node.left, node.rightがともにNoneの場合、nodeは「葉」となる
# nodeが葉の時点での合計値 sum が targetSum と等しい場合、Trueになる
if node.left is None and node.right is None and sum == targetSum:
return True
# node.leftがNoneでない場合、node.leftをqueueに追加する
# このとき、sum の更新も行う
if node.left:
queue.append((node.left, sum + node.left.val))
# node.leftと同様のことを node.right でも行う
if node.right:
queue.append((node.right, sum + node.right.val))
# 全て探索して while を抜けた場合、根から葉までの合計値で targetSum となるものが見つからなかったので Falseを返す。
return False
3. 深さ優先探索
3.1. 深さ優先探索とは？
深さ優先探索とは、探索できるところまで深く探索していき、行き止まりになったら戻るという方法。全ての経路を調べたいときや、再帰的な問題に向いている。
画像は Wikipedia: Depth-First Searchより
深さ優先探索は、木構造においては「どのタイミングでノードの値を処理するか」によって、次の3つに分類することができる。
| 名前 | 処理順序 | 説明 |
|---|---|---|
| 前順(pre-order) | 根->左->右 | ノードに訪れた直後に処理する |
| 間順(in-order) | 左->根->右 | 左の探索が終わった時点で処理 |
| 後順（post-order) | 左->右->根 | 左右の子をすべて処理した後にノードを処理する |
3.2. 前順操作の実装
以下の木構造を考える。
これに前順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。
# ---------- ここから、BinaryTreeまで全ての探索で共通である ----------
from collections import deque
class Node:
def __init__(self, value=0):
self.value = value
self.left = None
self.right = None
class BinaryTree:
def __init__(self, array):
self.root = Node(array[0]) if array else None
queue = deque([self.root])
i = 1
while i < len(array):
current = queue.popleft()
if i < len(array):
current.left = Node(array[i])
queue.append(current.left)
i += 1
if i < len(array):
current.right = Node(array[i])
queue.append(current.right)
i += 1
# ---------- ここまでのコードは、全ての探索で共通である。 ----------
def pre_order(arr):
binary_tree = BinaryTree(arr)
stack = [binary_tree.root]
result = []
while stack:
node = stack.pop()
result.append(node.value)
if node.right:
stack.append(node.right)
if node.left:
stack.append(node.left)
return result
pre = [1, 2, 9, 3, 6, 10, 13, 4, 5, 7, 8, 11, 12, 14, 15] # 前順（pre-order）
print(pre_order(pre)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
BinaryTreeオブジェクトでは、リストを二分探索木に変換している。前順の探索は、pre_order関数で実装している。
この関数では、まず最初に BinaryTreeオブジェクトを初期化し、ルートノードを作成する。そして stack を使って探索を行っていく。スタックの性質（=Last-In First-Out)より、左右の子ノードがある場合は、右側を先にスタックへ入れて、左側を後にいれる
こうすることで、取り出すときには左のノードが最初に処理される。
3.3. 間順操作の実装
以下の木構造を考える。
これに間順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。なお、前順操作と重複する部分のコードについては省略する。
def in_order(arr):
binary_tree = BinaryTree(arr)
stack = []
current = binary_tree.root
result = []
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
result.append(current.value)
current = current.right
return result
in_ = [8, 4, 12, 2, 6, 10, 14, 1, 3, 5, 7, 9, 11, 13, 15] # 間順（in-order）
print(in_order(in_)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
前順操作と比べると少し複雑なコードである。特徴としては、while ループの入れ子である。
- current に左の子がある限り、ひたすら下っていく
- 左端（葉ノード）まで行ったら、その時点でstackからノードを取り出して値を記録
- そのノードの右の子に移動して、同じ流れを繰り返す
ノードの右側が None の時は、内側の while ループはスキップされ、次のスタック操作に移る。これにより、探索は自動的に正しい順序で進むようになっている。
3.4. 後順操作の実装
以下の木構造を考える。
これに後順操作を用いて探索していき、探索した順に表示すると、1から15まで昇順になるはずである。Pythonコードは以下の通りである。
def post_order(arr):
binary_tree = BinaryTree(arr)
stack = [binary_tree.root]
result = []
while stack:
node = stack.pop()
result.append(node.value)
if node.left:
stack.append(node.left)
if node.right:
stack.append(node.right)
return result[::-1]
post = [15, 7, 14, 3, 6, 10, 13, 1, 2, 4, 5, 8, 9, 11, 12] # 後順（post-order）
print(post_order(post)) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
後順操作は、左->右->根であった。実装では根->右->左の順に探索していき、最後に反転をさせている。
4. 終わりに
ここまで読んでくれてありがとうございました。もし間違いがあれば、コメントで教えてください。