मान लीजिए कि हमारे पास एक बाइनरी ट्री है, जहां प्रत्येक नोड में निम्नलिखित फ़ील्ड हैं:(डेटा, लेफ्ट, राइट, नेक्स्ट), लेफ्ट लेफ्ट सबट्री को इंगित करेगा, राइट सबट्री को इंगित करेगा, और अगला पॉइंटर अगले नोड को इंगित करेगा। यदि दाहिने हाथ में कोई नोड नहीं है, तो वह शून्य होगा। तो शुरू में प्रत्येक अगला सूचक शून्य पर सेट है, हमें लिंक बनाना होगा। मान लीजिए कि पेड़ पहले वाले जैसा है, इसे अगले नोड में बदल दिया जाएगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- पूर्व सेट करें:=रूट, अगला प्री:=नल और पिछला:=शून्य
- जबकि प्री शून्य नहीं है
- जबकि प्री शून्य नहीं है
- अगर प्री का बायां हिस्सा खाली नहीं है
- पिछला के आगे सेट करें:=पूर्व के बाएँ, जब पिछला रिक्त न हो, अन्यथा अगलाPre:=पूर्व के बाएँ
- पिछला :=पूर्व के बाएँ
- अगर प्री का राइट अशक्त नहीं है
- पिछला के आगे सेट करें:=पूर्व का दायां, जब पिछला शून्य न हो, अन्यथा अगला प्री:=पूर्व का दायां
- पिछला :=पूर्व का अधिकार
- अगर प्री का बायां हिस्सा खाली नहीं है
- पूर्व:=अगलापूर्व
- अगला प्री को शून्य के रूप में और पिछले को शून्य के रूप में सेट करें
- जबकि प्री शून्य नहीं है
- वापसी शून्य
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include <bits/stdc++.h>
#include <stack>
using namespace std;
class Node {
public:
int val;
Node* left;
Node* right;
Node* next;
Node() : val(0), left(NULL), right(NULL), next(NULL) {}
Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
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);
Node nodeFive(5);
Node nodeSeven(7);
Node nodeTwo(2,&nodeFour,&nodeFive);
Node nodeThree(3,NULL,&nodeSeven);
Node nodeOne(1,&nodeTwo,&nodeThree);
root = &nodeOne;
Solution ob;
root = ob.connect(root);
printTree(root);
} इनपुट
[1,2,3,4,5,null,7] Node* root; Node nodeFour(4); Node nodeFive(5); Node nodeSeven(7); Node nodeTwo(2,&nodeFour,&nodeFive); Node nodeThree(3,NULL,&nodeSeven); Node nodeOne(1,&nodeTwo,&nodeThree); root = &nodeOne;
आउटपुट
[1, #, 2, 3, #, 4, 5, 7, #, ]