Computer >> कंप्यूटर >  >> प्रोग्रामिंग >> C++

सी ++ में प्रत्येक नोड में अगला दायां पॉइंटर्स पॉप्युलेट करना

मान लीजिए कि हमारे पास एक पूर्ण बाइनरी ट्री है, जहां प्रत्येक नोड में निम्नलिखित फ़ील्ड हैं:(डेटा, लेफ्ट, राइट, नेक्स्ट), लेफ्ट लेफ्ट सबट्री को इंगित करेगा, राइट सबट्री को इंगित करेगा, और अगला पॉइंटर अगले नोड को इंगित करेगा। . यदि दाहिने हाथ में कोई नोड नहीं है, तो वह शून्य होगा। तो शुरू में प्रत्येक अगला सूचक शून्य पर सेट है, हमें लिंक बनाना होगा। मान लीजिए कि पेड़ पहले वाले जैसा है, इसे अगले नोड में बदल दिया जाएगा -

सी ++ में प्रत्येक नोड में अगला दायां पॉइंटर्स पॉप्युलेट करना


सी ++ में प्रत्येक नोड में अगला दायां पॉइंटर्स पॉप्युलेट करना

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

  • पूर्व सेट करें:=रूट, अगला प्री:=नल और पिछला:=शून्य
  • जबकि प्री शून्य नहीं है
    • जबकि प्री शून्य नहीं है
      • अगर प्री का बायां हिस्सा खाली नहीं है
        • पिछला के आगे सेट करें:=पूर्व के बाएँ, जब पिछला रिक्त न हो, अन्यथा अगलाPre:=पूर्व के बाएँ
        • पिछला :=पूर्व के बाएँ
      • अगर प्री का राइट अशक्त नहीं है
        • पिछला के आगे सेट करें:=पूर्व का दायां, जब पिछला शून्य न हो, अन्यथा अगला प्री:=पूर्व का दायां
        • पिछला :=पूर्व का अधिकार
    • पूर्व:=अगलापूर्व
    • अगला प्री को शून्य के रूप में और पिछले को शून्य के रूप में सेट करें
  • वापसी शून्य

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

उदाहरण

#include <bits/stdc++.h>
#include <stack>
using namespace std;
class Node {
public:
   int val;
   Node* left;
   Node* right;
   Node* next;
   Node() {}
   Node(int _val, Node* _left, Node* _right) {
      val = _val;
      left = _left;
      right = _right;
      next = NULL;
   }
};
class Solution {
public:
   Node* connect(Node* root) {
      Node* pre = root;
      Node* nextPre = NULL;
      Node* prev = NULL;
      while(pre){
         while(pre){
            //cout << pre->val << endl;
            if(pre->left){
               if(prev){
                  prev->next = pre->left;
               }else{
                  nextPre = pre->left;
               }
               prev = pre->left;
            }
            if(pre->right){
               if(prev){
                  prev->next = pre->right;
               }else{
                  nextPre = pre->right;
               }
               prev = pre->right;
            }
            pre = pre->next;
         }
         //cout << "*" << endl;
         pre = nextPre;
         nextPre = NULL;
         prev = NULL;
      }
      return root;
   }
};
void printTree(Node* root) {
   cout << "[";
   if (root == NULL) return;
   queue<Node*> q;
   Node *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->next)
         // q.push(curr->next);
         if(curr->left)
            q.push(curr->left);
            if(curr->right)
               q.push(curr->right);
               if(curr->val == 0){
                  cout << "null" << ", ";
               }else{
                  cout << curr->val << ", ";
                  if (curr->next == NULL) cout<<"#, ";
              }
      }
   }
   cout << "]"<<endl;
}
int main() {
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
}

इनपुट

[1,2,3,4,5,6,7]
Node* root;
Node nodeFour(4, NULL, NULL);
Node nodeFive(5, NULL, NULL );
Node nodeSeven(7, NULL, NULL);
Node nodeSix(6, NULL, NULL);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,&nodeSix,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);

आउटपुट

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

  1. C++ में प्रत्येक नोड II में नेक्स्ट राइट पॉइंटर्स को पॉप्युलेट करना

    मान लीजिए कि हमारे पास एक बाइनरी ट्री है, जहां प्रत्येक नोड में निम्नलिखित फ़ील्ड हैं:(डेटा, लेफ्ट, राइट, नेक्स्ट), लेफ्ट लेफ्ट सबट्री को इंगित करेगा, राइट सबट्री को इंगित करेगा, और अगला पॉइंटर अगले नोड को इंगित करेगा। यदि दाहिने हाथ में कोई नोड नहीं है, तो वह शून्य होगा। तो शुरू में प्रत्येक अगला स

  1. C++ में लिंक की गई सूची में सबसे बड़े मान दाईं ओर के नोड के लिए पॉइंट आर्बिट पॉइंटर

    इस समस्या में, हमें एक मूल्य, लिंक सूचक और एक मनमाना सूचक के साथ एक लिंक्ड सूची दी जाती है। हमारा काम सबसे बड़ा मान इंगित करने के लिए मनमाना सूचक बिंदु बनाना है जो लिंक की गई सूची में इसके दाईं ओर है। समस्या को समझने के लिए एक उदाहरण लेते हैं, यहां, हम लिंक की गई सूची के निम्नलिखित मनमाने संकेत

  1. सी ++ में सभी नोड्स के लिए इनऑर्डर उत्तराधिकारी को पॉप्युलेट करें

    इस समस्या में हमें एक पेड़ दिया जाता है। संरचना में अगला सूचक होता है। हमारा काम इस पॉइंटर को इनऑर्डर सक्सेसर . के साथ पॉप्युलेट करना है नोड का। struct node {    int value;    struct node* left;    struct node* right;    struct node* next; } अगले सभी पॉइंटर क