C++での二分木の簡潔なエンコーディング

二分木があるとします。私たちが知っているように、バイナリツリーの簡潔なエンコーディングは可能な限り低いスペースに近いパフォーマンスを発揮します。 n番目のカタラン数は、n個の異なるノードを持つ構造的に異なる二分木の数によって指定されます。 nが大きい場合、これは約4nです。したがって、それをエンコードするには、log2（4）n=2nビット程度の最小値が必要です。したがって、簡潔な二分木は2n + O（n）ビットを消費します。

したがって、入力が次のような場合

その場合、出力は次のようになります

エンコードされた-

構造リスト111 0 0 1 0 0 1 0 1 0 0

データリスト102040 50 30 70

デコード済み-上記のツリー。

これを解決するには、次の手順に従います-

• 関数Encode（）を定義します。これにより、root、strucという名前のリスト、dataという名前のリストが取得されます。
• rootがNULLと同じ場合、-
  • 構造の最後に0を挿入
  • 戻る
• 構造の最後に1を挿入
• データの最後にrootの値を挿入
• エンコード（ルート、構造、データの左側）
• エンコード（ルート、構造、データの権利）
• 関数Decode（）を定義します。これにより、strucという名前のリスト、dataという名前のリストが取得されます。
• 構造のサイズが<=0の場合、-
  • NULLを返す
• vb：=strucの最初の要素
• 構造からフロント要素を削除する
• bが1と同じ場合、-
  • key：=データの最初の要素
  • データからフロント要素を削除する
  • root=キーを持つ新しいノード
  • ルートの左側：=Decode（struc、data）
  • ルートの権利：=Decode（struc、data）
  • ルートを返す
• 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