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

C++ में डायनामिक प्रोग्रामिंग द्वारा बाइनरी ट्री में असन्निकट नोड्स का अधिकतम योग


बाइनरी ट्री में असन्निकट नोड्स का अधिकतम योग खोजने के लिए डायनामिक प्रोग्रामिंग (ट्री DP) दृष्टिकोण।

दो DP सरणियाँ: dp1[node] = नोड शामिल करने पर अधिकतम योग, dp2[node] = नोड बाहर करने पर अधिकतम योग।

उदाहरण: ट्री मान {10,5,11,6,8} के लिए अधिकतम योग 25।

C++ कार्यान्वयन

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

void dfs(int node, int parent, int dp1[], int dp2[], list* adj, int tree[]) {
    int sum1 = 0, sum2 = 0;
    for (auto i = adj[node].begin(); i != adj[node].end(); ++i) {
        if (*i == parent) continue;
        dfs(*i, node, dp1, dp2, adj, tree);
        sum1 += dp2[*i];
        sum2 += max(dp1[*i], dp2[*i]);
    }
    dp1[node] = tree[node] + sum1;
    dp2[node] = sum2;
}

int main() {
    int n = 5;
    list* adj = new list[n + 1];
    adj[1].push_back(2); adj[2].push_back(1);
    adj[1].push_back(3); adj[3].push_back(1);
    adj[2].push_back(4); adj[4].push_back(2);
    adj[2].push_back(5); adj[5].push_back(2);
    int tree[n + 1] = {0, 10, 5, 11, 6, 8};
    int dp1[n + 1], dp2[n + 1];
    memset(dp1, 0, sizeof dp1);
    memset(dp2, 0, sizeof dp2);
    dfs(1, 1, dp1, dp2, adj, tree);
    cout << "Maximum sum: " << max(dp1[1], dp2[1]) << endl;
    return 0;
}

आउटपुट

Maximum sum: 25
  1. C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य एक प्रोग्राम बनाना है जो C++ में बाइनरी ट्री में अधिकतम स्पाइरल सम ढूंढेगा।बाइनरी ट्री का स्पाइरल सम  बाइनरी ट्री के स्पाइरल ट्रैवर्सल में मिलने वाले नोड्स का योग है।ट्री के स्पाइरल ट्रैवर्सल में, नोड्स को रूट से लीफ नोड तक ट्रैवर्स कि

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज

  1. C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ प्रिंट करना

    हमें एक बाइनरी ट्री दिया गया है जिसके नोड्स विशिष्ट हैं और उस बाइनरी ट्री के दो नोड्स दिए गए हैं जिनके बीच का पथ हम प्रिंट करना चाहते हैं। उदाहरण के लिए - हम नोड 140 से 211 के बीच का पथ प्रिंट करना चाहते हैं तो इसका आउटपुट होना चाहिए - Output: 140->3->10->211 विचार यह है कि रूट नोड्स से दो