สมมติว่าเรามีต้นไม้ไบนารี อย่างที่เราทราบดีว่าการเข้ารหัสแบบรวบรัดของ 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
ถอดรหัส – ต้นไม้ตามที่แสดงด้านบน
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- กำหนดฟังก์ชัน Encode() ซึ่งจะทำการรูท รายการชื่อ struc รายการชื่อ data
- ถ้ารูทเหมือนกับ NULL แล้ว −
- แทรก 0 ที่ส่วนท้ายของโครงสร้าง
- คืนสินค้า
- แทรก 1 ที่ส่วนท้ายของโครงสร้าง
- ใส่ค่าของรูทที่ส่วนท้ายของข้อมูล
- เข้ารหัส (ด้านซ้ายของรูท โครงสร้าง ข้อมูล)
- เข้ารหัส (ด้านขวาของรูท โครงสร้าง ข้อมูล)
- กำหนดฟังก์ชัน Decode() ซึ่งจะรับรายการชื่อ struc รายการชื่อ data
- ถ้าขนาดของ struc <=0 แล้ว −
- คืนค่า NULL
- vb :=องค์ประกอบแรกของ struc
- ลบองค์ประกอบด้านหน้าออกจาก struc
- ถ้า b เหมือนกับ 1 แล้ว −
- คีย์ :=องค์ประกอบแรกของข้อมูล
- ลบองค์ประกอบด้านหน้าออกจากข้อมูล
- root =โหนดใหม่พร้อมคีย์
- ด้านซ้ายของรูท :=ถอดรหัส (โครงสร้าง, ข้อมูล)
- ด้านขวาของรูท :=ถอดรหัส (โครงสร้าง ข้อมูล)
- คืนราก
- คืนค่า 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
