[자료 구조] 트리

 

트리란?

트리란 싸이클이 없는 무방향 그래프를 말한다. 싸이클이 존재하지 않아서 모든 노드가 루트가 될 수 있다. 마치 실로 연결된 구슬이 있는데 한 구슬을 잡아서 들어올릴 때마다 그 구슬이 루트가 되고 트리 구조가 형성되는 것과 비슷하다.

 

트리 순회하기

그래프의 구조를 가지므로 BFS와 DFS를 이용할 수 있다. 이 과정에서 부모의 정보 or 깊이의 정보가 필요한 경우 중간중간에 기록해주면 된다.

1. BFS

void bfs(int root){
    queue<int> q;
    q.push(root);
    while(!q.empty()){
        int cur = q.front();
        cout << cur << " ";
        for(int nxt: g[cur]){
            if(p[cur] == nxt) continue; //이미 자식이 기록되어 있으면 pass
            q.push(nxt);
            p[nxt] = cur; //부모 정보 기록
            depth[nxt] = depth[cur] + 1; //깊이 정보 기록
        }
    }
}

BFS 2차원 그래프의 BFS와 달리 visit배열이 필요하지 않다. 부모 정보다 깊이 정보를 기록할 경우 queue에 자식들을 추가할 때 전달해주면 된다.

2. DFS

재귀

void dfs(int cur){
    cout << cur << " ";
    for(int nxt: g[root]){
        if(p[cur] == nxt) continue;
        p[nxt] = cur;
        depth[nxt] = depth[cur] + 1;
        dfs(nxt);
    }
}