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

C++ में दिए गए नोड के सब-ट्री के सभी नोड्स का XOR


इस समस्या में, हमें एक n-ट्री दी गई है और कुछ क्वेरीज हैं जो ट्री के नोड्स हैं। हमारा कार्य दिए गए नोड द्वारा बने सब-ट्री के सभी नोड्स का XOR प्रिंट करना है।

आइए एक उदाहरण से समस्या को समझते हैं,

C++ में दिए गए नोड के सब-ट्री के सभी नोड्स का XOR

क्वेरीज - {1, 6, 5}

आउटपुट -

0 0 5

व्याख्या -

1^6^3^2^4^7^5
6^2^4
5

इस समस्या को हल करने के लिए, हम ट्री को एक बार पार करके सब-ट्री के सभी नोड्स का XOR गणना करेंगे और इसे संग्रहीत करेंगे। अब, हम चाइल्ड नोड्स के सब-ट्री के सभी नोड्स का XOR गणना करेंगे और फिर सभी दिए गए सब-ट्री के लिए गणना करेंगे। परिणामों को संग्रहीत करने से समय की बचत होती है।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,

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

vector<vector<int>> graph;
vector<int> values, xorValues;

int computeXorValues(int i, int prev) {
    int x = values[i];
    for (int j = 0; j < graph[i].size(); j++)
        if (graph[i][j] != prev) {
            x ^= computeXorValues(graph[i][j], i);
        }
    xorValues[i] = x;
    return x;
}

int solveQuerry(int u) {
    return xorValues[u];
}

int main() {
    int n = 7;
    graph.resize(n);
    xorValues.resize(n);
    
    graph[0].push_back(1);
    graph[0].push_back(2);
    graph[1].push_back(3);
    graph[1].push_back(4);
    graph[2].push_back(5);
    graph[2].push_back(6);
    
    values.push_back(1);
    values.push_back(2);
    values.push_back(3);
    values.push_back(4);
    values.push_back(5);
    values.push_back(6);
    values.push_back(7);
    
    computeXorValues(0, -1);
    
    int queries[] = {0, 2, 4, 6};
    int q = sizeof(queries) / sizeof(queries[0]);
    
    for (int i = 0; i < q; i++)
        cout << "Solution for querry " << (i+1) << ": " << solveQuerry(queries[i]) << endl;
    
    return 0;
}

आउटपुट

Solution for querry 1: 0
Solution for querry 2: 2
Solution for querry 3: 5
Solution for querry 4: 7
  1. C++ में बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ का XOR C++ में बाइनरी ट्री में किन्हीं दो नोड्स के बीच पथ का XOR

    इस समस्या में, हमें एक बाइनरी ट्री और बाइनरी ट्री के दो नोड्स दिए गए हैं। हमारा कार्य उन सभी नोड्स का XOR प्रिंट करना है जो दो नोड्स के बीच पथ में आते हैं। आइए एक उदाहरण से समस्या को समझते हैं, हमें 2 और 3 के बीच सभी नोड्स का XOR खोजने की आवश्यकता है। 2 से 3 तक का पथ, 2 → 6 → 1 → 3। हम 2^3^1^3 ख

  1. C++ में दिए गए नोड से दूरी K पर सभी नोड्स प्रिंट करना C++ में दिए गए नोड से दूरी K पर सभी नोड्स प्रिंट करना

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

  1. C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें C++ में दिए गए परफेक्ट बाइनरी ट्री के सभी नोड्स का योग ज्ञात करें

    मान लीजिए हमारे पास एक धनात्मक पूर्णांक L है, जो परफेक्ट बाइनरी ट्री में स्तरों की संख्या दर्शाता है। इस परफेक्ट बाइनरी ट्री में पत्ती नोड्स को 1 से n तक संख्या दी गई है। जहां n पत्ती नोड्स की संख्या है। पैरेंट नोड बच्चों का योग है। हमारा कार्य इस परफेक्ट बाइनरी ट्री के सभी नोड्स का योग प्रिंट करने