是否可以按顺序遍历k叉树？

Question

根据the Homespring proposed language standard，三文鱼逆流而上需要对鱼tick up执行"an in-order search of the river system … to find a river node with the same name as the salmon"（第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

如果我们在这里使用 "sweep from left to right" 想法，我们会这样做：

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]);
}