给定一棵存储在父数组中的 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 级只是它的子级,但在那之后我不知道如何获取它以获得子级的子级。
最佳答案
这样做的一种方法是使用 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 是从前面弹出并添加到后面的,因此节点将逐级处理。
复杂度与节点数呈线性关系。
关于c++ - 逐级遍历父数组n叉树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36823364/