কম্পিউটার

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


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

রূপান্তরিত হবে

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


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

  1. C++ এ প্রদত্ত কী-এর পরবর্তী ডানদিকের নোড খুঁজুন

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

  3. C++ এ একটি লিঙ্ক করা তালিকায় আর্বিট পয়েন্টারকে সর্বাধিক মানের ডান পাশের নোডে নির্দেশ করুন

  4. C++-এ সমস্ত নোডের জন্য Inorder Successor পপুলেট করুন