트리의 순회, 탐색

트리의 모든 노드를 방문하는 순서

종류

- preorder (전위순회)

- 루트 노드의 방문

- 왼쪽 서브트리의 순회

- 오른쪽 서브트리의 순회

ex)

탐색 순서를 살펴보면 그래프의 DFS순서와 같다는 것을 알 수 있다.

- inorder (중위순회)

- 왼쪽 서브트리의 순회

- 루트 노드의 방문

- 오른쪽 서브트리의 순회

ex)

- postorder (후위 순회)

- 왼쪽 서브트리의 순회

- 오른쪽 서브트리의 순회

- 노드방문

ex)

코드짜보기

백준 1991번 문제를 통해 트리의 순회에 대한 코드를 짜는 법을 살펴볼 것이다.

이 문제는 순회의 방법에 따라 코드를 짜는 것 자체가 풀이가 되기 때문에

만약 이 문제를 맞췄다면 어느정도 트리의 순회에 대해 이해를 했다고 볼 수 있을것이다.

#include <iostream>

using namespace std;

int tree[26][2];

void inorder(int node)
{
	if (tree[node][0] >= 0) // '.' - 'A'를 하면 음수가 나오기 때문에 
							// 이것을 반영한 것이다.
		inorder(tree[node][0]);
	printf("%c", node + 'A');
	if (tree[node][1] >= 0)
		inorder(tree[node][1]);
}
void preorder(int node)
{
	printf("%c", node + 'A');
	if (tree[node][0] >= 0)
		preorder(tree[node][0]);
	if (tree[node][1] >= 0)
		preorder(tree[node][1]);
}
void postorder(int node)
{
	if (tree[node][0] >= 0)
		postorder(tree[node][0]);
	if (tree[node][1] >= 0)
		postorder(tree[node][1]);
	printf("%c", node + 'A');
}
int main()
{
	int N;
	scanf("%d", &N);
	char x, y, z;
	for (int i = 0; i < N; i++) {
		cin >> x >> y >> z;
		int node = x - 'A';
		tree[node][0] = y - 'A';
		tree[node][1] = z - 'A';
	}
	preorder(0);
	printf("\n");
	inorder(0);
	printf("\n");
	postorder(0);
	printf("\n");
}

트리의 탐색같은 경우 DFS나 BFS 알고리즘을 이용해서 할 수 있다.

트리는 방향성이 없으며 두 정점사이의 경로가 하나밖에 없기 때문에

BFS를 이용하면 최단 거리도 구할 수 있다.