是否可以按順序遍歷k-ary樹？

Question

根據the Homespring proposed language standard，向上遊遊走的鮭魚需要執行「按順序搜索河流系統......以找到與鮭魚同名的河流節點」（第6.4.2節）。問題在於河流節點存儲在一個n-ary樹中，所以我不確定如何對這棵樹進行有序搜索。谷歌搜索沒有任何相關性，維基百科頁面甚至沒有提到任何類型的遍歷。是否有可能按順序遍歷k-ary樹？

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. Visit v1。
5. ...
6. 以遞歸方式做Tn的散步。
7. Visit 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]); 
}