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


हल करने के चरण
- 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 का left null नहीं है
- pre := nextPre
- nextPre को null और prev को null सेट करें
- जब तक pre 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, #, ]