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

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


मान लीजिए हमारे पास एक पूर्ण बाइनरी ट्री है, जहां प्रत्येक नोड में निम्नलिखित फ़ील्ड हैं: (data, left, right, next), left बाएं उपट्री की ओर इंगित करेगा, right दाएं उपट्री की ओर इंगित करेगा, और next पॉइंटर अगले नोड की ओर इंगित करेगा। यदि दाएं हाथ की तरफ कोई नोड नहीं है, तो वह null होगा। इसलिए प्रारंभ में प्रत्येक next पॉइंटर null पर सेट है, हमें लिंक बनाने हैं।

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


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

हल करने के चरण

  • pre := root, nextPre := null और prev := null सेट करें
  • जब तक pre null नहीं है
    • जब तक pre null नहीं है
      • यदि pre का left null नहीं है
        • prev के next को pre के left पर सेट करें, जब prev null नहीं है, अन्यथा nextPre := pre का left
        • prev := pre का left
      • यदि pre का right null नहीं है
        • prev के next को pre के right पर सेट करें, जब prev null नहीं है, अन्यथा nextPre := pre का right
        • prev := pre का right
    • pre := nextPre
    • nextPre को null और prev को null सेट करें
  • null वापस करें

उदाहरण

#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){             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;          }          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->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]

आउटपुट

[1, #, 2, 3, #, 4, 5, 6, 7, #, ]
  1. C++ में प्रत्येक नोड II में अगले राइट पॉइंटर्स भरना C++ में प्रत्येक नोड II में अगले राइट पॉइंटर्स भरना

    मान लीजिए हमारे पास एक बाइनरी ट्री है, जहां प्रत्येक नोड में निम्नलिखित फ़ील्ड हैं: (data, left, right, next), left बाएं उपट्री की ओर इंगित करेगा, right दाएं उपट्री की ओर इंगित करेगा, और next पॉइंटर अगले नोड की ओर इंगित करेगा। यदि दाएं हाथ की तरफ कोई नोड नहीं है, तो वह null होगा। इसलिए प्रारंभ में प

  1. C++ में लिंक्ड लिस्ट में मनमाना पॉइंटर को दाईं ओर के सबसे बड़े मान वाले नोड पर इंगित करना C++ में लिंक्ड लिस्ट में मनमाना पॉइंटर को दाईं ओर के सबसे बड़े मान वाले नोड पर इंगित करना

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

  1. C++ में सभी नोड्स के लिए इनऑर्डर सक्सेसर भरना C++ में सभी नोड्स के लिए इनऑर्डर सक्सेसर भरना

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