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

C++ में बाइनरी ट्री की संपूर्णता जांचना


मान लीजिए हमारे पास एक बाइनरी ट्री है। हमें जांचना है कि क्या यह ट्री एक पूर्ण बाइनरी ट्री (Complete Binary Tree) है या नहीं। लेवल n का एक पूर्ण बाइनरी ट्री में n-1 लेवल पूरी तरह भरे होते हैं, और लेवल n पर सभी नोड्स बाईं ओर से भरे होते हैं।

उदाहरण: ट्री [1,2,3,4,5,6] के लिए आउटपुट true (1) होगा, क्योंकि यह एक पूर्ण बाइनरी ट्री है।

BFS-आधारित एल्गोरिदम

  1. यदि ट्री खाली है, तो true लौटाएँ।
  2. एक क्यू q बनाएँ और रूट डालें।
  3. flag := true सेट करें (यह दर्शाता है कि अब तक सभी नोड्स पूर्ण हैं)।
  4. while q खाली नहीं है:
    • sz := q का आकार।
    • while sz > 0:
      • node := q से डी-क्यू किया गया नोड।
      • यदि node->left मौजूद है:
        • यदि flag सेट है, तो node->left को एनक्यू करें, अन्यथा false लौटाएँ।
      • अन्यथा flag := false।
      • यदि node->right मौजूद है:
        • यदि flag सेट है, तो node->right को एनक्यू करें, अन्यथा false लौटाएँ।
      • flag := false (राइट चाइल्ड के बाद कोई और चाइल्ड नहीं हो सकता)।
      • sz--।
  5. true लौटाएँ।

C++ कार्यान्वयन

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = NULL; right = NULL; }
};

class Solution {
public:
    bool isCompleteTree(TreeNode* root) {
        if (!root) return true;
        queue<TreeNode*> q;
        q.push(root);
        bool isComplete = true;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                TreeNode* node = q.front(); q.pop();
                if (node->left) {
                    if (isComplete) q.push(node->left);
                    else return false;
                } else {
                    isComplete = false;
                }
                if (node->right) {
                    if (isComplete) q.push(node->right);
                    else return false;
                } else {
                    isComplete = false;
                }
            }
        }
        return true;
    }
};

// टेस्ट
int main() {
    vector<int> v = {1,2,3,4,5,6};
    // make_tree फंक्शन की आवश्यकता होगी (लेवल ऑर्डर से ट्री बनाएँ)
    // यहाँ सरलता के लिए मान लें ट्री बना है
    Solution ob;
    // cout << ob.isCompleteTree(root);
    return 0;
}

इनपुट

{1,2,3,4,5,6}

आउटपुट

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

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

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

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

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

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