C++ এ প্রতিটি নোডে পরবর্তী ডান পয়েন্টার পপুলেট করা হচ্ছে

ধরুন আমাদের একটি সম্পূর্ণ বাইনারি ট্রি আছে, যেখানে প্রতিটি নোডের নিম্নলিখিত ক্ষেত্র রয়েছে:(ডেটা, বাম, ডান, পরবর্তী), বামটি বাম সাবট্রিকে নির্দেশ করবে, ডানটি ডান সাবট্রিকে নির্দেশ করবে এবং পরবর্তী পয়েন্টারটি পরবর্তী নোডের দিকে নির্দেশ করবে . যদি ডান দিকে কোন নোড না থাকে, তাহলে সেটি শূন্য হবে। তাই প্রাথমিকভাবে প্রতিটি পরবর্তী পয়েন্টার নাল সেট করা হয়, আমাদের লিঙ্কগুলি তৈরি করতে হবে। ধরুন গাছটি প্রথমটির মতো, এটি পরবর্তী নোডে −

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• সেট pre :=root, nextPre :=null এবং prev :=null
• যদিও pre null নয়
  • যদিও pre null নয়
    • যদি pre-এর বাম অংশ null না হয়
      • prev এর পরের সেট করুন :=pre এর বাম, যখন prev নাল না হয়, অন্যথায় nextPre :=pre এর বাম
      • পূর্ববর্তী :=পূর্বের বাম
    • যদি pre-এর রাইট শূন্য না হয়
      • পূর্ববর্তীর পরের সেট করুন :=পূর্বের ডানদিকে, যখন পূর্ববর্তী শূন্য হয় না, অন্যথায় NextPre :=পূর্বের ডানদিকে
      • পূর্ববর্তী :=পূর্বের অধিকার
  • pre :=nextPre
  • nextPre কে null এবং prev কে 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){
            //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, #, ]