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

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

तो, यदि इनपुट इस तरह है

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

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

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

• यदि root मान्य है, तो −

  • null लौटाएं

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

• यदि root के बच्चों का आकार 0 नहीं है, तो −

  • node का left := encode(root के children[0])

• curr = node का left

• i := 1 से आरंभ करें, जब i, root के बच्चों के आकार से कम, अद्यतन करें (i को 1 से बढ़ाएं), करें −

  • node का right := encode(root के children[i])

  • curr := curr का right

• node लौटाएं

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

• यदि root मौजूद नहीं है, तो −

  • NULL लौटाएं

• node := root के val के साथ नया नोड

• curr := root का left

• जब तक curr शून्येतर है, करें −

  • decode(curr) को node के children के अंत में डालें

  • curr := curr का right

• node लौटाएं

उदाहरण 

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

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