5

根据Homespring 提出的语言标准,逆流而上的鲑鱼需要在鱼的勾选上执行“河流系统的有序搜索……以找到与鲑鱼同名的河流节点”(第 6.4.2 节)。问题是河流节点存储在 n 叉树中,所以我不确定如何对这棵树进行有序搜索。谷歌搜索没有发现任何相关内容,维基百科页面甚至没有提到任何类型的遍历。是否可以按顺序遍历k-ary树?

4

1 回答 1

4

是的,确实可以做到这一点!让我们以此类推。在二叉树中,节点如下所示:

            +---+
            | 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]);
}
于 2016-11-25T23:08:10.027 回答