c++ - 逐级遍历父数组n叉树？

Question

给定一棵存储在父数组中的 n 叉树，子树存储在指向数组的指针数组中，其中第一个值是子树的数量:

(childArray[2][0]表明节点2有2个 child ，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 级只是它的子级，但在那之后我不知道如何获取它以获得子级的子级。

Answer 1

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

从一些队列 q 开始，并将其放入父级为 -1 的(唯一)项的索引中。现在，在每一步，直到 q 为空，

• 执行v <- pop(q)(弹出头部)
• 打印出v
• 对于 v 的每个 child w，执行push(q, v)(推尾部)

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

• 最初，q = [3](3 是父项为 -1 的项的索引)。
• 我们弹出 q，打印出 3，然后压入 0、2 和 4，所以 q = [0, 2, 4]。
• 现在我们弹出 q，打印出 0，然后压入 1，所以 q = [2, 4, 1]。

几乎按照定义，由于 q 是从前面弹出并添加到后面的，因此节点将逐级处理。

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