C++で二分木を簡潔にエンコード・デコードする方法

二分木の簡潔なエンコーディングとは

ここに一つの二分木があるとします。ご存知の通り、二分木の簡潔なエンコーディング（succinct encoding）とは、理論上の最低限に近い記憶領域で木の構造を表現できる手法です。構造的に異なる「n個のノードを持つ二分木」の総数は、n番目のカタラン数（Catalan number）によって表されます。nが大きくなると、この数はおよそ4^nに近づくため、エンコードには最低でも log₂(4^n) = 2n ビットが必要になります。したがって、簡潔な二分木は 2n + O(n) ビット程度で表現できることになります。

たとえば、次のような二分木が入力として与えられた場合を考えます。

このとき、出力は次のようになります。

エンコード結果：

• 構造リスト（Structure List）：1 1 1 0 0 1 0 0 1 0 1 0 0
• データリスト（Data List）：10 20 40 50 30 70

デコード結果：元の二分木がそのまま復元されます。

アルゴリズムの手順

この問題を解くために、以下の手順に従います。ポイントは、木を先行順（preorder）で走査しながら、「ノードが存在するかどうか」を1ビットずつ記録していくことです。

• Encode() 関数を定義します。引数は root、struc というリスト、data というリストです。
  • root が NULL の場合は、struc の末尾に 0 を挿入して return します。
• struc の末尾に 1 を挿入します。
• data の末尾に root の値を挿入します。
• Encode(root の左部分木, struc, data) を再帰呼び出しします。
• Encode(root の右部分木, struc, data) を再帰呼び出しします。
• Decode() 関数を定義します。引数は struc というリスト、data というリストです。
  • struc のサイズが 0 以下の場合は NULL を返します。
• b := struc の先頭要素を取得します。
• struc から先頭要素を削除します。
• b が 1 の場合は以下を行います。
  • key := data の先頭要素を取得します。
  • data から先頭要素を削除します。
  • key を持つ新しいノードを作成し、root とします。
  • root の左の子 := Decode(struc, data)
  • root の右の子 := Decode(struc, data)
  • root を返します。
• b が 0 の場合は NULL を返します。

このように、構造リストの「1」はノードの存在を、「0」は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; // 構造リスト用イテレータ
    for(si = struc.begin(); si != struc.end(); ++si)
    cout << *si << " ";
    cout << "\nData List\n";
    list<int>::iterator di; // データリスト用イテレータ
    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

出力結果から、エンコードされた木を Decode() 関数で復元すると、元の木とまったく同じ先行順走査結果が得られることが確認できます。この手法は、木構造をファイルやネットワーク越しに保存・転送する際など、メモリ効率が求められる場面で特に有効です。