Data-structures-algorithms-tree-traversal

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

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

• 順番通りのトラバーサル
• 先行予約のトラバーサル
• 注文後のトラバーサル

一般に、ツリーを走査して、ツリー内の特定のアイテムまたはキーを検索または検索するか、ツリーに含まれるすべての値を印刷します。

順番通りのトラバーサル

この走査方法では、左のサブツリーが最初に訪問され、次にルート、次に右のサブツリーが訪問されます。 すべてのノードがサブツリー自体を表す場合があることを常に覚えておく必要があります。

バイナリツリーが in-order で走査される場合、出力は昇順でソートされたキー値を生成します。

In Order Traversal

*A* から開始し、順番にトラバーサルした後、その左側のサブツリー *B* に移動します。 *B* も順番に走査されます。 このプロセスは、すべてのノードが訪問されるまで続きます。 このツリーの順序走査の出力は次のようになります-

Copy

*_D→B→E→A→F→C→G_*

Copy

アルゴリズム

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

Copy

先行予約のトラバーサル

この走査方法では、ルートノードが最初に訪問され、次に左のサブツリー、最後に右のサブツリーが訪問されます。

事前注文トラバーサル

*A* から開始し、予約注文のトラバーサルに続いて、まず *A* 自体にアクセスしてから、左のサブツリー *B* に移動します。 *B* も事前注文されます。 このプロセスは、すべてのノードが訪問されるまで続きます。 このツリーの事前順序走査の出力は次のようになります-

Copy

*_A→B→D→E→C→F→G_*

Copy

アルゴリズム

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

Copy

注文後のトラバーサル

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

注文順のトラバース

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

Copy

*_D→E→B→F→G→C→A_*

Copy

アルゴリズム

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

Copy

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