C++ प्रोग्राम: पूर्ण बाइनरी ट्री में रूट से सभी नोड्स तक का पथ प्रिंट करना

इस ट्यूटोरियल में, हम बाइनरी ट्री के रूट नोड से दिए गए बाइनरी ट्री में मौजूद अन्य सभी नोड्स तक के पथ को प्रिंट करने के प्रोग्राम पर चर्चा करेंगे।

इस प्रोग्राम में, हमें एक संख्या N दी जाएगी, जो 1 से N तक बाइनरी ट्री में मौजूद तत्वों की संख्या को दर्शाती है; 1 बाइनरी ट्री का रूट नोड है। इसलिए, हमारा कार्य रूट नोड से बाइनरी ट्री में मौजूद विभिन्न अन्य तत्वों तक के सभी संभावित पथ प्रिंट करना है।

इस प्रोग्राम को हल करने के लिए, हम जानते हैं कि दिए गए नोड i के लिए, इसका बायां बच्चा 2*i के रूप में गणना की जा सकती है और इसका दायां बच्चा 2*i+1 के रूप में गणना की जा सकती है। हम फिर उस विशेष तत्व के पथ को एक वेक्टर में स्टोर करने के लिए बैकट्रैकिंग का उपयोग कर सकते हैं और फिर सभी संभावित पथ प्रिंट कर सकते हैं।

उदाहरण

#include <iostream>
#include <vector>
using namespace std;

// रूट नोड से सभी संभावित पथों की गणना करना
void calc_allpath(vector 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);
}

// रूट नोड से सभी संभावित पथ प्रिंट करना
void print_allpath(int nth_node) {
    vector paths;
    calc_allpath(paths, nth_node, 1);
}

int main() {
    int nth_node = 9;
    print_allpath(nth_node);
    return 0;
}

आउटपुट