इस समस्या में, हमें एक बाइनरी ट्री BT और एक कुंजी मान दिया जाता है। हमारा कार्य दी गई कुंजी का अगला दायां नोड ढूंढना है।
बाइनरी ट्री डेटा स्टोरेज उद्देश्यों के लिए उपयोग की जाने वाली एक विशेष डेटा संरचना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
key = 4
आउटपुट
5
व्याख्या
नोड 4 के बगल में स्थित तत्व 5 है।
समाधान दृष्टिकोण
इस समस्या का एक सरल समाधान लेवल ऑर्डर ट्रैवर्सल का उपयोग करके बाइनरी ट्री को पार करना है। और दी गई कुंजी मान के लिए, हम जांचेंगे कि क्या ट्रैवर्सल में उसी लेवल पर नोड के बगल में कोई नोड मौजूद है। यदि हां, तो अगला नोड वापस करें, अन्यथा NULL वापस करें।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> #include <queue> using namespace std; struct node { struct node *left, *right; int key; }; node* newNode(int key) { node *temp = new node; temp->key = key; temp->left = temp->right = NULL; return temp; } node* findNextRightNodeBT(node *root, int k) { if (root == NULL) return 0; queue<node *> nodeVal; queue<int> nodeLevel; int level = 0; nodeVal.push(root); nodeLevel.push(level); while (nodeVal.size()) { node *node = nodeVal.front(); level = nodeLevel.front(); nodeVal.pop(); nodeLevel.pop(); if (node->key == k) { if (nodeLevel.size() == 0 || nodeLevel.front() != level) return NULL; return nodeVal.front(); } if (node->left != NULL) { nodeVal.push(node->left); nodeLevel.push(level+1); } if (node->right != NULL) { nodeVal.push(node->right); nodeLevel.push(level+1); } } return NULL; } int main() { node *root = newNode(1); root->left = newNode(2); root->right = newNode(3); root->left->left = newNode(4); root->left->right = newNode(5); root->right->left = newNode(6); int key = 4; cout<<"The next right node of the node "<<key<<" is "; node *nextNode = findNextRightNodeBT(root, key); if(nextNode != NULL) cout<<nextNode->key; else cout<<"not available"; return 0; }आउटपुट
The next right node of the node 4 is 5
