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

जांचें कि बाइनरी ट्री को सी ++ में स्तर के अनुसार क्रमबद्ध किया गया है या नहीं

यहां हम देखेंगे कि बाइनरी ट्री की जांच कैसे की जाती है कि यह स्तर के अनुसार क्रमबद्ध है या नहीं। स्तर के अनुसार क्रमबद्ध बाइनरी ट्री नीचे जैसा दिखेगा -

जांचें कि बाइनरी ट्री को सी ++ में स्तर के अनुसार क्रमबद्ध किया गया है या नहीं

प्रत्येक स्तर में, नोड्स को बाएं से दाएं क्रमबद्ध किया जाता है, और प्रत्येक परत में अपने पिछले स्तर की तुलना में उच्च मान होता है।

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

उदाहरण

#include <iostream>
#include <queue>
using namespace std;
class Node {
   public:
   int key;
   Node *left, *right;
};
Node* getNode(int key) {
   Node* newNode = new Node;
   newNode->key = key;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool isLevelWiseSorted(Node* root) {
   int prevMax = INT_MIN;
   int min_val, max_val;
   int levelSize;
      queue<Node*> q;
      q.push(root);
      while (!q.empty()) {
         levelSize = q.size();
         min_val = INT_MAX;
         max_val = INT_MIN;
         while (levelSize > 0) {
            root = q.front();
            q.pop();
            levelSize--;
            min_val = min(min_val, root->key);
            max_val = max(max_val, root->key);
            if (root->left)
               q.push(root->left);
            if (root->right)
               q.push(root->right);
         }
         if (min_val <= prevMax)
            return false;
         prevMax = max_val;
      }
      return true;
}
int main() {
   Node* root = getNode(1);
   root->left = getNode(2);
   root->right = getNode(3);
   root->left->left = getNode(4);
   root->left->right = getNode(5);
   root->right->left = getNode(6);
   root->right->right = getNode(7);
   if (isLevelWiseSorted(root))
      cout << "Tree is levelwise Sorted";
   else
      cout << "Tree is Not levelwise sorted";
}

आउटपुट

Tree is level wise Sorted

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

    यहां हम देखेंगे कि कैसे जांचा जाए कि बाइनरी ट्री सम-ट्री है या नहीं। अब प्रश्न यह है कि योग वृक्ष क्या है। सम-ट्री एक बाइनरी ट्री है जहाँ एक नोड अपने बच्चों का योग मान रखेगा। पेड़ की जड़ में उसके नीचे के सभी तत्वों का योग होगा। यह सम-वृक्ष का उदाहरण है - इसे चेक करने के लिए हम एक आसान सी ट्रिक अप

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

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

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

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