इस समस्या में, हमें एक बाइनरी ट्री और एक पूर्णांक N दिया जाता है। कार्य बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल में n-वां नोड ढूंढना है।
एक बाइनरी ट्री में एक विशेष शर्त होती है कि प्रत्येक नोड के अधिकतम दो बच्चे हो सकते हैं।
ट्रैवर्सल एक प्रक्रिया है जो ट्री के सभी नोड्स को विजिट करती है और उनके मान भी प्रिंट कर सकती है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
N = 6
आउटपुट
6
व्याख्या
ट्री का प्री ऑर्डर ट्रैवर्सल : 1, 2, 4, 5, 3, 6, 7
समाधान दृष्टिकोण
विचार बाइनरी ट्री के प्री-ऑर्डर ट्रैवर्सल का उपयोग करना है जो पुनरावर्ती कॉल का उपयोग करके किया जाता है। प्रत्येक कॉल में हम रूट नोड को विजिट करेंगे फिर बाएं सबट्री के लिए preOrder() कॉल करेंगे और फिर preOrder() कॉल करेंगे। इस ट्रैवर्सल के दौरान, हम नोड्स की संख्या गिनेंगे और उस नोड को प्रिंट करेंगे जिसके लिए गिनती N है।
हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,
उदाहरण
#include <iostream> using namespace std; struct Node { int data; Node *left, *right; }; struct Node* createNode(int item){ Node* temp = new Node; temp->data = item; temp->left = NULL; temp->right = NULL; return temp; } void findPreOrderTraversalRec(struct Node* root, int N){ static int nodeCount = 0; if (root == NULL) return; if (nodeCount <= N) { nodeCount++; if (nodeCount == N) cout << root->data; findPreOrderTraversalRec(root->left, N); findPreOrderTraversalRec(root->right, N); } } int main() { struct Node* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7); int N = 6; cout<<N<<"th node in preorder traversal is "; findPreOrderTraversalRec(root, N); return 0; }आउटपुट
6th node in preorder traversal is 6
