एन-एरी ट्री को बाइनरी ट्री में सी ++ में एन्कोड करें

मान लीजिए हमारे पास एक एन-आरी पेड़ है। हमें उस पेड़ को एक बाइनरी में एन्कोड करना होगा। बाइनरी ट्री को एन-एरी ट्री में डीसेरिएलाइज़ करने के लिए हमें डिसेरिएलाइज़र भी बनाना होगा।

तो, अगर इनपुट पसंद है

तो आउटपुट होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• एक फ़ंक्शन एन्कोड () को परिभाषित करें, यह रूट लेगा,

• यदि रूट मान्य है, तो -

  • वापसी शून्य

• नोड =जड़ के मान के साथ नया ट्री नोड

• यदि जड़ के बच्चों का आकार 0 नहीं है, तो -

  • नोड के बाईं ओर:=एनकोड (रूट के बच्चे [0])

• curr =नोड के बाईं ओर

• इनिशियलाइज़ i :=1 के लिए, जब i <रूट के बच्चों का आकार, अपडेट करें (i से 1 बढ़ाएँ), करें -

  • नोड का अधिकार:=एनकोड (रूट के बच्चे [i])

  • curr :=curr का अधिकार

• वापसी नोड

• एक फ़ंक्शन डिकोड () को परिभाषित करें, यह जड़ लेगा,

• यदि जड़ मौजूद नहीं है, तो -

  • वापसी शून्य

• नोड:=रूट के वैल के साथ नया नोड

• 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, ]