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

C++ में सभी डुप्लिकेट सबट्री खोजें


मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह पता लगाना है कि ट्री में कुछ डुप्लिकेट सबट्री हैं या नहीं। मान लीजिए हमारे पास नीचे जैसा बाइनरी ट्री है:

C++ में सभी डुप्लिकेट सबट्री खोजें

आकार 2 के दो समान सबट्री हैं। प्रत्येक सबट्री में D, BD और BE भी डुप्लिकेट सबट्री हैं। हम इस समस्या को ट्री सीरियलाइज़ेशन और हैशिंग प्रक्रिया का उपयोग करके हल कर सकते हैं। हम सबट्री के इनऑर्डर ट्रैवर्सल को हैश टेबल में स्टोर करेंगे। खाली नोड्स के लिए ओपनिंग और क्लोजिंग पैरेंथेसिस डालेंगे।

उदाहरण

#include <iostream> 
#include <unordered_set> 
#include <unordered_map> 
#include <algorithm> 
using namespace std; 

const char MARKER = '$'; 
struct Node { 
    public: 
    char data; 
    Node *left, *right; 
}; 

Node* getNode(char key) { 
    Node* newNode = new Node; 
    newNode->data = key; 
    newNode->left = newNode->right = NULL; 
    return newNode; 
} 

unordered_set<string> subtrees; 
string inorder(Node* node, unordered_map<string, int>& map) { 
    if (!node) 
        return ""; 
    string str = "("; 
    str += inorder(node->left, map); 
    str += to_string(node->data); 
    str += inorder(node->right, map); 
    str += ")"; 
    if (map[str] == 1) 
        cout << node->data << " "; 
    map[str]++; 
    return str; 
} 

void duplicateSubtreeFind(Node *root) { 
    unordered_map<string, int> map; 
    inorder(root, map); 
} 

int main() { 
    Node *root = getNode('A'); 
    root->left = getNode('B'); 
    root->right = getNode('C'); 
    root->left->left = getNode('D'); 
    root->left->right = getNode('E'); 
    root->right->right = getNode('B'); 
    root->right->right->right = getNode('E'); 
    root->right->right->left= getNode('D'); 
    duplicateSubtreeFind(root); 
}

आउटपुट

D E B

  1. C++ में डुप्लिकेट उपट्री ढूंढना C++ में डुप्लिकेट उपट्री ढूंढना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें सभी डुप्लिकेट उपट्री ढूंढने हैं। इसलिए प्रत्येक प्रकार के डुप्लिकेट उपट्री के लिए, हमें उनमें से किसी एक का रूट नोड लौटाना है। मान लीजिए हमारे पास ऐसा ट्री है: डुप्लिकेट उपट्री हैं: हल का दृष्टिकोण इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  1. C++ में सभी डुप्लिकेट सबट्री खोजें C++ में सभी डुप्लिकेट सबट्री खोजें

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें यह पता लगाना है कि ट्री में कुछ डुप्लिकेट सबट्री हैं या नहीं। मान लीजिए हमारे पास नीचे जैसा बाइनरी ट्री है: आकार 2 के दो समान सबट्री हैं। प्रत्येक सबट्री में D, BD और BE भी डुप्लिकेट सबट्री हैं। हम इस समस्या को ट्री सीरियलाइज़ेशन और हैशिंग प्रक्रिया का उ

  1. C++ में एकल-मान वाले सबट्री की गिनती ढूंढना C++ में एकल-मान वाले सबट्री की गिनती ढूंढना

    मान लीजिए हमारे पास एक बाइनरी ट्री है। हमारा कार्य दिए गए ट्री में एकल-मान वाले सबट्री की गिनती करना है। एक एकल-मान वाला सबट्री एक सबट्री है, जहां उस ट्री के सभी नोड्स समान मान रखते हैं। मान लीजिए एक ट्री नीचे जैसा है -चार एकल-मान वाले सबट्री हैं। ये नीचे जैसे हैं -हम इसे बॉटम-अप तरीके से हल कर सकते