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

C++ में दिया गया बाइनरी ट्री का वर्टिकल लेवल सॉर्टेड है या नहीं खोजें


अवधारणा

एक दिए गए बाइनरी ट्री के संबंध में, हमारा कार्य यह निर्धारित करना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल सॉर्टेड है या नहीं।

(इस मामले के संबंध में, जब दो नोड्स ओवरलैप होते हैं, तो सत्यापित करें कि क्या वे उस लेवल में एक सॉर्टेड अनुक्रम बनाते हैं जिसमें वे स्थित हैं।)

इनपुट

2 / \ 3 6 / \ 8 5   / 7 Level l = -1

आउटपुट

Yes

लेवल -1 में नोड्स 3 -> 7 हैं जो एक सॉर्टेड अनुक्रम बनाते हैं।

इनपुट

2 / \ 3 7 \ / 4 5 Level l = 0

आउटपुट

Yes

यह ध्यान दिया जाना चाहिए कि मान 4 और 5 वाले नोड्स बाइनरी ट्री में ओवरलैप हो रहे हैं।

अब हम सत्यापित करते हैं कि क्या यह लेवल के अनुसार एक सॉर्टेड अनुक्रम बनाते हैं। लेवल 0 में नोड्स 2 -> 4 -> 5 हैं जो एक सॉर्टेड अनुक्रम बनाते हैं।

विधि

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

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

उदाहरण

<प्रि क्लास="प्रिटीप्रिंट नोट्रांसलेट">// CPP program to determine whether // vertical level l of binary tree // is sorted or not. #include <bits/stdc++.h> using namespace std; // ट्री नोड की संरचना दिखाता है। struct Node1 {    int key1;    Node1 *left1, *right1; }; // नया ट्री नोड बनाने वाला फ़ंक्शन। Node1* newNode(int key1){    Node1* temp1 = new Node1;    temp1->key1 = key1;    temp1->left1 = temp1->right1 = NULL;    return temp1; } // सहायक फ़ंक्शन यह निर्धारित करने के लिए कि // दिए गए बाइनरी ट्री का वर्टिकल लेवल l // सॉर्टेड है या नहीं। bool isSorted1(Node1* root1, int level1){    // तो यदि रूट null है, तो उत्तर एक    // खाली उपसमुच्चय है और एक खाली उपसमुच्चय    // हमेशा सॉर्टेड माना जाता है।    if (root1 == NULL)       return true;    // वर्टिकल लेवल l में पिछले    // मान को संग्रहीत करने के लिए इंगित करता है।    int prevVal1 = INT_MIN;    // ट्री को वर्टिकली पार करते समय वर्तमान लेवल    // संग्रहीत करने के लिए इंगित करता है।    int currLevel1;    // ट्री को वर्टिकली पार करते समय वर्तमान नोड    // संग्रहीत करने के लिए इंगित करता है।    Node1* currNode1;    // वर्टिकल ऑर्डर ट्रैवर्सल करने के लिए कतार घोषित करने के लिए उपयोग किया जाता है। एक जोड़ी का उपयोग    // कतार के तत्व के रूप में किया जाता है। जोड़ी में पहला तत्व    // नोड को दर्शाता है और दूसरा    // तत्व उस नोड के वर्टिकल लेवल को दर्शाता है।    queue<pair<Node1*, int>> q1;    // रूट को कतार में डालने के लिए उपयोग किया जाता है। रूट का वर्टिकल लेवल    // 0 है।    q1.push(make_pair(root1, 0));    // वर्टिकल ऑर्डर ट्रैवर्सल तब तक करें जब तक    // सभी नोड्स विज़िट न हो जाएं।    while (!q1.empty()) {       currNode1 = q1.front().first;       currLevel1 = q1.front().second;       q1.pop();       // कतार से निकाले गए नोड के लेवल को सत्यापित करें       // आवश्यक लेवल है या नहीं। यदि यह       // आवश्यक लेवल है तो सत्यापित करें कि       // उस लेवल में पिछला मान नोड के मान से कम       // या बराबर है।       if (currLevel1 == level1) {          if (prevVal1 <= currNode1->key1)             prevVal1 = currNode1->key1;       else          return false;    }    // तो यदि बायां बच्चा NULL नहीं है तो इसे    // लेवल को 1 से कम करके कतार में डालें।    if (currNode1->left1)       q1.push(make_pair(currNode1->left1, currLevel1 - 1));    // तो यदि दायां बच्चा NULL नहीं है तो इसे    // लेवल को 1 से बढ़ाकर कतार में डालें।    if (currNode1->right1)       q1.push(make_pair(currNode1->right1, currLevel1 + 1));    }    // तो यदि पूछा गया लेवल दिए गए में मौजूद नहीं है    // बाइनरी ट्री, इसका मतलब है कि वह लेवल    // एक खाली उपसमुच्चय होगा। इसलिए उत्तर    // सच होगा।    return true; } // ड्राइवर प्रोग्राम int main(){ /*       2       / \       3 6       / \       8 5         /       7 */    Node1* root1 = newNode(2);    root1->left1 = newNode(3);    root1->right1 = newNode(6);    root1->left1->left1 = newNode(8);    root1->left1->right1 = newNode(5);    root1->left1->right1->left1 = newNode(7);    int level1 = -1;    if (isSorted1(root1, level1) == true)       cout << "Yes";    else       cout << "No";    return 0; }

आउटपुट

Yes

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

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

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

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

  1. Python में दिए गए बाइनरी ट्री के वर्टिकल लेवल को क्रमबद्ध है या नहीं जांचना Python में दिए गए बाइनरी ट्री के वर्टिकल लेवल को क्रमबद्ध है या नहीं जांचना

    मान लीजिए हमारे पास बाइनरी ट्री है; हमें जांचना है कि बाइनरी ट्री का दिया गया वर्टिकल लेवल क्रमबद्ध है या नहीं। जब दो नोड ओवरलैप हो रहे हों, तो जांचें कि वे उस लेवल से संबंधित हैं जहां वे क्रमबद्ध क्रम में हैं। तो, यदि इनपुट l = -1 है तो आउटपुट True होगा, क्योंकि लेवल -1 में तत्व 3, 7 हैं और वे क्र