N-ary 트리를 이진 트리로 변환하는 문제란?
N-ary 트리(N진 트리)는 하나의 노드가 여러 개의 자식 노드를 가질 수 있는 트리 구조입니다. 이번 글에서는 이러한 N-ary 트리를 이진 트리(binary tree)로 인코딩(직렬화)하는 방법과, 반대로 인코딩된 이진 트리를 다시 원래의 N-ary 트리로 복원(역직렬화)하는 방법을 C++ 코드로 자세히 살펴보겠습니다.
예를 들어 다음과 같은 N-ary 트리가 입력으로 주어졌다고 가정해 보겠습니다.
이 트리를 인코딩하면 같은 데이터를 담고 있는 이진 트리 구조로 변환되며, 디코딩을 통해 원래의 N-ary 트리 그대로 되돌릴 수 있습니다.
핵심 아이디어: 왼쪽 자식-오른쪽 형제 표현법
이 문제는 왼쪽 자식-오른쪽 형제(left-child right-sibling) 기법을 활용하면 깔끔하게 해결할 수 있습니다. 핵심 규칙은 다음과 같습니다.
- 부모 노드의 첫 번째 자식은 이진 트리에서 부모의 왼쪽(left) 자식으로 연결합니다.
- 나머지 자식들은 첫 번째 자식의 오른쪽(right) 포인터를 따라 형제처럼 차례대로 연결합니다.
이렇게 하면 임의 개수의 자식을 가진 노드도 두 개의 포인터만으로 손실 없이 표현할 수 있습니다.
1. 인코딩(encode) 함수 알고리즘
- encode(root) 함수를 정의합니다.
- root가 유효하지 않으면(NULL이면) NULL을 반환합니다.
- root의 값을 갖는 새로운 이진 트리 노드(node)를 생성합니다.
- root의 자식이 존재하면, node의 left를 encode(root.children[0])의 결과로 설정합니다.
- curr 변수를 node의 left로 초기화합니다.
- i를 1부터 시작하여 root의 자식 개수보다 작을 동안 1씩 증가시키며 반복합니다.
- curr의 right를 encode(root.children[i])의 결과로 설정합니다.
- curr을 curr의 right로 갱신합니다.
- node를 반환합니다.
2. 디코딩(decode) 함수 알고리즘
- decode(root) 함수를 정의합니다.
- root가 존재하지 않으면 NULL을 반환합니다.
- root의 val 값을 갖는 새로운 N-ary 노드(node)를 생성합니다.
- curr을 root의 left로 초기화합니다.
- curr이 NULL이 아닌 동안 반복합니다.
- node의 children 벡터 끝에 decode(curr)의 결과를 추가합니다.
- curr을 curr의 right로 갱신합니다.
- node를 반환합니다.
C++ 전체 구현 예제
아래 전체 구현 코드를 통해 동작 과정을 더 명확하게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = NULL;
right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Node {
public:
int val;
vector<Node*> children;
Node() {}
Node(int _val) {
val = _val;
}
Node(int _val, vector<Node*> _children) {
val = _val;
children = _children;
}
};
string n_ary_to_str(Node *root){
string ret = "";
if(root){
ret = ret + to_string(root->val);
if(root->children.size() > 0){
ret += "[";
for(Node* child : root->children){
ret += n_ary_to_str(child) + ", ";
}
ret += "]";
}
}
return ret;
}
class Codec {
public:
TreeNode* encode(Node* root) {
if(!root) return NULL;
TreeNode* node = new TreeNode(root->val);
if(root->children.size()){
node->left = encode(root->children[0]);
}
TreeNode* curr = node->left;
for(int i = 1; i < root->children.size(); i++){
curr->right = encode(root->children[i]);
curr = curr->right;
}
return node;
}
Node* decode(TreeNode* root) {
if(!root) return NULL;
Node* node = new Node(root->val);
TreeNode* curr = root->left;
while(curr){
node->children.push_back(decode(curr));
curr = curr->right;
}
return node;
}
};
main() {
Codec ob;
Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);
cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
cout << "Serialized Binary Tree: ";
TreeNode *root = ob.encode(&n1);
inord(root);
cout << endl;
Node *deser = ob.decode(root);
cout << "Deserialized Tree: " << n_ary_to_str(deser);
}
실행 결과 확인
입력
Node n5(5), n6(6); Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6); Node n2(2), n4(4); Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2); n1.children.push_back(&n4);
출력
Given Tree: 1[3[5, 6], 2, 4] Serialized Binary Tree: 5 6 3 2 4 1 Deserialized Tree: 1[3[5, 6], 2, 4]
동작 원리와 복잡도 분석
위 출력에서 볼 수 있듯이, 중위 순회(inorder traversal) 결과 5 6 3 2 4 1은 원래 트리의 구조 정보를 그대로 담고 있습니다. 루트 1의 첫 번째 자식 3이 왼쪽 서브트리로 내려가고, 3의 자식들인 5와 6이 오른쪽 형제 사슬로 연결되며, 나머지 자식 2와 4도 같은 방식으로 배치됩니다.
- 시간 복잡도: 인코딩과 디코딩 모두 모든 노드를 정확히 한 번씩 방문하므로 O(n)입니다.
- 공간 복잡도: 재귀 호출 스택과 새로 생성되는 노드 때문에 최악의 경우 O(n)입니다.
이처럼 왼쪽 자식-오른쪽 형제 표현법을 사용하면 N-ary 트리와 이진 트리 사이의 변환을 손실 없이, 그리고 선형 시간 안에 처리할 수 있습니다.