14. 트리

트리

빠른 설명

트리는 사이클이 없고 연결된 그래프다. 정점이 $N$개인 트리는 항상 간선이 $N-1$개다.

언제 쓰는가

• 부모-자식 관계
• 계층 구조
• 루트에서 각 노드까지의 깊이
• 서브트리 크기 계산

핵심 성질

• 두 정점 사이의 단순 경로가 정확히 하나다.
• 정점 $N$개, 간선 $N-1$개다.
• DFS/BFS로 쉽게 순회할 수 있다.

참고자료

• Wikipedia - Tree
• CP-Algorithms - Trees
• GeeksforGeeks - Tree Data Structure
• 나무위키 - 트리

C++ 코드

#include <algorithm>
#include <deque>
#include <functional>
#include <iostream>
#include <queue>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;
 
vector<vector<int>> tree;
vector<int> subtree_size;
 
void dfs(int cur, int parent) {
    subtree_size[cur] = 1;
    for (int next : tree[cur]) {
        if (next == parent) continue;
        dfs(next, cur);
        subtree_size[cur] += subtree_size[next];
    }
}
 
int main() {
    int n = 5;
    tree.assign(n, {});
    subtree_size.assign(n, 0);
 
    tree[0] = {1, 2};
    tree[1] = {0, 3, 4};
    tree[2] = {0};
    tree[3] = {1};
    tree[4] = {1};
 
    dfs(0, -1);
    for (int x : subtree_size) cout << x << ' ';
}

Python 코드

tree = [
    [1, 2],
    [0, 3, 4],
    [0],
    [1],
    [1],
]
subtree_size = [0] * len(tree)
 
def dfs(cur, parent):
    subtree_size[cur] = 1
    for nxt in tree[cur]:
        if nxt == parent:
            continue
        dfs(nxt, cur)
        subtree_size[cur] += subtree_size[nxt]
 
dfs(0, -1)
print(subtree_size)