Week8

Tree

Tree는 아래의 조건들을 만족하는 그래프입니다.

• 사이클이 존재하지 않는다.
• 어느 한 정점 u에서 다른 정점 v로 이동할 수 있는 경로가 유일하다.
• 정점의 갯수를 V개라고 하면 간선의 갯수는 V-1개이다.
• 모든 정점의 in-degree(한 정점을 기준으로 들어오는 선의 갯수)는 1이다. (단, 양방향 간선으로 표시하는 경우 약간 다를 수 있다.)
• 재귀적 속성 : 어떠한 노드를 기준으로 삼더라도 트리를 형성한다.

Tree에 사용되는 용어

• Root node : 트리의 최상위 노드
• Child node : 연결된 두 노드 중, 하위 노드
• Parent node : 연결된 두 노드 중, 상위 노드
• Sibling node : 부모가 같은 노드(형제 노드)
• Ancestor node : 부모 노드와 그의 부모 노드들
• Descendant node : 자식 노드와 그의 자식 노드들
• Leaf node : 자식 노드가 없는 노드
• Depth : 루트 노드에서 출발하여 어떤 노드에 도달하기 위해 거쳐야하는 간선의 수
• Height : 트리에서 가장 깊은 곳에 위치한 노드의 깊이(Depth)
• Subtree : 한 노드와 그의 자손들을 모두 모은 트리

Tree의 표현 방법

트리 구조는 그래프의 일종이므로 그래프와 같이 인접리스트 또는 인접행렬로 표현할 수 있습니다. 또한 자식노드가 최대 2개인 Binary tree의 경우 1차원 배열을 사용하여 간단하게 표현할 수 있습니다. 단, 이 방법으로 구현할 경우 Skewed binary tree(한쪽으로만 편향된 트리)의 경우 메모리 낭비가 심합니다. 이 방법뿐 아니라 노드의 부모노드만 저장하는 식으로 Uion-Find를 이용하여 구현할 수도 있습니다. 하지만 인접리스트를 사용하는 방법이 메모리도 효율적으로 사용할 수 있고 대부분의 상황에서 좋은 것 같습니다.

Traversal(순회)

Traversal는 트리의 모든 노드를 방문하는 순서를 의미합니다. 현재 노드의 왼쪽 자식 노드를 방문하는 것을 'L', 현재 노드를 방문하는 것을 'D', 현재 노드의 오른쪽 자식 노드를 방문하는 것을 'R'이라고 가정하겠습니다. Traversal는 아래의 3가지로 나누어집니다.

• Pre-order(전위 순회) : D -> L -> R
• In-order(중위 순회) : L -> D -> R
• Post-order(후위 순회) : L -> R -> D

예제(백준 1991번)

#include <bits/stdc++.h>

using namespace std;

vector<int> vec[33];

void pre(int s) { // 전위 순회
	if (s == -1)
		return;
	printf("%c", s + 'A');
	pre(vec[s][0]);
	pre(vec[s][1]);
}

void in(int s) { // 중위 순회
	if (s == -1)
		return;
	in(vec[s][0]);
	printf("%c", s + 'A');
	in(vec[s][1]);
}

void post(int s) { // 후위 순회
	if (s == -1)
		return;
	post(vec[s][0]);
	post(vec[s][1]);
	printf("%c", s + 'A');
}

int main() {
	int n;
	scanf_s("%d", &n);
	for (int i = 0; i < n; i++) {
		char msg[3];
		for(int j=0; j<3; j++)
			cin >> msg[j];
		int p = msg[0] - 'A';
		int l = -1;
		int r = -1;

		if (msg[1] != '.')
			l = msg[1] - 'A';
		if (msg[2] != '.')
			r = msg[2] - 'A';

		vec[p].push_back(l);
		vec[p].push_back(r);
	}

	pre(0);
	puts("");
	in(0);
	puts("");
	post(0);


	return 0;
}