सी ++ में एक बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल में एन-वें नोड खोजें

इस समस्या में, हमें एक बाइनरी ट्री और एक पूर्णांक N दिया जाता है। कार्य एक बाइनरी ट्री के प्रीऑर्डर ट्रैवर्सल में n-वें नोड को खोजना है।

बाइनरी ट्री की एक विशेष शर्त होती है कि प्रत्येक नोड में अधिकतम दो बच्चे हो सकते हैं।

ट्रैवर्सल एक पेड़ के सभी नोड्स पर जाने की एक प्रक्रिया है और उनके मूल्यों को भी प्रिंट कर सकता है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

N = 6

आउटपुट

6

स्पष्टीकरण

Pre order traversal of tree : 1, 2, 4, 5, 3, 6, 7

समाधान दृष्टिकोण

विचार बाइनरी ट्री के प्री-ऑर्डर ट्रैवर्सल का उपयोग करना है जो रिकर्सिव कॉल का उपयोग करके किया जाता है। प्रत्येक कॉल में हम रूट नोड पर जाएंगे, फिर पहले लेफ्ट सबट्री के लिए प्रीऑर्डर () को कॉल करेंगे और फिर प्रीऑर्डर () को कॉल करेंगे। इस ट्रैवर्सल के दौरान, हम नोड्स की संख्या की गणना करेंगे और उस नोड को प्रिंट करेंगे जिसके लिए गिनती एन है।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला कार्यक्रम,

उदाहरण

#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