木構造（ツリー構造）の探索アルゴリズムは、ツリー内のすべてのノードを特定の順序で訪問する方法です。主に深さ優先探索（DFS: Depth-First Search）と幅優先探索（BFS: Breadth-First Search）の2つに大別されます。さらに、DFSには前順（Pre-order）, 中順（In-order）, 後順（Post-order） という3つの主要な方法があります。

DFSは、できるだけ深くツリーの枝を辿ってからバックトラックする探索方法です。

順序:

1. 現在のノードを訪問
2. 左の子ノードを再帰的に訪問
3. 右の子ノードを再帰的に訪問

例:

    A
   / \
  B   C
 / \
D   E

前順: A → B → D → E → C

メリット:

• ノードを訪れた順序でコピーを作成するのに適している。
• 構造全体を保持したままシリアライズ（保存）するのに便利。

デメリット:

• ソートされたデータを得ることはできない（特に二分探索木では中順が必要）。

活用方法:

• ツリー構造のクローン作成、ディレクトリのコピー操作。

順序:

1. 左の子ノードを再帰的に訪問
2. 現在のノードを訪問
3. 右の子ノードを再帰的に訪問

例:

    A
   / \
  B   C
 / \
D   E

中順: D → B → E → A → C

メリット:

• 二分探索木（BST） では、中順探索を行うとソート済みの順序でノードを取得できる。

デメリット:

• バランスの悪いツリーの場合、探索が非効率になることがある。

活用方法:

• BSTにおけるデータのソートと検索、数式の評価（中置記法）。

順序:

1. 左の子ノードを再帰的に訪問
2. 右の子ノードを再帰的に訪問
3. 現在のノードを訪問

例:

    A
   / \
  B   C
 / \
D   E

後順: D → E → B → C → A

メリット:

• ノードの削除やメモリ解放の処理に適している（子ノードを先に処理するため）。
• ディレクトリやファイルを削除する際の手順に対応。

デメリット:

• ソートには適さない。
• ノードの構造を保持するのが難しい。

活用方法:

• ディレクトリの削除、数式の評価（後置記法）。

BFSは、各レベルのノードを順番に訪問します。最初に根ノードを訪問し、その後は子ノードをレベルごとに広がって探索します。

例:

    A
   / \
  B   C
 / \
D   E

BFS: A → B → C → D → E

メリット:

• 最短経路の探索に適している（グラフ理論でも利用される）。
• ツリーのレベルごとの情報を得るのに便利。

デメリット:

• メモリ使用量が多くなる（全てのノードをキューに保持するため）。
• 深さが大きいツリーでは非効率。

活用方法:

• 最短経路問題（例: ダイクストラ法の前処理）、ネットワーク探索、AIの状態探索（パズル解法など）。

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def in_order_traversal(node):
    if node:
        in_order_traversal(node.left)
        print(node.value, end=' ')
        in_order_traversal(node.right)

# ツリーの構築
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')

in_order_traversal(root)
# 出力: D B E A C

from collections import deque

def bfs(root):
    queue = deque([root])
    while queue:
        node = queue.popleft()
        print(node.value, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

bfs(root)
# 出力: A B C D E

• ソートが必要 → 中順探索（In-order）
• 最短経路を探す → 幅優先探索（BFS）
• ツリーのコピーや保存 → 前順探索（Pre-order）
• ノードの削除や後処理 → 後順探索（Post-order）
• メモリ制限が厳しい場合 → 深さ優先探索（DFS）