이진 트리가 있다고 가정합니다. 우리가 알고 있듯이 Binary Tree의 간결한 인코딩은 가능한 가장 낮은 공간에 가깝게 수행됩니다. n' 카탈로니아 수는 n개의 다른 노드를 가진 구조적으로 다른 이진 트리의 수로 지정됩니다. n이 크면 약 4n입니다. 따라서 인코딩하려면 최소 약 log2(4) n =2n 비트가 필요합니다. 따라서 간결한 이진 트리는 2n + O(n) 비트를 소비합니다.
따라서 입력이 다음과 같으면
그러면 출력은
인코딩 -
구조 목록 1 1 1 0 0 1 0 0 1 0 1 0 0
데이터 목록 10 20 40 50 30 70
Decoded - 위와 같은 트리입니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- Encode() 함수를 정의하면 루트가 생성되고 struc라는 목록, 데이터라는 목록,
- 루트가 NULL과 같으면 -
- 구조체 끝에 0 삽입
- 반환
- 구조체 끝에 1 삽입
- 데이터 끝에 루트 값 삽입
- 인코딩(루트, 구조체, 데이터의 왼쪽)
- 인코딩(루트, 구조체, 데이터의 오른쪽)
- Decode() 함수를 정의하면 struc라는 목록, data라는 목록이 필요합니다.
- struc의 크기가 <=0이면 -
- NULL 반환
- vb :=struc의 첫 번째 요소
- struc에서 앞 요소 삭제
- b가 1과 같으면 -
- key :=데이터의 첫 번째 요소
- 데이터에서 앞 요소 삭제
- 루트 =키가 있는 새 노드
- 루트 왼쪽 :=디코딩(struc, 데이터)
- 루트 오른쪽 :=디코딩(struc, 데이터)
- 루트 반환
- NULL 반환
예시(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 Encode(TreeNode *root, list<bool>&struc, list<int>&data){
if(root == NULL){
struc.push_back(0);
return;
}
struc.push_back(1);
data.push_back(root->val);
Encode(root->left, struc, data);
Encode(root->right, struc, data);
}
TreeNode *Decode(list<bool>&struc, list<int>&data){
if(struc.size() <= 0)
return NULL;
bool b = struc.front();
struc.pop_front();
if(b == 1){
int key = data.front();
data.pop_front();
TreeNode *root = new TreeNode(key);
root->left = Decode(struc, data);
root->right = Decode(struc, data);
return root;
}
return NULL;
}
void preorder_trav(TreeNode* root){
if(root){
cout << "key: "<< root->val;
if(root->left)
cout << " | left child: "<< root->left->val;
if(root->right)
cout << " | right child: "<< root->right->val;
cout << endl;
preorder_trav(root->left);
preorder_trav(root->right);
}
}
main() {
TreeNode *root = new TreeNode(10);
root->left = new TreeNode(20);
root->right = new TreeNode(30);
root->left->left = new TreeNode(40);
root->left->right = new TreeNode(50);
root->right->right = new TreeNode(70);
cout << "The Tree\n";
preorder_trav(root);
list<bool> struc;
list<int> data;
Encode(root, struc, data);
cout << "\nEncoded Tree\n";
cout << "Structure List\n";
list<bool>::iterator si; // Structure iterator
for(si = struc.begin(); si != struc.end(); ++si)
cout << *si << " ";
cout << "\nData List\n";
list<int>::iterator di; // Data iIterator
for(di = data.begin(); di != data.end(); ++di)
cout << *di << " ";
TreeNode *newroot = Decode(struc, data);
cout << "\n\nPreorder traversal of decoded tree\n";
preorder_trav(newroot);
} 입력
root->left = new TreeNode(20); root->right = new TreeNode(30); root->left->left = new TreeNode(40); root->left->right = new TreeNode(50); root->right->right = new TreeNode(70);
출력
The Tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70 Encoded Tree Structure List 1 1 1 0 0 1 0 0 1 0 1 0 0 Data List 10 20 40 50 30 70 Preorder traversal of decoded tree key: 10 | left child: 20 | right child: 30 key: 20 | left child: 40 | right child: 50 key: 40 key: 50 key: 30 | right child: 70 key: 70