EOJ 3348 树的顺序存储结构

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

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

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

Input

第一行一个整数 n (1≤n≤100 000)，表示有 n 个节点，节点的编号从 0 到 n−1。

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

Output

输出树的后序遍历。

注意：如果有两个节点拥有相同的双亲节点，应该先遍历节点编号较大的那一个。

Examples

Input

10
-1 0 0 0 1 1 1 3 3 8

Output

9 8 7 3 2 6 5 4 1 0 

---

#include <bits/stdc++.h>
#define CAP 100001
using namespace std;
vector<int> v[CAP];bool cmp(int i,int j){return i>j;};
void print(int pos)
{
    if(v[pos].size()==0) return;
    sort(v[pos].begin(), v[pos].end(),cmp);
    for(int x:v[pos]){
            print(x);
        printf("%d ",x);
    }
}
int main()
{
    scanf("%d",&n);int n,bac;
    for(int i=0,tmp;i<n;i++){
        scanf("%d",&tmp);
        if(tmp==-1) bac=i;
        else
            v[tmp].push_back(i);
    }
    print(0);
    printf("%d",bac);
    return 0;
}

 

vector数组每个单元保存了元素x所有子节点（如果有的话），且将其从大到小排列(题意要求从编号最大的输出)

且一旦有子节点，继续寻找子节点是否有子节点，直到没有子节点时，开始输出。

用dfs遍历解决。