[TREE의 조건]
1) 연결 그래프이다
2) 방향무시하였을때, 싸이클이 존재하지 않는다.
3) 트리의 간선 개수는 트리의 정점 개수보다 1작다.
TREE를 구현 할때 중요한 것은?
- 트리는 재귀적인 구조를 띈다.(DP나 분할 정복의 기법과 굉장히 잘 맞다)
-어떤 정점의 서브트리들은 서로 절대영역이 겹치지 않기때문에 각 서브트리에 대한 문제를 풀어 합치면 큰 트리의 문제를 풀 수 있다.(DP 및 분할 정복 )
[TREE의 순회]
1)전위 순회
- 모든 정점에 대해서 자기자신을 먼저 방문한 후에 자식들을 방문 (DFS의 성향이 더 강함)
2)중위 순회
-자식들 중간에 루트를 방문하는 순회, 왼쪽자식->루트->오른쪽 자식 순서 (차수가 최대 2인 트리에서 주로 사용된다.)
3)후위 순회
- 자식들을 모두 방문하고서야 루트를 방문
4)레벨 순회
- 깊이가 작은 것부터 순회한다. 루트를 먼저 방문한 후에 루트의 자식들을 큐에 넣고 큐에 들어있던 노드를 하나씩 방문 할때마다 그의 자식 들을 큐에 넣는다. 이렇게 해서 큐가 빌 때 까지 순회 (BFS와 같다.)
=>전위 ,중위, 후위 순회는 재귀함수로 구현 가능(같은 재귀로 돌리지만, 출력시점만 다르게 한다.)
다른 점은 루트의 방문 시점이다. 레벨순회만 BFS로 똑같이 구현
연습 문제 : https://www.acmicpc.net/problem/1991(트리의 순회)
#include<iostream>
using namespace std;
int N, i;
char a, b, c, tree[99][2];
void func(int x)
{
if (i == 0) //전위
cout << char(x);
if (tree[x][0] != '.')
func(tree[x][0]);
if (i == 1) //중위
cout << char(x);
if (tree[x][1] != '.')
func(tree[x][1]);
if (i == 2) //후위
cout << char(x);
}
int main()
{
cin >> N;
char R, l, r;
for (int i = 0; i < N; i++)
{
cin >> R >> l >> r;
tree[R][0] = l;
tree[R][1] = r;
}
for (i = 0; i < 3; i++)
{
func('A');
cout << endl;
}
}
