Возможно ли пересечение k-арного дерева в порядке?

Question

Согласно the Homespring proposed language standard, лосось, идущий вверх по течению, должен выполнить «поиск в порядке речной системы ... найти речной узел с таким же названием, как лосось» на отметке рыбы (раздел 6.4.2). Проблема в том, что речные узлы хранятся в n-арном дереве, поэтому я не уверен, как вести поиск в этом дереве в порядке. Поиск в Google не принес ничего значимого, и на странице Википедии не упоминается какой-либо обход. Можно ли по ходу двигаться по k-арному дереву?

Answer 1

Да, это действительно возможно! Давайте рассуждать по аналогии. В двоичном дереве, узел выглядит следующим образом:

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

Симметричный обход Затем выполняются следующим образом:

1. Рекурсивного сделать заказовМой обход Т0
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. Рекурсивно совершать прогулку по суше.
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]); 
}