[바킹독 알고리즘] 0x19강 - 트리

0x00 정의와 성질

 

트리 : 무방향이면서 사이클이 없는 연결 그래프(Undirected Acyclic Connected Graph)

 

 

트리의 여러 종류 예시

 

 

 

 

모두 같은 트리이지만 루트가 달라지면 각 노드의 부모 또한 달라진다.

 

 

 

 

 

0x01 BFS, DFS

BFS

부모 정보가 필요한 문제에서 이를 활용할 수 있다

 

 

자식의 depth는 부모의 depth + 1

 

 

 

 

 

 

DFS

BFS코드에서 queue를 stack으로 바꾸면 DFS로 처리된다

 

 

 

재귀를 이용할 때는 스택 메모리가 1MB로 제한될 경우 등 제한이 있는지에 주의해야된다

 

 

 

부모 배열이나 depth 배열 등을 굳이 저장할 필요가 없고 단순 순회 목적이라면 코드가 간결해진다

 

 

 

 

 

 

0x02 이진 트리의 순회

레벨 순회

 

레벨순회는 BFS랑 같다고 보면 된다. 위에서부터 흝고 내려가는 순서이다. 위 예시 순서로는 1>2>3>4>5>6>7>8 이다.

 

 

전위 순회

순서

1. 현재 정점을 방문한다.
2. 왼쪽 서브 트리를 전위 순회한다.
3. 오른쪽 서브 트리를 전위순회한다.

 

 

 

 

 

 

중위 순회

순서

1. 왼쪽 서브 트리를 중위 순회한다.
2. 현재 정점을 방문한다.
3. 오른쪽 서브 트리를 중위 순회한다.

 

중위 순회는 왼쪽 서브트리 > 나 > 오른쪽 서브트리 순으로 처리하는 순회 방법이다.

 

 

 

 

 

 

다른 모양의 트리이더라도 순회 결과가 동일할 수도 있다

 

 

 

 

 

후위 순회

순서

1. 왼쪽 서브 트리를 후위 순회한다.
2. 오른쪽 서브 트리를 후위 순회한다.
3. 현재 정점을 방문한다.

 

 

 

 

 

0x03 연습 문제

BOJ 11725번:트리의 부모 찾기

11725번: 트리의 부모 찾기

 

 

#include <bits/stdc++.h>
using namespace std;

int n;
vector<int> adj[100005];
int p[100005];

void dfs(int cur){
    for(int nxt : adj[cur]) {
        if(p[cur] == nxt) continue;
        p[nxt] = cur;
        dfs(nxt);
    }
}
int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> n;
    for(int i =0; i < n-1; i++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1);
    for(int i=2; i<=n; i++) cout << p[i] << '\n';
}

 

 

 

 

 

 

 

 

 

 

 

 

BOJ 1991번: 트리 순회

1991번: 트리 순회

 

 

 

#include <bits/stdc++.h>
using namespace std;

int n;
int lc[29];
int rc[29];

void preorder(int cur){
    cout << char(cur+'A'-1);
    if(lc[cur] != 0) preorder(lc[cur]);
    if(rc[cur] != 0) preorder(rc[cur]);
}
void inorder(int cur){
    if(lc[cur] != 0) inorder(lc[cur]);
    cout << char(cur+'A'-1);
    if(rc[cur] != 0) inorder(rc[cur]);
}
void postorder(int cur){
    if(lc[cur] != 0) postorder(lc[cur]);
    if(rc[cur] != 0) postorder(rc[cur]);
    cout << char(cur+'A'-1);
}

int main(void){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        char c, l, r;
        cin >> c >> l >> r;
        if(l != '.') lc[c-'A'+1] = l-'A'+1;
        if(r != '.') rc[c-'A'+1] = r-'A'+1;
    }
    preorder(1); cout << '\n';
    inorder(1); cout << '\n';
    postorder(1); cout << '\n';
}