문제
다음은 특정 단어(또는 문장)를 트리 형태로 구성한 것으로, in-order 형식으로 순회하여 각 노드를 읽으면 원래 단어를 알 수 있다고 한다.
위 트리를 in-order 형식으로 순회할 경우 SOFTWARE 라는 단어를 읽을 수 있다.
[제약 사항]
총 10개의 테스트 케이스가 주어진다.
총 노드의 개수는 100개를 넘어가지 않는다.
트리는 완전 이진 트리 형식으로 주어지며, 노드당 하나의 알파벳만 저장할 수 있다.
노드가 주어지는 순서는 아래 그림과 같은 숫자 번호대로 주어진다.
[입력]
각 테스트 케이스의 첫 줄에는 각 케이스의 트리가 갖는 정점의 총 수 N(1≤N≤100)이 주어진다. 그 다음 N줄에 걸쳐 각각의 정점 정보가 주어진다.
해당 정점에 대한 정보는 해당 정점의 알파벳, 해당 정점의 왼쪽 자식, 오른쪽 자식의 정점번호가 차례대로 주어진다.
정점번호는 1부터 N까지의 정수로 구분된다. 입력에서 정점 번호를 매기는 규칙은 위와 같으며, 루트 정점의 번호는 반드시 1이다.
입력에서 이웃한 알파벳이나 자식 정점의 번호는 모두 공백으로 구분된다.
위의 예시에서, 알파벳 S가 7번 정점에 해당하면 “7 S”으로 주어지고, 알파벳 ‘F’가 2번 정점에 해당하면 두 자식이 각각 알파벳 ‘O’인 4번 정점과 알파벳 ‘T’인 5번 정점이므로 “2 F 4 5”로 주어진다.
총 10개의 테스트 케이스가 주어진다,
[출력]
#부호와 함께 테스트 케이스의 번호를 출력하고, 공백 문자 후 테스트 케이스의 답을 출력한다.
코드
#include<iostream>
#include<cmath>
using namespace std;
struct node {
int data;
char alpha;
node* left, * right;
};
constexpr size_t MAX_NODE = 999;
int node_count = 0;
node node_pool[MAX_NODE];
node* new_node(int data,char alpha)
{
node_pool[node_count].data = data;
node_pool[node_count].alpha = alpha;
node_pool[node_count].left= nullptr;
node_pool[node_count].right = nullptr;
return &node_pool[node_count++];
}
void inorder(node* cur)
{
if (cur != 0)
{
inorder(cur->left);
cout << cur->alpha;
inorder(cur->right);
}
}
int main()
{
int n,number,left,right;
char alpha;
for (int i=0;i<10;i++)
{
cin >> n;
for (int q = 0; q < n; q++)
{
cin >> number;
if (n % 2 == 0)
{
if (n / 2 > number)
{
cin >> alpha >> left >> right;
node* node_new=new_node(number, alpha);
node_new->left = &node_pool[left-1];
node_new->right = &node_pool[right-1];
}
else if (n / 2 == number)
{
cin >> alpha >> left;
node* node_new = new_node(number, alpha);
node_new->left = &node_pool[left-1];
node_new->right = nullptr;
}
else
{
cin >> alpha;
node* node_new = new_node(number, alpha);
node_new->left = nullptr;
node_new->right = nullptr;
}
}
else
{
if (n / 2 >= number)
{
cin >> alpha >> left >> right;
node* node_new = new_node(number, alpha);
node_new->left = &node_pool[left-1];
node_new->right = &node_pool[right-1];
}
else
{
cin >> alpha;
node* node_new = new_node(number, alpha);
node_new->left = nullptr;
node_new->right = nullptr;
}
}
}
cout << "#" << i + 1<<' ';
inorder(&node_pool[0]);
cout << endl;
node_count = 0;
}
return 0;
}설명
입력에서 정점 번호를 매기는 규칙에 맞게 조건을 나누어 설정해주었고 문제의 이름과 같이 중위순회 (InOrder) 방식을 이용하여 트리를 탐색해야한다. 이는 상단에 InOrder 재귀함수를 보면 쉽게 이해할 수 있을것이다. 가장 좌측부터 탐색하고 끝까지 도달하였으면 자신으로 돌아오고 오른쪽으로 한칸씩 이동하여 탐색하는 방법이다.
후기
순회 방법에는 3가지가 있다.
-
전위순회 (Pre-Order)
: 자신 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문 -
중위순회 (Pre-Order)
: 왼쪽 서브트리 -> 자신 -> 오른쪽 서브트리 순서로 방문
Binary Search Tree에서 in-order 방문 순서는 key를 정렬한 결과와 같습니다. -
후위순회 (Post-Order)
: 왼쪽 서브트리 -> 오른쪽 서브트리 -> 자신 순서로 방문
헷갈리기 쉬우니 잘 외우고 넘어가자
