Giả sử chúng ta có một cây nhị phân. Như chúng ta biết mã hóa ngắn gọn của Cây nhị phân thực hiện gần với không gian thấp nhất có thể. Số Catalan thứ n được chỉ định bởi số lượng cây nhị phân khác nhau về cấu trúc với n nút khác nhau. Nếu n lớn thì khoảng 4n; do đó, chúng tôi yêu cầu tối thiểu khoảng log2 (4) n =2n bit để mã hóa nó. Do đó, một cây nhị phân ngắn gọn sẽ sử dụng 2n + O (n) bit.
Vì vậy, nếu đầu vào giống như
thì đầu ra sẽ là
được mã hóa -
Danh sách cấu trúc 1 1 1 0 0 1 0 0 1 0 1 0 0
Danh sách dữ liệu 10 20 40 50 30 70
Đã giải mã - Cây như hình trên.
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- Xác định một hàm Encode (), hàm này sẽ bắt nguồn gốc, một danh sách có tên struc, một danh sách có tên dữ liệu,
- nếu gốc giống như NULL, thì -
- chèn 0 vào cuối struc
- trở lại
- chèn 1 vào cuối struc
- chèn giá trị gốc vào cuối dữ liệu
- Mã hóa (bên trái thư mục gốc, chuỗi ký tự, dữ liệu)
- Mã hóa (quyền root, struc, data)
- Xác định một hàm Decode (), điều này sẽ lấy một danh sách có tên struc, một danh sách có tên dữ liệu,
- nếu kích thước của struc <=0, thì -
- trả về NULL
- vb:=phần tử đầu tiên của struc
- xóa phần tử phía trước khỏi struc
- nếu b giống 1, thì -
- key:=phần tử đầu tiên của dữ liệu
- xóa phần tử phía trước khỏi dữ liệu
- root =nút mới có khóa
- left of root:=Decode (struc, data)
- right of root:=Decode (struc, data)
- trả về thư mục gốc
- trả về NULL
Ví dụ (C ++)
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
#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);
} Đầu vào
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);
Đầu ra
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