Mã hóa gọn (Succinct Encoding) của cây nhị phân trong C++

Mã hóa gọn của cây nhị phân đạt gần giới hạn không gian lý thuyết (2n bit cho cấu trúc). Sử dụng Euler tour: ghi '1' khi vào nút, '0' khi ra (null). Dữ liệu nút lưu riêng theo thứ tự preorder.

Ví dụ: Cây gốc 10, con trái 20 (con 40,50), con phải 30 (con phải 70).

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

Ví dụ (C++)

#include<bits/stdc++.h>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){ val=data; left=right=NULL; }
};

void Encode(TreeNode* root, list<bool>& struc, list<int>& data){
    if(!root){ 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.empty()) return NULL;
    bool b=struc.front(); struc.pop_front();
    if(b){
        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: "<<root->left->val;
        if(root->right) cout<<" | right: "<<root->right->val;
        cout<<endl;
        preorder_trav(root->left); preorder_trav(root->right);
    }
}

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);
    cout<<"The Tree\n"; preorder_trav(root);
    list<bool> struc; list<int> data;
    Encode(root,struc,data);
    cout<<"\nEncoded Tree\nStructure List\n";
    for(bool b:struc) cout<<b<<" ";
    cout<<"\nData List\n";
    for(int d:data) cout<<d<<" ";
    TreeNode* newroot=Decode(struc,data);
    cout<<"\n\nDecoded tree preorder:\n"; preorder_trav(newroot);
}

Đầu ra

Structure List: 1 1 1 0 0 1 0 0 1 0 1 0 0
Data List: 10 20 40 50 30 70
Decoded tree khớp gốc.