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

C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं


मान लीजिए हमारे पास दो बाइनरी ट्री हैं। हमें जांचना है कि छोटा ट्री दूसरे बाइनरी ट्री का सबट्री है या नहीं। मान लीजिए ये दो ट्री दिए गए हैं।

C++ में जांचें कि बाइनरी ट्री किसी अन्य बाइनरी ट्री का सबट्री है या नहीं

दो ट्री हैं। दूसरा ट्री पहले का सबट्री है। इस गुण की जांच करने के लिए, हम ट्री को पोस्ट-ऑर्डर फैशन में ट्रैवर्स करेंगे, फिर यदि इस नोड से रूटेड सबट्री दूसरे ट्री के समान है, तो यह सबट्री है।

उदाहरण

#include <bits/stdc++.h> using namespace std; class node {    public:    int data;    node *left, *right; }; bool areTwoTreeSame(node * t1, node *t2) {    if (t1 == NULL && t2 == NULL)       return true;    if (t1 == NULL || t2 == NULL)       return false;    return (t1->data == t2->data && areTwoTreeSame(t1->left, t2->left) && areTwoTreeSame(t1->right, t2->right) ); } bool isSubtree(node *tree, node *sub_tree) {    if (sub_tree == NULL)       return true;    if (tree == NULL)       return false;    if (areTwoTreeSame(tree, sub_tree))       return true;    return isSubtree(tree->left, sub_tree) || isSubtree(tree->right, sub_tree); } node* getNode(int data) {    node* newNode = new node();    newNode->data = data;    newNode->left = newNode->right = NULL;    return newNode; } int main() {    node *real_tree = getNode(26);    real_tree->right = getNode(3);    real_tree->right->right = getNode(3);    real_tree->left = getNode(10);    real_tree->left->left = getNode(4);    real_tree->left->left->right = getNode(30);    real_tree->left->right = getNode(6);    node *sub_tree = getNode(10);    sub_tree->right = getNode(6);    sub_tree->left = getNode(4);    sub_tree->left->right = getNode(30);    if (isSubtree(real_tree, sub_tree))       cout << "Second tree is subtree of the first tree";    else       cout << "Second tree is not a subtree of the first tree"; }

आउटपुट

Second tree is subtree of the first tree

  1. C++ में बाइनरी ट्री लेवल-वाइज क्रमबद्ध है या नहीं जांचें C++ में बाइनरी ट्री लेवल-वाइज क्रमबद्ध है या नहीं जांचें

    समस्या विवरण जांचें कि बाइनरी ट्री लेवल-वाइज क्रमबद्ध है या नहीं। प्रत्येक लेवल में नोड्स बाएं से दाएं क्रमबद्ध हों और प्रत्येक लेवल के मान पिछले लेवल से बड़े हों। एल्गोरिदम (लेवल ऑर्डर ट्रैवर्सल) क्यू का उपयोग करके लेवल ऑर्डर ट्रैवर्सल प्रत्येक लेवल के लिए न्यूनतम (min_val) और अधिकतम (max_val) ट

  1. C++ में जांचें कि दिया गया बाइनरी ट्री सम-ट्री है या नहीं C++ में जांचें कि दिया गया बाइनरी ट्री सम-ट्री है या नहीं

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

  1. C++ में जांचें कि बाइनरी ट्री लेवल-वार सॉर्टेड है या नहीं C++ में जांचें कि बाइनरी ट्री लेवल-वार सॉर्टेड है या नहीं

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