트리 변형 과제가 나온김에 포스팅해야겠다
임의의 트리에 대해서
전위와 중위 트리에 대한 정보가 주어졌을 떄 이 정보를 통해서 실제 트리를 구현해낼 수 있다.
단순히 재귀만 이용하면 되는 간단한 문제이다
전위, 중위 뿐만 아니라 중위, 후위 등등 최소 2개의 순서 정보만 있다면 실제 트리를 구현할 수 있다.
예를 들어 값 자체가 중위 순회 순서 값으로 이루어진 다음과 같은 트리를 보자
전위와 중위의 순서를 위 순서와 같다고 할 때
다음과 같은 특징을 알 수 있다.
전위의 첫번째 값인 5는 곧 전체트리의 루트노드가 된다.
그럼 전체 트리중 5의 left 와 right는 어떻게 구별해야하나?
그것은 중위 순회의 순서에서 5를 찾아주면 된다.
결국 중위순회의 [0]~[4]번째까지는 5의 left 자식이 되고 [6]~[12]번째까지는 5의 right 자식이 된다
==> 전위 기준 [1]~[5]번째까지는 left의 자식, [6]~[12]번째까지는 5의 right 자식이 된다
결국 left, right를 나누는 기준은 전위, 중위의 배열 인덱스를 이용해서 현재 트리의 루트를 찾고 좌 우 를 나누는 것이다
이 특정 구간들을 다음과 같은 재귀문을 통해서 트리를 만들 수 있다.
order[] : 전위 순회의 순서가 들어간 배열
node[] : 중위 순회 순서의 값을 weight로 가지는 각 노드들
(node[]의 경우는 쉬운 예를 위해 이런식으로 표현한 것이고, 애초에 중위 순서가 주어진다면
이 순서를 배열에 넣고 사용하면 된다. 이 경우는 아예 값 자체를 중위 순회 순서로 넣은 것이니 착각하지말자)
|
1
2
3
4
5
6
7
8
9
|
void make_tree() {
root = &node[order[0]];
root->left = left_tree(0, order[0] - 1, 1);
root->right = right_tree(order[0] + 1, tree_size - 1, order[0] + 1);
if (root->left != NULL) root->left->parent = root;
if (root->right != NULL) root->right->parent = root;
}
|
전역 변수 root는 order[0] (전위 순회의 첫번째 값) 을 루트노드로 가진다.
이 root의 left와 right에 다음과 같은 함수를 적용할 수 있다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
tree* right_tree(int l, int r, int idx) {
return left_tree(l, r, idx);
}
tree* left_tree(int l, int r, int idx) {
if (!(l <= r && idx < tree_size)) return NULL;
tree* now = &node[order[idx]];
if (l == r) return now;
int next = order[idx];
now->left = left_tree(l, next - 1, idx + 1);
now->right = right_tree(next + 1, r, idx + (next - l) + 1);
if (now->left != NULL) now->left->parent = now;
if (now->right != NULL) now->right->parent = now;
return now;
}
|
함수에서는 현재 노드를 루트로 보고 좌우의 트리를 반환받은 후에 루트노드를 리턴하는 형식이기 때문에
결국 트리를 만드는 부분은 결국 left_tree 나 right_tree 가 같다고 볼 수 있다.
코드를 간단하게 설명하자면
중위 순회 : 0 1 2 3 4 5 6 7 ,,,
전위 순회 : 5 3 1 0 2 4 7 6 ...
tree 함수는 다음과 같은 동작을 하게 된다
L,R 을 중위순회의 인덱스, idx 를 전위순회의 인덱스에 두고 좌 우를 찾게 된다
첫번째 left_tree를 기준으로
L : 0, R : 4, idx : 1 이다
order[idx] 는 3이 되고, 이 의미는 5의 좌측에 들어갈 루트노드가 3이 됨을 의미한다.
이 3을 중위 순회에서 몆번째 인덱스에 있는지 찾는다. (지금은 값 자체기 때문에 3이 된다)
중위 순회의 3번째 인덱스에 3이 있으므로, 3의 좌측에 들어갈 노드는
3 - 0(=> L이 0이므로) = 3개가 된다.
3의 좌측트리를 left_right(L, 3-1, idx+1) 의 반환값으로 호출 => 노드 0, 1, 2 를 3의 좌측트리에서 만든다
3의 우측트리를 right(3+1, R, idx+(3-L)+1) 의 반환값으로 호출 => 노드 4 를 3의 우측트리에서 만든다
다시 한번 말하지만
중위 순회를 0, 1, 2, 3, ... 순서대로 예를 든 것이기 때문에 L,R,next 같은 매개인자를 사용할 수 있는 것이고
애초에 이런식이 아닌 중위 순회의 값을 배열에 넣고 호출하는게 일반적일 것이다.
'algorithm > algorithm' 카테고리의 다른 글
| 두 노드간의 최단or최장거리 찾기 (0) | 2020.04.27 |
|---|---|
| 전위 중위 후위 순회방법 (0) | 2020.04.24 |
| c,c++ 세 점이 주어졌을 때 각도 구하기 (0) | 2020.04.10 |
| STL 사용할때 주의할 것(set,map,...) (0) | 2020.04.10 |
| Point in a Polygon - 다각형 내부점 판단 (0) | 2020.04.07 |