실전 알고리즘 0x19강 - 트리

트리

[ 정의와 성질 ]

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

 

트리( Tree )

= 무방향이면서 사이클이 없는 연결 그래프

= 연결 그래프이면서 임의의 간선을 제거하면 연결 그래프가 아니게 되는 그래프

= 임의의 두 점을 연결하는 simple path(정점이 중복해서 나오지 않는 경로)가 유일한 그래프

= V개의 정점을 가지고 V-1개의 간선을 가지는 연결 그래프

= 사이클이 없는 연결 그래프이면서 임의의 간선을 추가하면 사이클이 생기는 그래프

= V개의 정점을 가지고 V-1개의 간선을 가지는 Acyclic(=사이클이 없는) 그래프

 

- 트리에서는 임의의 노드를 루트로 만들 수 있다.

 

[ BFS, DFS ]

- 트리는 그래프의 한 종류이기 때문에 그래프에서의 BFS와 DFS랑 똑같이 구현할 수 있다.

- BFS 예시 코드 1 : 부모 배열 채우기

vector<int> adj[10];
int p[10];
void bfs(int root) {
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (int nxt : adj[cur]) {
			if (p[cur] == nxt)continue;
			q.push(nxt);
			p[nxt] = cur;
		}
	}
}

- BFS 예시 코드 2 : 부모와 depth 배열 채우기

vector<int> adj[10];
int p[10];
int depth[10];
void bfs(int root) {
	queue<int> q;
	q.push(root);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		for (int nxt : adj[cur]) {
			if (p[cur] == nxt)continue;
			q.push(nxt);
			p[nxt] = cur;
			depth[nxt] = depth[cur] + 1;
		}
	}
}

- DFS 예시 코드 1 : 부모와 depth 배열 채우기, 비 재귀

vector<int> adj[10];
int p[10];
int depth[10];
void bfs(int root) {
	stack<int> s;
	s.push(root);
	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		cout << cur << ' ';
		for (int nxt : adj[cur]) {
			if (p[cur] == nxt)continue;
			s.push(nxt);
			p[nxt] = cur;
			depth[nxt] = depth[cur] + 1;
		}
	}
}

- DFS 예시 코드 2 : 부모와 depth 배열 채우기, 재귀 ( Stack메모리 제한이 있으면 초과할 수 있다.)

vector<int> adj[10];
int p[10];
int depth[10];
void dfs(int cur) {
	cout << cur << ' ';
	for (int nxt : adj[cur]) {
		if (p[cur] == nxt) continue;
		p[nxt] = cur;
		depth[nxt] = depth[cur] + 1;
		dfs(nxt);
	}
}

- DFS 예시 코드 3 : 단순 순회, 재귀

vector<int> adj[10];
void dfs(int cur,int par) {
	cout << cur << ' ';
	for (int nxt : adj[cur]) {
		if (par == nxt) continue;
		dfs(nxt,cur);
	}
}

 

[ 이진트리의 순회 ]

- 이진 트리 : 각 정점의 자식이 최대 2개인 트리

- 레벨 순회, 전위/중위/후위 순회가 있다.

- 이진트리를 그래프처럼 표현할 수 있지만 그렇게 하면 왼쪽 자식과 오른쪽 자식을 구분할 수 없다. 구조체나 클래스를 만들고 left, right라는 이름의 구조체 변수를 두는 방법도 있다. 다음처럼 배열로 구현할 수 있다.

- 레벨 순회 (Level-order Traversal) : 높이 순으로 방문하는 순회이다. (루트에서 BFS를 돌리면 된다)

int lc[9] = { 0,2,4,6,0,0,0,0,0 };
int rc[9] = { 0,3,5,7,0,8,0,0,0 };
void bfs() {
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		cout << cur << ' ';
		if (lc[cur]) q.push(lc[cur]);
		if (rc[cur]) q.push(rc[cur]);
	}
}

- 전위 순회(Preorder Traversal)

1. 현재 정점을 방문한다.

2. 왼쪽 서브 트리를 전위 순회한다.

3. 오른쪽 서브 트리를 전위 순회한다.

// 전위 순회
int lc[9] = { 0,2,4,6,0,0,0,0,0 };
int rc[9] = { 0,3,5,7,0,8,0,0,0 };
void preorder(int cur) {
	cout << cur << ' ';
	if (lc[cur] != 0)preorder(lc[cur]);
	if (rc[cur] != 0)preorder(rc[cur]);
}
//preorder(1);

- 중위 순회(Inorder Traversal)

1. 왼쪽 서브 트리를 중위 순회한다.

2. 현재 정점을 방문한다.

3. 오른쪽 서브 트리를 중위 순회한다.

// 중위 순회
int lc[9] = { 0,2,4,6,0,0,0,0,0 };
int rc[9] = { 0,3,5,7,0,8,0,0,0 };
void inorder(int cur) {
	if (lc[cur] != 0)preorder(lc[cur]);
	cout << cur << ' ';
	if (rc[cur] != 0)preorder(rc[cur]);
}
//inorder(1);

- 후위 순회(Postorder Traversal)

1. 왼쪽 서브 트리를 후위 순회한다.

2. 오른쪽 서브 트리를 후위 순회한다.

3. 현재 정점을 방문한다.

// 후위 순회
int lc[9] = { 0,2,4,6,0,0,0,0,0 };
int rc[9] = { 0,3,5,7,0,8,0,0,0 };
void postorder(int cur) {
	if (lc[cur] != 0)preorder(lc[cur]);
	if (rc[cur] != 0)preorder(rc[cur]);
	cout << cur << ' ';
}
// postorder(1);

- 서로 다른 트리라도 순회 결과가 똑같을 수 있다. 중위 순회와 다른 순회가 주어진다면 유일한 트리가 존재하고 중위 순회가 포함되어 있지 않다면 유일하지 않다.

(https://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/)

 

[ 연습 문제 ]

- 백준 11725번 : https://www.acmicpc.net/problem/11725

- 백준 1991번 : https://www.acmicpc.net/problem/1991