Data-structures-algorithms-tree-traversal
提供：Dev Guides
データ構造とアルゴリズム-ツリートラバーサル
トラバーサルは、ツリーのすべてのノードを訪問するプロセスであり、それらの値も出力する場合があります。 すべてのノードはエッジ（リンク）を介して接続されているため、常にルート（ヘッド）ノードから開始します。 つまり、ツリー内のノードにランダムにアクセスすることはできません。 私たちがツリーを横断するために使用する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実装を確認するには、リンクしてください：/data_structures_algorithms/tree_traversal_in_c [ここをクリック]。
