test

위계가 존재하는 트리에서 두 노드 a와 b가 있을 때, a가 b의 ancestor(조상)인지 확인해야 할 때 사용하는 방법이다.

트리의 루트노드에서부터 dfs순회를 시작해서 preorder로 한 번, postorder로 한 번 각각 돌아준다. 그러면 각 순회 별로 노드의 방문 순서를 기록을 해둘텐데, 당연히 preorder의 순서와 postorder의 순서는 다를 것이다. 여기서 생기는 특징은 preorder는 루트노드에서 가까울수록 순회 순서가 빠를 것이고, postorder는 루트노드에서 가까울수록 순회 순서가 느리다. 이를 이용해서 ancestor를 판별할 수 있다.

바로 a가 b의 ancestor라면 preorder로 돌았을 때는 a가 b보다 먼저 등장할 것이고, postorder로 돌았을 때는 a가 b보다 나중에 등장한다는 것이다. 따라서 preorder, postorder를 돌 때부터 각 노드별로 몇 번째 방문하는지 기록해두고 쿼리에서 대소를 비교해주면 단 O(1)만에 a가 b의 ancestor인지 판별할 수 있게 된다.

밑은 구현 코드이다.

#include<stdio.h>
#include<vector>
using namespace std;
const int SIZE=10;
vector<int> tree[SIZE];
int pre[SIZE],post[SIZE];
int cnt=1;

void PreOrder(int node,int p){
    pre[node]=cnt++;
    for(int next:tree[node]){
        if(next==p) continue;
        PreOrder(next,node);
    }
}

void PostOrder(int node,int p){
    for(int next:tree[node]){
        if(next==p) continue;
        PostOrder(next,node);
    }
    post[node]=cnt++;
}

void tree_init(){
    tree[1].push_back(2);
    tree[2].push_back(1);
    tree[1].push_back(3);
    tree[3].push_back(1);
    tree[2].push_back(4);
    tree[4].push_back(2);
    tree[2].push_back(5);
    tree[5].push_back(2);
}

void Query(int anc,int child){
    if(pre[anc]<pre[child] && post[anc]>post[child])
        printf("%d is ancestor of %d.\n",anc,child);
    else printf("%d is NOT ancestor of %d.\n",anc,child);
}

int main(){
    tree_init();
    PreOrder(1,0);
    cnt=1;
    PostOrder(1,0);

    for(int i=1 ; i<=5 ; i++)
        printf("%d : %d\n",i,post[i]);


    Query(1,3);


    return 0;
}