逐层遍历parent数组n-ary树？

Question

给定一棵存储在 parent 数组中的 n-ary 树，children 存储在指向数组的指针数组中，其中第一个值是 [=31] 的编号=]仁:

(childArray[2][0]表示节点2有2个children,childArray[2][1]表示其第一个child 是 5，等等）

parentArray = {3, 0, 3, -1, 3, 2, 2};
childArray = {{1, 1}, {0}, {2, 5, 6}, {3, 0, 2, 4}, {0}, {0}, {0}};

生成一棵看起来像这样的树：

  3
 /|\
0 2 4
| |\
1 5 6

使用队列，如何逐级输出树：

1 级：3

2 级：0、2、4

3 级：1、5、6

1级和2级很简单，因为1级只是根，2级只是它的children，但是之后我就不知道怎么弄了children之children.

Answer 1

这样做的一种方法是使用 queue 数据结构。

从一些 queue q 开始，然后放入 parent 为 -1 的（唯一）项目的索引中。现在，在每一步，直到 q 为空，

执行v <- pop(q)（爆头）
打印出来v
对于 v 的每个 child w，做 push(q, v)（推尾巴）

例如，以下是您案例的第一步：

最初，q = [3]（3是parent为-1的项目的索引）。
我们弹出q，打印出3，然后压入0、2、4，所以q = [0,2,4].
现在我们 pop q，打印出 0，然后压入 1，所以 q = [2, 4, 1].

几乎按照定义，由于q是从前面出栈，在后面添加，所以节点会逐级处理。

复杂度与节点数呈线性关系。

Answer 2

您将必须在树上执行 BFS（广度优先搜索），同时保持推入下一级的节点数。大纲：

q.push(root); nodesInCurrentLevel = 1; nodesInNextLevel = 0; currentLevelIndex = 1;
while q is not empty do:
  u = q.pop()
  print currentLevelIndex and u
  decrement nodesInCurrentLevel
  for every child v of u do:
    increment nodesInNextLevel
    q.push(v)
  if nodesInCurrentLevel is 0 do:
    nodesInCurrentLevel = nodesInNextLevel
    nodesInNextLevel = 0
    increment currentLevelIndex

当然，这会将输出打印为 Level 2:0 Level 2:2 等。您可以将当前级别节点存储在循环内的临时列表中并根据需要打印。

逐层遍历parent数组n-ary树？

Level by level traversal of parent array n-ary tree?

c++

arrays

algorithm

tree