有可能有序地遍历一棵k叉树吗？

Question

根据国内提出的语言标准的说法，逆流而上的鲑鱼需要“对河流系统…进行有序搜索，以找到与鲑鱼同名的河流节点”(第6.4.2节)。问题是河流节点存储在n叉树中，所以我不知道如何对这棵树进行有序搜索。谷歌搜索没有提到任何相关问题，维基百科页面甚至没有提到任何类型的遍历。有可能有序地遍历一棵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]);
}