有可能按顺序遍历k叉树吗？

Question

根据Homespring提出的语言标准，向上游移动的鲑鱼需要在“河流系统中执行顺序搜索...以找到与鲑鱼名称相同的河流节点”（第6.4.2节）。问题是，河流节点存储在一个n叉树中，所以我不确定如何进行这棵树的顺序搜索。谷歌搜索没有相关结果，维基百科页面甚至没有提到任何遍历方式。在k叉树中进行顺序搜索是否可能？

- Ontonator

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

- templatetypedef

---

那么如果每个节点只有一个关联值，那么这个值会被访问多次吗？ - Ontonator

@Ontonator 在这种情况下，谈论“中序遍历”会有点困难。有一个相关的遍历顺序叫做欧拉遍历，可能是你要找的东西？ - templatetypedef

我认为不是这样的，因为鲑鱼会朝着具有相同名称的节点的第一个出现位置前进，所以搜索最终将等同于先序搜索。无论如何，我认为这是我们能够得到的最接近正确解决方案，因此我已将其标记为正确。 - Ontonator