k-진 트리(k-ary tree)의 전위 순회(preorder traversal) 결과가 배열 arr[]에 순서대로 주어집니다. 목표는 이 배열로부터 동일한 k-진 트리를 다시 구성하고, 그 트리의 후위 순회(postorder traversal) 결과를 출력하는 것입니다. 여기서 말하는 완전 k-진 트리(full k-ary tree)는 모든 노드가 자식을 하나도 갖지 않거나(0개) 정확히 k개의 자식을 갖는 트리를 의미합니다.
예제 입력
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, int size = 8, int children = 2
예제 출력
자식 수가 2일 때 전위 순회 배열로부터 구성되는 완전 k-진 트리는 아래와 같습니다.
설명
정수 값으로 이루어진 배열, 즉 자식 수 k = 2인 트리의 전위 순회 결과가 주어졌습니다. 이렇게 구성된 트리의 후위 순회 결과는 3 6 1 2 1 7 5 2가 됩니다. 후위 순회는 '모든 자식 서브트리(왼쪽부터 오른쪽 순서)를 먼저 방문한 뒤, 마지막에 루트 노드를 방문한다'는 규칙에 따라 진행됩니다.
예제 입력
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1}, int size = 8, int children = 3
예제 출력
자식 수가 3일 때 전위 순회 배열로부터 구성되는 완전 k-진 트리는 아래와 같습니다.
설명
같은 배열이지만 자식 수 k = 3으로 트리를 구성할 수도 있습니다. 자식 수에 따라 같은 전위 순회 배열이라도 트리의 구조가 달라지며, 후위 순회 결과 역시 그에 맞게 계산됩니다.
알고리즘 접근 방식
핵심 아이디어는 전위 순회의 성질을 활용하는 것입니다. 전위 순회에서는 항상 루트가 먼저 등장하므로, 배열의 첫 번째 요소를 루트 노드로 삼습니다. 그다음 요소들은 루트의 첫 번째 자식 서브트리에 속하고, 각 서브트리 역시 같은 방식으로 재귀적으로 분할하여 구성합니다. 왼쪽(첫 번째) 서브트리가 비어 있다면 나머지 서브트리들도 비어 있습니다. 자식 서브트리들을 재귀 호출로 만든 뒤 부모 노드에 연결하면 됩니다.
후위 순회는 각 노드의 모든 자식 서브트리를 먼저 순회한 후, 마지막에 해당 노드의 값을 출력하는 방식으로 수행합니다.
단계별 동작
- 각 자식 서브트리에 대해 postorder(자식)를 재귀적으로 호출합니다.
- 모든 자식 순회가 끝난 뒤 root->data를 출력합니다.
- arr[] : 전위 순회 결과가 담긴 입력 배열입니다.
- k : 자식(children)의 수를 나타내는 변수입니다.
- 시작 인덱스는 count = 0으로 초기화합니다.
- Tree_Node* node = create_tree(arr, size, children, count) 호출로 트리를 생성합니다.
- new_Node(int data) 함수는 트리의 새 노드를 생성합니다.
- create_tree(int arr[], int N, int k, int height, int& count) 함수는 배열 arr[]로부터 k-진 트리를 생성합니다.
- 노드 수가 0 이하이면 NULL을 반환합니다. 즉, 구성할 트리가 없습니다.
- newNode = new_Node(arr[count])로 배열의 현재 요소로 새 노드를 초기화합니다.
- (newNode == NULL)이 참이면 트리를 만들 수 없습니다.
- i = 0부터 i < k까지 for 루프로 배열을 순회합니다.
- (count < N - 1 && height > 1)이면 count를 증가시켜 다음 인덱스로 이동하고, newNode->root.push_back(create_tree(arr, N, k, height - 1, count))로 자식 노드를 트리에 추가합니다.
- 조건을 만족하지 않으면 newNode->root.push_back(NULL);을 호출하여 해당 자리를 NULL로 채우고 트리를 종료합니다.
- 마지막에 노드 포인터를 반환합니다.
- create_tree(int* arr, int N, int k, int count) 함수는 트리의 높이를 계산합니다.
- 높이는 height = (int)ceil(log((double)N * (k - 1) + 1) / log((double)k)); 공식으로 계산합니다.
- 반환문에서 위에서 구한 높이로 create_tree(arr, N, k, height, count)를 호출하여 실제 트리를 생성합니다.
- postorder_traversal(Tree_Node* node, int k) 함수는 node를 루트로 하는 k-진 트리의 후위 순회를 출력합니다.
- 노드가 NULL이면 아무 작업도 하지 않고 반환합니다.
- i = 0부터 i < k까지 for 루프로 postorder_traversal(node->root[i], k)를 재귀 호출합니다.
- for 루프가 끝난 후 node->address를 출력합니다.
구현 예제
#include <bits/stdc++.h>
using namespace std;
struct Tree_Node{
int address;
vector<Tree_Node*> root;
};
Tree_Node* new_Node(int data){
Tree_Node* newNode = new Tree_Node;
newNode->address = data;
return newNode;
}
Tree_Node* create_tree(int arr[], int N, int k, int height, int& count){
if(N <= 0){
return NULL;
}
Tree_Node* newNode = new_Node(arr[count]);
if (newNode == NULL){
cout<<"Code Dumped";
return NULL;
}
for(int i = 0; i < k; i++){
if (count < N - 1 && height > 1){
count++;
newNode->root.push_back(create_tree(arr, N, k, height - 1, count));
}else{
newNode->root.push_back(NULL);
}
}
return newNode;
}
Tree_Node* create_tree(int* arr, int N, int k, int count){
int height = (int)ceil(log((double)N * (k - 1) + 1) / log((double)k));
return create_tree(arr, N, k, height, count);
}
void postorder_traversal(Tree_Node* node, int k){
if (node == NULL){
return;
}
for(int i = 0; i < k; i++){
postorder_traversal(node->root[i], k);
}
cout<<node->address<< " ";
}
int main(){
int arr[] = {2, 5, 1, 3, 6, 7, 2, 1 };
int size = 8;
int children = 2;
int count = 0;
Tree_Node* node = create_tree(arr, size, children, count);
cout<<"전위 순회로부터 구성한 완전 k-진 트리의 후위 순회 결과: ";
postorder_traversal(node, children);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
전위 순회로부터 구성한 완전 k-진 트리의 후위 순회 결과: 3 6 1 2 1 7 5 2
복잡도 분석
트리 구성 단계에서는 배열의 각 요소를 정확히 한 번씩 처리하므로 시간 복잡도는 O(N)입니다. 후위 순회 역시 모든 노드를 한 번씩 방문하므로 O(N)이며, 생성된 트리를 저장하기 위해 O(N)의 공간 복잡도가 필요합니다.