Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में बाइनरी ट्री में सभी K-सम पाथ प्रिंट करना


इस समस्या में, हमें एक बाइनरी ट्री और एक संख्या K दी गई है और हमें ट्री में उन सभी पाथ को प्रिंट करना है जिनमें पाथ के नोड्स का योग K के बराबर हो।

यहां, ट्री का पाथ ट्री के किसी भी नोड से शुरू हो सकता है और किसी भी नोड पर समाप्त हो सकता है। पाथ हमेशा रूट नोड से लीफ नोड की ओर होना चाहिए। ट्री के नोड्स के मान पॉजिटिव, नेगेटिव, या शून्य हो सकते हैं।

उदाहरण

C++ में बाइनरी ट्री में सभी K-सम पाथ प्रिंट करना

K = 5

आउटपुट -

1 3 1 3 2 1 4

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

हम पाथ के सभी नोड्स को वेक्टर में संग्रहीत करते हैं और योग मान की जांच करते हैं कि यह K के बराबर है या नहीं।

उदाहरण

एल्गोरिदम के कार्यान्वयन को दिखाने वाला प्रोग्राम:

#include <bits/stdc++.h> 
using namespace std; 

struct Node { 
    int data; 
    Node *left, *right; 
    Node(int x) { 
        data = x; 
        left = right = NULL; 
    } 
}; 

void printPath(const vector<int>& v, int i) { 
    for (int j = i; j < v.size(); j++) 
        cout << v[j] << "\t"; 
    cout << "\n"; 
} 

void findKSumPath(Node *root, vector<int>& path, int k) { 
    if (!root) 
        return; 
    path.push_back(root->data); 
    findKSumPath(root->left, path, k); 
    findKSumPath(root->right, path, k); 
    int f = 0; 
    for (int j = path.size() - 1; j >= 0; j--) { 
        f += path[j]; 
        if (f == k) 
            printPath(path, j); 
    } 
    path.pop_back(); 
} 

int main() { 
    Node *root = new Node(1); 
    root->left = new Node(3); 
    root->left->left = new Node(1); 
    root->left->right = new Node(2); 
    root->right = new Node(4); 
    root->right->right = new Node(7); 
    int k = 5; 
    cout << "Paths with sum " << k << " are :\n"; 
    vector<int> path; 
    findKSumPath(root, path, k); 
    return 0; 
}

आउटपुट

Paths with sum 5 are - 1 3 1 3 2 1 4

  1. C++ में बाइनरी ट्री में K लीफ वाले सभी नोड्स प्रिंट करना C++ में बाइनरी ट्री में K लीफ वाले सभी नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी ट्री और एक पूर्णांक K दिया गया है और हमें बाइनरी ट्री के उन सभी नोड्स को प्रिंट करना है जिनके चाइल्ड सबट्री में K लीफ हैं। बाइनरी ट्री बाइनरी ट्री एक विशेष ट्री है जिसके प्रत्येक नोड में अधिकतम दो नोड्स होते हैं (एक/दो/कोई नहीं)। लीफ नोड बाइनरी ट्री का लीफ नोड ट्री क

  1. C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी सर्च ट्री दी गई है और हमें उन सभी नोड्स को प्रिंट करना है जिनके मान विषम हैं। बाइनरी सर्च ट्री बाइनरी सर्च ट्री एक विशेष प्रकार का ट्री है जिसमें निम्नलिखित गुण होते हैं: बायां सबट्री हमेशा रूट नोड से छोटे मान रखता है। दायां सबट्री हमेशा रूट नोड से बड़े मान रखता है।

  1. C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना

    दिए गए बाइनरी ट्री में, कार्य 1 से n तक शुरू होने वाले प्रत्येक कुंजी से जुड़े लेवल को प्रिंट करना है जो एक नोड में संग्रहीत है। उपरोक्त ट्री में नोड्स हैं - 10 at level 1 3 and 211 at level 2 140, 162, 100 and 146 at level 3 दिए गए कुंजी के लिए प्रोग्राम को उस विशेष कुंजी का लेवल प्रिंट करना होगा।