3348. 树的双亲存储法

单点时限: 2.0 sec

内存限制: 256 MB

前面介绍了树的链式存储结构,那么如何用顺序存储来存储一棵树呢?在顺序存储时,我们除了存储每个结点值外,还要存储树中结点与结点之间的逻辑关系(即双亲与孩子结点之间的关系)。下面介绍树的双亲存储法。

  1. 编号,从根结点(它的编号为 0)开始,按从上到下的层次顺序,每一层按从左到右的顺序,递增地依次给每一个结点一个编号,图1上标出了各个结点的编号。
  2. 存储,如果用一维数组 tree[n] 来存储图1中的这棵树,则树中每个结点存储在 tree[n] 中的下标等于它的编号值,而且在数组 tree[n] 中, 每个元素是一个结构体,它包含两个成员,dataparent:其中 tree[i].data 存储一个结点的值, tree[i].parent 存储该结点的双亲结点在该数组中的下标。根结点 tree[O].parent=-1, 图2为图1中树的存储数组。

现在给出一棵树的顺序存储结构,打印树的后序遍历。

输入格式

第一行一个整数 $n$ $(1 \leq n \leq 100~000)$,表示有 $n$ 个节点,节点的编号从 $0$ 到 $n-1$。

接下来一行 $n$ 个整数,依次表示每个节点的双亲 (tree[i].parent)。数据保证合法,能构成一棵树,并且 tree[0].parent=-1

输出格式

输出树的后序遍历。

样例

Input
10
-1 0 0 0 1 1 1 3 3 8
Output
4 5 6 1 2 7 9 8 3 0

305 人解决,379 人已尝试。

454 份提交通过,共有 3006 份提交。

2.8 EMB 奖励。

创建: 7 年,2 月前.

修改: 6 年,1 月前.

最后提交: 1 月前.

来源: 数据结构上机实践课程(2018年秋)

题目标签