Можно ли пройти по k-арному дереву по порядку?

Question

В соответствии с предлагаемым языковым стандартом Homespring лосось, путешествующий вверх по течению, должен выполнить "поиск по порядку речной системы…, чтобы найти речной узел с тем же названием, что и у лосося" на рыбе (см. Раздел 6.4.2). Проблема в том, что речные узлы хранятся в n-арном дереве, поэтому я не уверен, как выполнить поиск по порядку этого дерева. Поиск Google не выявил ничего релевантного, а страница Википедии даже не упоминает какой-либо обходной путь. Можно ли пройти по k-арному дереву по порядку?

Answer 1

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

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

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

1. Рекурсивно сделать обход по порядку T0
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.
7. Посетите вн.
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]);
}