データ構造とアルゴリズム-ツリートラバーサル

トラバーサルは、ツリーのすべてのノードにアクセスするプロセスであり、それらの値も出力する場合があります。すべてのノードはエッジ（リンク）を介して接続されているため、常にルート（ヘッド）ノードから開始します。つまり、ツリー内のノードにランダムにアクセスすることはできません。ツリーをトラバースするために使用する3つの方法があります-

インオーダートラバーサル
トラバーサルの事前注文
注文後のトラバーサル

通常、ツリーをトラバースして、ツリー内の特定のアイテムまたはキーを検索または検索したり、ツリーに含まれるすべての値を出力したりします。

インオーダートラバーサル

このトラバーサル方法では、最初に左側のサブツリーにアクセスし、次にルートにアクセスし、次に右側のサブツリーにアクセスします。すべてのノードがサブツリー自体を表す場合があることを常に覚えておく必要があります。

二分木がトラバースされる場合 in-order、出力は、ソートされたキー値を昇順で生成します。

から始めます A、および順序どおりの走査に続いて、左側のサブツリーに移動します B。 Bまた、順番にトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーの順序通りのトラバーサルの出力は次のようになります-

D → B → E → A → F → C → G

アルゴリズム

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

トラバーサルの事前注文

このトラバーサル方法では、最初にルートノードにアクセスし、次に左側のサブツリーにアクセスし、最後に右側のサブツリーにアクセスします。

から始めます A、および事前注文トラバーサルに続いて、最初に訪問します A それ自体を選択してから、左側のサブツリーに移動します B。 Bプレオーダーもトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのプレオーダートラバーサルの出力は次のようになります-

A → B → D → E → C → F → G

アルゴリズム

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

注文後のトラバーサル

このトラバーサル方法では、ルートノードが最後にアクセスされるため、この名前が付けられます。最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルートノードをトラバースします。

から始めます A、およびポストオーダートラバーサルに続いて、最初に左側のサブツリーにアクセスします B。 B注文後にもトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのポストオーダートラバーサルの出力は次のようになります-

D → E → B → F → G → C → A

アルゴリズム

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

ツリートラバースのC実装を確認するには、ここをクリックしてください。