N-aryツリーをC++でバイナリツリーにエンコードする

N-aryツリーがあるとします。そのツリーを1つのバイナリにエンコードする必要があります。また、バイナリツリーをN-aryツリーに逆シリアル化するためにデシリアライザーを作成する必要があります。

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

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

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

• 関数encode（）を定義します。これはルートになります

• ルートが有効な場合、-

  • nullを返す

• node=ルートの値を持つ新しいツリーノード

• ルートの子のサイズが0でない場合、-

  • ノードの左側：=encode（ルートのchildren [0]）

• curr=ノードの左側

• 初期化i：=1の場合、i <ルートの子のサイズの場合、更新（iを1増やします）、実行-

  • ノードの右側：=encode（ルートのchildren [i]）

  • curr：=currの権利

• リターンノード

• 関数decode（）を定義します。これはルートになります

• ルートが存在しない場合、-

  • NULLを返す

• node：=ルートの値を持つ新しいノード

• curr：=ルートの左側

• currがゼロ以外の場合、実行-

  • ノードの子の最後にdecode（curr）を挿入します

  • curr：=currの権利

• リターンノード

例

理解を深めるために、次の実装を見てみましょう-

#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 inord(TreeNode *root) {
   if (root != NULL) {
      inord(root->left);
      cout << root->val << " ";
      inord(root->right);
   }
}
class Node {
   public:
   int val;
   vector<Node*> children;
   Node() {}
   Node(int _val) {
      val = _val;
   }
   Node(int _val, vector<Node*> _children) {
      val = _val;
      children = _children;
   }
};
string n_ary_to_str(Node *root){
   string ret = "";
   if(root){
      ret = ret + to_string(root->val);
      if(root->children.size() > 0){
         ret += "[";
         for(Node* child : root->children){
            ret += n_ary_to_str(child) + ", ";
         }
         ret += "]";
      }
   }
   return ret;
}
class Codec {
public:
   TreeNode* encode(Node* root) {
      if(!root) return NULL;
         TreeNode* node = new TreeNode(root->val);
         if(root->children.size()){
            node->left = encode(root->children[0]);
         }
         TreeNode* curr = node->left;
         for(int i = 1; i < root->children.size(); i++){
            curr->right = encode(root->children[i]);
            curr = curr->right;
         }
         return node;
      }
      Node* decode(TreeNode* root) {
         if(!root) return NULL;
            Node* node = new Node(root->val);
         TreeNode* curr = root->left;
         while(curr){
            node->children.push_back(decode(curr));
            curr = curr->right;
         }
      return node;
   }
};
main() {
   Codec ob;
   Node n5(5), n6(6);
   Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
   Node n2(2), n4(4);
   Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
   n1.children.push_back(&n4);
   cout << "Given Tree: " << n_ary_to_str(&n1) << endl;
   cout << "Serialized Binary Tree: ";
   TreeNode *root = ob.encode(&n1);
   inord(root);
   cout << endl;
   Node *deser = ob.decode(root);
   cout << "Deserialized Tree: " << n_ary_to_str(deser);
}

入力

Node n5(5), n6(6);
Node n3(3); n3.children.push_back(&n5); n3.children.push_back(&n6);
Node n2(2), n4(4);
Node n1(1); n1.children.push_back(&n3); n1.children.push_back(&n2);
n1.children.push_back(&n4);

出力

Given Tree: 1[3[5, 6, ], 2, 4, ]
Serialized Binary Tree: 5 6 3 2 4 1
Deserialized Tree: 1[3[5, 6, ], 2, 4, ]