ツリー走査

コンピュータサイエンスにおいて、ツリー走査（ツリーサーチ、ツリーウォークとも呼ばれる）はグラフ走査の一種であり、ツリーデータ構造内の各ノードを（取得、更新、削除など）正確に一度だけ訪問するプロセスを指します。このような走査は、ノードを訪問する順序によって分類されます。以下のアルゴリズムは二分木を対象としていますが、他のツリーにも一般化できます。

連結リスト、一次元配列、その他の線形データ構造は、通常は線形順序で走査されますが、ツリーは複数の方法で走査できます。深さ優先または幅優先で走査できます。深さ優先で走査する一般的な方法は、順序通り、前順、後順の 3 つです。^{[ 1 ]}これらの基本的な走査方法以外にも、反復深化深さ優先探索のような深さ制限探索など、さまざまな複雑な方法やハイブリッドな方法が可能です。後者は、幅優先探索と同様に、無限ツリーの走査にも使用できます（下記参照）。

深さ優先探索

深さ優先探索（DFS）では、次の兄弟ノードに進む前に、探索ツリーを可能な限り深く掘り下げます。

深さ優先探索で二分木を走査するには、各ノードで次の操作が実行されます。^{[ 3 ] [ 4 ]}

1. 現在のノードが空の場合は、処理を終了します。
2. 以下の３つの操作を特定の順序で実行します。^{[ 5 ]}

   N: 現在のノードを訪問します。

   L: 現在のノードの左部分木を再帰的に走査します。

   R: 現在のノードの右部分木を再帰的に走査します。

トラバーサルのトレースは、ツリーのシーケンシャル化と呼ばれます。トラバーサルのトレースは、訪問した各ノードのリストです。前順、中順、後順のいずれかのシーケンシャル化では、基となるツリーを一意に記述することはできません。異なる要素を持つツリーが与えられた場合、前順または後順と中順の組み合わせのいずれかで、ツリーを一意に記述するのに十分です。ただし、前順と後順の組み合わせでは、ツリー構造にいくらかの曖昧さが残ります。^{[ 6 ]}

ノードに対する走査の位置（図では赤、緑、青）によって、ノードの訪問が行われる方法は3つあります。1つの色だけを選択すると、以下に説明するように、ノードの訪問は1回だけになります。3つの色すべてで訪問すると、同じノードが3回訪問され、「全順序」のシーケンス化が実現します。

F - B - A - A - A - B - D - C - C - C - D - E - E - E - D - B - F - G - G - I - H - H - H - I - I - G - F

予約注文、NLR

1. 現在のノード（図中の赤色の位置）を訪問します。
2. 現在のノードの左部分木を再帰的に走査します。
3. 現在のノードの右部分木を再帰的に走査します。

先行順走査はトポロジカルソートされた走査である。なぜなら、親ノードは子ノードの処理が完了する前に処理されるからである。

注文後、LRN

1. 現在のノードの左部分木を再帰的に走査します。
2. 現在のノードの右部分木を再帰的に走査します。
3. 現在のノード（図中の青色の位置）を訪問します。

後順走査は、二分式木の後置式を取得するのに役立ちます。

順番に、LNR

1. 現在のノードの左部分木を再帰的に走査します。
2. 現在のノード（図中の緑色の位置）を訪問します。
3. 現在のノードの右部分木を再帰的に走査します。

二分探索木では、各ノードのキーがその左部分木内のすべてのキーよりも大きく、右部分木内のすべてのキーよりも小さいように順序付けられているため、順序通りの走査では、キーが昇順で取得されます。^{[ 7 ]}

逆予約、NRL

1. 現在のノードに移動します。
2. 現在のノードの右部分木を再帰的に走査します。
3. 現在のノードの左部分木を再帰的に走査します。

逆順、RLN

1. 現在のノードの右部分木を再帰的に走査します。
2. 現在のノードの左部分木を再帰的に走査します。
3. 現在のノードに移動します。

逆順、RNL

1. 現在のノードの右部分木を再帰的に走査します。
2. 現在のノードに移動します。
3. 現在のノードの左部分木を再帰的に走査します。

二分探索木において、各ノードのキーがその左部分木内のすべてのキーよりも大きく、右部分木内のすべてのキーよりも小さいように順序付けられている場合、逆順走査では、キーが降順で取得されます。

任意の木

深さ優先探索を用いて任意の木構造（必ずしも二分木とは限らない）を走査するには、各ノードで以下の操作を実行します。

1. 現在のノードが空の場合は、処理を終了します。
2. 先行順走査を行うには、現在のノードにアクセスしてください。
3. 1から現在のノードのサブツリーの数-1までの各iについて、または逆方向の走査の場合は後者から前者まで、以下を実行する。
   1. 現在のノードのi番目の部分木を再帰的に走査します。
   2. 順方向走査を行うには、現在のノードにアクセスしてください。
4. 現在のノードの最後のサブツリーを再帰的に走査します。
5. 後順走査を行うには、現在のノードにアクセスしてください。

扱う問題によっては、前順、後順、特にサブツリーの数－1個のインオーダー操作のいずれかが省略可能な場合があります。また、実際には、前順、後順、インオーダー操作のうち複数が必要になる場合もあります。例えば、三分木に要素を挿入する場合、要素を比較することで前順操作が実行されます。その後、木のバランスを再調整するために後順操作が必要になる場合があります。

幅優先探索

