C++ में पेड़ में एक पंक्ति जोड़ें

मान लीजिए कि हमारे पास एक बाइनरी ट्री है, हमारे पास मूल्य v और गहराई d भी है, हमें दी गई गहराई d पर मान v के साथ नोड्स की एक पंक्ति जोड़नी है। रूट नोड 1 गहराई पर है। इस ऑपरेशन को करने के लिए हमें इस नियम का पालन करना होगा -

जैसा कि हम गहराई d जानते हैं, प्रत्येक मान्य ट्री नोड्स N के लिए गहराई d-1 में, हमें N के लेफ्ट सबट्री रूट और राइट सबट्री रूट के रूप में मान v के साथ दो ट्री नोड्स बनाने होंगे। और N का ओरिजिनल लेफ्ट सबट्री नए लेफ्ट सबट्री रूट का लेफ्ट सबट्री होगा, इसका ओरिजिनल राइट सबट्री नए राइट सबट्री रूट का राइट सबट्री होगा। जब गहराई d 1 हो, जिसका अर्थ है कि कोई गहराई d-1 बिल्कुल नहीं है, तो एक ट्री नोड बनाएं जिसका मान v है कि पूरे मूल पेड़ की नई जड़ है, और मूल पेड़ नई जड़ का बायां उपट्री है।

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

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

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

• यदि d 1 के समान है, तो -

  • अस्थायी =नया नोड मान v

    . के साथ

  • तापमान के बाएँ:=रूट

  • जड़:=अस्थायी

• अन्यथा

  • जोड़े के एक स्टैक को परिभाषित करें जिसे सेंट कहा जाता है

  • सेंट में {रूट, 2} डालें

  • एलवीएल:=0

  • एक जोड़ी अस्थायी परिभाषित करें

  • जबकि (सेंट खाली नहीं है), करें -

    • अस्थायी:=सेंट का शीर्ष तत्व

    • सेंट से तत्व हटाएं

    • lvl:=अस्थायी का दूसरा तत्व

    • नोड:=अस्थायी का पहला तत्व

    • यदि lvl, d के समान है, तो -

      • temp1 =नया नोड मान v

        . के साथ

      • temp2 =नया नोड मान v

        . के साथ

      • temp1 के बाएँ:=नोड के बाएँ

      • temp2 का दायां:=नोड का दायां

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

      • नोड का दायां:=temp2

    • अन्यथा

      • यदि नोड का बायां भाग मान्य है, तो -

        • सेंट में {नोड के बाएं, lvl + 1} डालें

      • यदि नोड का अधिकार मान्य है, तो -

        • सेंट में {नोड का दायां, lvl + 1} डालें

• वापसी जड़

उदाहरण

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

#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 insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
void tree_level_trav(TreeNode*root){
   if (root == NULL) return;
      cout << "[";
   queue<TreeNode *> q;
   TreeNode *curr;
   q.push(root);
   q.push(NULL);
   while (q.size() > 1) {
      curr = q.front();
      q.pop();
      if (curr == NULL){
         q.push(NULL);
      }
      else {
         if(curr->left)
            q.push(curr->left);
         if(curr->right)
            q.push(curr->right);
         if(curr == NULL || curr->val == 0){
            cout << "null" << ", ";
         }
         else{
            cout << curr->val << ", ";
         }
      }
   }
   cout << "]"<<endl;
}
class Solution {
public:
   TreeNode* addOneRow(TreeNode* root, int v, int d) {
      if (d == 1) {
         TreeNode* temp = new TreeNode(v);
         temp->left = root;
         root = temp;
      }
      else {
         stack<pair<TreeNode*, int> > st;
         st.push({ root, 2 });
         int lvl = 0;
         pair<TreeNode*, int> temp;
         TreeNode* node;
         while (!st.empty()) {
            temp = st.top();
            st.pop();
            lvl = temp.second;
            node = temp.first;
            if (lvl == d) {
               TreeNode* temp1 = new TreeNode(v);
               TreeNode* temp2 = new TreeNode(v);
               temp1->left = node->left;
               temp2->right = node->right;
               node->left = temp1;
               node->right = temp2;
            }
            else {
               if (node->left && node->left->val != 0) {
                  st.push({ node->left, lvl + 1 });
               }
               if (node->right && node->right->val != 0) {
                  st.push({ node->right, lvl + 1 });
               }
            }
         }
      }
      return root;
   }
};
main(){
   Solution ob;
   vector<int> v = {4,2,6,3,1,5};
   TreeNode *root = make_tree(v);
   tree_level_trav(ob.addOneRow(root, 1, 2));
}

इनपुट

{4,2,6,3,1,5}, 1, 2

आउटपुट

[4, 1, 1, 2, 6, 3, 1, 5, ]