इस ट्यूटोरियल में, हम एक बाइनरी ट्री के रूट नोड से दिए गए बाइनरी ट्री में मौजूद अन्य सभी नोड्स के पथ को प्रिंट करने के लिए एक प्रोग्राम पर चर्चा करेंगे।
इस कार्यक्रम में, हमें एक संख्या N दी जाएगी, जो बाइनरी ट्री में 1 से N तक मौजूद तत्वों की संख्या को दर्शाती है; 1 बाइनरी ट्री का रूट नोड है। इसलिए, हमारा काम रूट नोड से बाइनरी ट्री में मौजूद विभिन्न अन्य तत्वों के लिए सभी संभावित रास्तों को प्रिंट करना है।
इस कार्यक्रम को हल करने के लिए, हम जानते हैं कि दिए गए नोड I के लिए, इसके बाएं बच्चे की गणना 2*i के रूप में की जा सकती है और इसके दाहिने बच्चे की गणना 2*i+1 के रूप में की जा सकती है। फिर हम उस विशेष तत्व के पथ को वेक्टर में संग्रहीत करने के लिए बैकट्रैकिंग का उपयोग कर सकते हैं और फिर सभी संभावित पथों को अंतिम रूप से प्रिंट कर सकते हैं।
उदाहरण
#include <iostream>
#include <vector>
using namespace std;
//calculating all the possible paths from the root node
void calc_allpath(vector<int> paths, int nth_node, int kth_node){
if (kth_node > nth_node)
return;
paths.push_back(kth_node);
for (int i = 0; i < paths.size(); i++)
cout << paths[i] << " ";
cout << endl;
calc_allpath(paths, nth_node, kth_node * 2);
calc_allpath(paths, nth_node, kth_node * 2 + 1);
}
//printing all the possible paths from the root node
void print_allpath(int nth_node){
vector<int> paths;
calc_allpath(paths, nth_node, 1);
}
int main(){
int nth_node = 9;
print_allpath(nth_node);
return 0;
} आउटपुट
1 1 2 1 2 4 1 2 4 8 1 2 4 9 1 2 5 1 3 1 3 6 1 3 7