リンクリストや一次元配列などの線形データ構造とは異なり、木は複数の方法で探索することができます。 木は深さ優先または幅優先で走査されるかもしれません。 深さ優先の場合、インオーダー、プレオーダー、ポストオーダーの3つの方法がある。 これらの基本的な探索の他に、反復深化探索のような深さ制限のある探索など、より複雑な、あるいはハイブリッドな方法が可能である。 後者は広さ優先探索と同様に、無限木の探索にも使用できる（以下を参照）。
木探索のためのデータ構造編集
木を探索するには、何らかの方法ですべてのノードを反復する必要がある。 与えられたノードから複数の可能な次のノードが存在するため（線形データ構造ではない）、逐次計算を仮定すると（並列ではない）、いくつかのノードは後で訪れるために何らかの方法で延期保存されなければならない。 これは、スタック（LIFO）やキュー（FIFO）を介して行われることが多い。 木は自己参照 (再帰的に定義された) データ構造であるため、走査は非常に自然で明確な方法で再帰またはより微妙には中核再帰によって定義することができる。45-61
2項木の深さ優先探索Edit
- 前順（位置赤●でノードアクセス）。
F, B, A, D, C, E, G, I, H;
- In-order (node access at position green ●):
A, B, C, D, E, F, G, H, I;
- Post-order (node access at position blue ●):
A, C, E, D, B, H, I, G, F.
In-order (node access at position green ●):
B, B, E, F, G, F.
これらの検索は、次の兄弟に行く前に各子で検索木をできるだけ深くするので、深さ優先検索 (DFS) と呼ばれる。 二分木の場合、それらは現在のノードから始まる各ノードでのアクセス操作として定義され、そのアルゴリズムは以下の通りである：
二分木を走査するための一般的な再帰パターンは以下の通り：
- 再帰的引数Nまで1レベル下がり、Nが存在すれば（空でなければ）以下の3つの操作をある順序で実施する。 L: Nの左部分木を再帰的に走査する。 R: Nの右辺の部分木を再帰的に走査する。 N: 現在のノードN自身へのアクセス（訪問）。
- 1レベル上がってNの親ノードに到着して戻る。
ノードに対して、どの位置で（図では赤、緑、青の）パルクール（トラバーサル）を行うか、ノードの訪問（アクセス）の方法（パターン）は3つある。 1つの色を選択すると、後述するように、ノードの訪問が1回だけ行われることになる。
F-B-A-A-B-D-C-D-E-E-D-F-G- I-H-H-H- I- I-G-F
Pre-order, NLREdit
- 現在のノードのデータ部（図では赤の位置）にアクセスする。
- pre-order関数を再帰的に呼び出して左サブツリーをトラバースする。
- pre-order関数を再帰的に呼び出して右サブツリーをトラバースする。
親ノードがその子ノードのどれよりも先に処理されるため、pre-order traversalはトポロジカルソートされます。
In-order, LNREdit
- in-order関数を再帰的に呼び出して左サブツリーをトラバースする。
- 現在のノードのデータ部分（図では緑の位置）にアクセスします。
- インオーダー関数を再帰的に呼び出して、右側のサブツリーをトラバースします。
各ノードにおいて、キーがその左サブツリーのすべてのキーより大きく、その右サブツリーのすべてのキーより小さいように順序付けられた二項探索木において、順方向探索はキーを昇順に並べたものを取得する。
Reverse in-order, RNLEdit
- 逆順序関数を再帰的に呼び出して右サブツリーをトラバースします。
- 現在のノードのデータ部分にアクセスします。
二分探索木において、逆順探索はソートされた降順でキーを取り出す。
後順序、LRNEdit
- 後順関数を再帰的に呼び出して左サブツリーを横断する。
- ポストオーダー関数を再帰的に呼び出して右側のサブツリーを走査する。
- 現在のノードのデータ部分（図では青の位置）にアクセスする。
走査のトレースはツリーの逐次化と呼ばれる。 探索の跡は各訪問ノードのリストである。 前、中、後順序に従った1つの順次化では、基礎となる木を一意に記述することはできない。 異なる要素を持つ木があるとき、木を一意に記述するには、前順序または後順序と内順序のペアで十分である。
Generic treeEdit
深さ優先探索で任意の木を横断するには、各ノードで以下の操作を行う：
- ノードが存在しない場合は戻る。
- Access (= visit) node (preorder position).
- For each i from 1 to number_of_children – 1 do:
- Recursively traverse i-th child.
- For each i to number_of_children – 1 do:
- For each node (priororder position).
- アクセスノード(順方向).
- 最後の子を再帰的に走査.
- アクセスノード(順方向後方).
- Recursively traverse i-th child.
- アクセスノード(順方向後方).
- アクセスノード(順方向).
手元の問題によっては、プレオーダー、ポストオーダー、特に (number_of_children – 1) インオーダー操作の1つが無効であったり、特定の子へのアクセスのみが望まれたりするので、これらの操作は任意である。 また、実際には、pre-order, in-order, post-order のうち、2つ以上の操作が必要な場合がある。 例えば、3項木に挿入する場合、項目を比較することで前順序操作を行う。 4131>
Breadth-first search, or level orderEdit
Trees can also be traversed in level-order, where we visit every nodes on a level before going to the lower level.
その他のタイプ編集
深さ優先探索でも幅優先探索でもない木構造探索アルゴリズムもある。 このようなアルゴリズムの1つがモンテカルロ木探索で、探索空間のランダムサンプリングに基づいて探索木を拡張し、最も有望な手の分析に集中するものである。