C++ में रूट-टू-लीफ पथों पर लंबाई < K वाले नोड्स को हटाना

एक ट्री दिया गया है, और हमें दिए गए k से कम लंबाई वाले पथ के लीफ नोड को हटाने की आवश्यकता है, उदाहरण के लिए।

इनपुट -

K = 4.

आउटपुट -

व्याख्या

पथ थे:
1. A -> B -> C -> E लंबाई = 4
2. A -> B -> C -> F लंबाई = 4
3. A -> B -> D लंबाई = 3
4. A -> G -> H लंबाई = 3
5. A -> B -> I लंबाई = 3

अब जैसा कि आप देख सकते हैं पथ 3, 4, 5 की लंबाई 3 है जो दिए गए k से कम है इसलिए हम इन पथों के लीफ नोड्स को हटा देते हैं यानी D, H, I।
अब पथ 4 और 5 के लिए जब H और I हटा दिए जाते हैं तो हम देखते हैं कि अब G भी पथ लंबाई 2 के साथ एक लीफ नोड है इसलिए हम फिर से नोड G को हटा देते हैं और यहां हमारा प्रोग्राम समाप्त होता है।

हम ट्री को पोस्ट-ऑर्डर फॉर्मेट में ट्रैवर्स करेंगे; फिर, हम एक रिकर्सिव फंक्शन बनाते हैं जो हमारे लीफ नोड्स को हटा देता है यदि उनकी पथ लंबाई K से कम है।

समाधान खोजने का दृष्टिकोण

इस दृष्टिकोण में, हम पोस्ट-ऑर्डर ट्रैवर्सल में ट्रैवर्स करते हैं; अब हम रिकर्सिवली उन लीफ नोड्स को हटाने का प्रयास करते हैं जिनकी पथ लंबाई k से कम है और इसी तरह जारी रखते हैं।

उदाहरण

उपरोक्त दृष्टिकोण के लिए C++ कोड

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

struct Node {
    // हमारे नोड की संरचना
    char data;
    Node *left, *right;
};

Node *newNode(int data) { // नया नोड डालना
    Node *node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

Node *trimmer(Node *root, int len, int k) {
    if (!root) // यदि रूट == NULL तो हम रिटर्न करते हैं
        return NULL;
    root->left = trimmer(root->left, len + 1, k); // बाएं चरण को ट्रैवर्स करना
    root->right = trimmer(root->right, len + 1, k); // दाएं चरण को ट्रैवर्स करना
    if (!root->left && !root->right && len < k) {
        delete root;
        return NULL;
    }
    return root;
}

Node *trim(Node *root, int k) {
    return trimmer(root, 1, k);
}

void printInorder(Node *root) {
    if (root) {
        printInorder(root->left);
        cout << root->data << " ";
        printInorder(root->right);
    }
}

int main() {
    int k = 4;
    Node *root = newNode('A');
    root->left = newNode('B');
    root->right = newNode('G');
    root->left->left = newNode('C');
    root->left->right = newNode('D');
    root->left->left->left = newNode('E');
    root->left->left->right = newNode('F');
    root->right->left = newNode('H');
    root->right->right = newNode('I');
    printInorder(root);
    cout << "\n";
    root = trim(root, k);
    printInorder(root);
    return 0;
}

आउटपुट

E C F B D A H G I E C F B A

उपरोक्त कोड की व्याख्या

इस कोड में, हम एक रिकर्सिव फंक्शन का उपयोग कर रहे हैं जो हमारे ट्री को ट्रैवर्स कर रहा है और बाएं और दाएं सबट्री के स्टैट्स को बनाए रख रहा है। अब हम एक लीफ नोड पर पहुंचते हैं; हम उस नोड तक पथ लंबाई की जांच करते हैं। यदि पथ लंबाई कम है, तो हम इस नोड को हटा देते हैं, और फिर हम NULL रिटर्न करते हैं; अन्यथा, कोड जारी रहता है।

निष्कर्ष

इस ट्यूटोरियल में, हम रिकर्सन का उपयोग करके रूट से लीफ पथों की लंबाई < K वाले नोड्स को हटाने की समस्या को हल करते हैं। हमने इस समस्या के लिए C++ प्रोग्राम और रिकर्सन को भी सीखा और इसे हल करने के पूर्ण दृष्टिकोण को भी। हम इसी प्रोग्राम को C, Java, Python और अन्य भाषाओं में लिख सकते हैं। आशा है कि आपको यह ट्यूटोरियल मददगार लगा होगा।