幅優先探索（BFS）またはレベル順探索では、次の深さに進む前に、探索木を可能な限り広くします。

Pre-order traversal can be used to make a prefix expression (Polish notation) from expression trees: traverse the expression tree pre-orderly. For example, traversing the depicted arithmetic expression in pre-order yields "+ * A − BC + DE". In prefix notation, there is no need for any parentheses as long as each operator has a fixed number of operands. Pre-order traversal is also used to create a copy of the tree.

Post-order traversal can generate a postfix representation (Reverse Polish notation) of a binary tree. Traversing the depicted arithmetic expression in post-order yields "ABC − * DE + +"; the latter can easily be transformed into machine code to evaluate the expression by a stack machine. Post-order traversal is also used to delete the tree. Each node is freed after freeing its children.

In-order traversal is very commonly used on binary search trees because it returns values from the underlying set in order, according to the comparator that set up the binary search tree.

走査は通常、有限個のノード（したがって有限の深さと有限の分岐係数）を持つ木に対して行われますが、無限の木に対しても行うことができます。これは関数型プログラミング（特に遅延評価の場合）において特に重要です。無限のデータ構造は、厳密には評価されないものの、容易に定義および操作できることが多いためです。評価には無限の時間がかかるためです。チェスや囲碁のゲームツリーのように、有限の木でも大きすぎて明示的に表現できないものもあるため、それらを無限の木であるかのように解析することが有用です。

走査の基本的な要件は、最終的にすべてのノードを訪問することです。無限ツリーの場合、単純なアルゴリズムではこの要件を満たせないことがよくあります。たとえば、無限の深さを持つ二分木の場合、深さ優先探索はツリーの一方の側（慣例として左側）をたどるだけで、残りの側を訪問することはありません。また、中順走査や後順走査では、葉ノードに到達していないため（そして実際には到達しないため）、どのノードも訪問しません。これに対し、幅優先（レベル順）走査は、無限の深さを持つ二分木を問題なく走査でき、分岐係数が制限されている任意のツリーを走査できます。

一方、深さ2の木において、根ノードが無限に多くの子ノードを持ち、それぞれの子ノードがさらに2つの子ノードを持つ場合、深さ優先探索ではすべてのノードを探索します。これは、あるノードの子ノードの孫ノードをすべて探索し尽くすと、次のノードに進むためです（後順探索でない場合。後順探索では根ノードに到達することはありません）。これに対し、幅優先探索では、まず子ノードをすべて探索するため、孫ノードに到達することはありません。

実行時間のより洗練された分析は、無限順序数によって行うことができます。たとえば、上記の深さ 2 の木の幅優先探索では、ω ·2 ステップかかります。最初のレベルで ω、そして 2 番目のレベルで別の ω です。

したがって、単純な深さ優先探索や幅優先探索では、すべての無限木を網羅することはできず、非常に大きな木では効率的ではありません。しかし、ハイブリッド法では、対角線引数（垂直方向と水平方向の組み合わせである「対角線」は、深さと幅の組み合わせに対応します）を介して、任意の（可算）無限木を網羅することができます。

具体的には、無限に分岐する無限の深さの木が与えられた場合、根を ()、根の子を (1)、(2)、...、孫を (1, 1)、(1, 2)、...、(2, 1)、(2, 2)、...、といったようにラベル付けします。したがって、ノードは、有限個の（空の場合もある）正の数列と1 対 1で対応しており、これらの数は可算であり、まずエントリの合計によって、次に与えられた合計内で辞書式順序によって順序付けできます（与えられた値に合計される数列は有限個しかないため、すべてのエントリに到達できます。形式的には、与えられた自然数の構成は有限個あり、具体的にはn ≥ 1の2 ^{n −1}個の構成があります）。これにより、走査が得られます。具体的には、次のようになります。

1. （）
2. （１）
3. （１、１）（２）
4. (1, 1, 1) (1, 2) (2, 1) (3)
5. (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

等

これは、無限深度二分木をこの木にマッピングし、幅優先探索を適用すると解釈できます。親ノードからその2番目以降の子ノードに接続する「下」エッジを、最初の子ノードから2番目の子ノード、2番目の子ノードから3番目の子ノードなどへの「右」エッジに置き換えます。したがって、各ステップで、下に進む（末尾に（、1）を追加する）か、右に進む（最後の番号に1を追加する）かのいずれかになります（ルートノードは例外で、下に進むことしかできません）。これは、無限二分木と上記の番号付けとの対応関係を示しています。エントリの合計（マイナス1）はルートノードからの距離に対応し、これは無限二分木の深さn -1にある^{2n -1}個のノードと一致します（2は二分木に対応します）。

• デール、ネル。リリー、スーザン D.「Pascal Plus データ構造」。DC Heath and Company。マサチューセッツ州レキシントン。1995年。第4版。
• Drozdek, Adam. "C++によるデータ構造とアルゴリズム". Brook/Cole. Pacific Grove, CA. 2001. 第2版.
• 「ツリー横断法」（math.northwestern.edu）

• PHPにおける階層型データのデータベースへの格納と走査例
• MySQLにおける階層型データの管理
• MySQLでグラフを操作する
• Rosetta Codeで、さまざまなプログラミング言語で実装されたツリー走査を参照してください。
• 再帰を用いないツリー走査
• 木構造探索アルゴリズム
• 二分木走査
• データ構造におけるツリー走査