k-aryツリーを順番にトラバースすることは可能ですか？

Question

the Homespring proposed language standardによると、上流のサーモンは、魚のチックアップ（セクション6.4.2）の「川システムの順不同検索...鮭と同じ名前の川ノードを見つける」必要があります。問題は、川のノードがn個のツリーに格納されていることです。そのため、このツリーを順番に検索する方法がわかりません。 Google検索では何も関係がなくなり、Wikipediaのページにはどんな種類のトラバーサルも言及されていません。 k-aryツリーを順番にトラバースすることは可能ですか？

Answer 1

はい、実際にこれを行うことができます！類推によって理由を考えましょう。バイナリツリーでは、ノードは次のようになります。

は

  +---+ 
      | v | 
      +---+ 
     / \ 
      T0  T1 

トラバーサルが、その後のように行われるINORDERは次のとおりです。

1. は、再帰的にT0のINORDERトラバーサルを行う
2. が再帰的に行う訪問のV
3. T1のインオーダートラバーサル。

言い換えれば、値を左から右に移動すると想像することができます。掃引は最初にT0に当たってからvをヒットし、T1にヒットします。

+----+----+----+ ... +----+ 
    | v0 | v1 | v2 | ... | vn | 
    +----+----+----+ ... +----+ 
/ | | |  |  \ 
    T0 T1 T2 T3 Tn  Tn+1 

我々はここで、「左から右にスイープ」のアイデアを使用している場合は、我々はこれを行うだろう：

多分木中のノードが次のようになります

1. は、再帰的に行いますT0のインオーダーウォーク
2. v0をご覧ください。
3. T1のインオーダーウォークを再帰的に行います。
4. v1をご覧ください。
5. ...
6. Tnのinorder walkを再帰的に行います。
7. vnをご覧ください。
8. Tn + 1のインオーダーウォークを再帰的に行います。ここで

は、このためのいくつかの擬似コードです：

void inorderWalk(Node* v) { 
    if (v == null) return; 

    for (int i = 0; i < v.numChildren; i++) { 
     inorderWalk(v.child[i]); 
     visit(v.value[i]); 
    } 
    inorderWalk(v.child[v.numChildren]); 
}