Succinct Encoding ของ Binary Tree ใน C++

แนวคิด

Succinct Encoding ของ Binary Tree ใช้พื้นที่ใกล้เคียงกับ theoretical minimum จำนวน binary tree โครงสร้างต่างกัน n โหนด = Catalan number นำไปสู่ ~2n bits สำหรับโครงสร้าง + O(n) bits สำหรับข้อมูล

วิธีการ Encoding

Preorder traversal: - โหนดมีอยู่ → เขียน '1' ใน structure list, เขียน value ใน data list, แล้ว recurse left, right - โหนดเป็น NULL → เขียน '0' ใน structure list

วิธีการ Decoding

อ่าน structure list: - '0' → return NULL - '1' → อ่านค่าจาก data list สร้างโหนด, decode left, decode right

ตัวอย่างโค้ด 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){ ... }

int 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);
    
    list<bool> struc;
    list<int> data;
    Encode(root, struc, data);
    
    cout << "Structure List\n";
    for(bool b : struc) cout << b << " ";
    cout << "\nData List\n";
    for(int v : data) cout << v << " ";
    
    TreeNode *newroot = Decode(struc, data);
    preorder_trav(newroot);
}

ผลลัพธ์

Structure List: 1 1 1 0 0 1 0 0 1 0 1 0 0
Data List: 10 20 40 50 30 70