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

C++ में जांचें कि आकार n की दी गई सरणी n लेवल के BST को दर्शा सकती है या नहीं


हमारे पास एक सरणी A है, हमें जांचना है कि सरणी n लेवल के BST को दर्शा सकती है या नहीं। चूंकि लेवल n है, हम निम्न तरीके से ट्री बना सकते हैं। मान लीजिए एक संख्या k है, k से बड़ा मान दाईं ओर जाता है, और k से छोटा मान बाईं ओर जाता है। मान लीजिए दो सूचियां हैं: {50, 20, 9, 25, 10}, और {50, 30, 20, 25, 10}

C++ में जांचें कि आकार n की दी गई सरणी n लेवल के BST को दर्शा सकती है या नहीं

पहली वैध नहीं है, लेकिन दूसरी वैध है।

इसे जांचने के लिए हम या तो BST बना सकते हैं और ऊंचाई जांच सकते हैं, अन्यथा सरणी-आधारित दृष्टिकोण का उपयोग कर सकते हैं। सरणी-आधारित दृष्टिकोण नीचे जैसा है -

  • दो वेरिएबल लें max = इन्फिनिटी, बाएं सबट्री की अधिकतम सीमा चिह्नित करने के लिए, और min = नेगेटिव इन्फिनिटी दाएं सबट्री के लिए न्यूनतम सीमा चिह्नित करने के लिए
  • arr[i] से arr[n-1] रेंज में प्रत्येक तत्व के लिए, निम्न चरण दोहराएं
    • यदि arr[i] > arr[i-1] और arr[i] > min और arr[i] < max, तो min := arr[i-1] अपडेट करें
    • अन्यथा यदि arr[i] > min और arr[i] < max, तो max := arr[i] अपडेट करें
    • यदि इनमें से कोई भी वैध नहीं है, तो तत्व एक नए लेवल में डाला जाएगा, तो ब्रेक करें

उदाहरण

#include <iostream> using namespace std; bool canMakeBSTifHeightN(int arr[], int n) {    int min = INT_MIN;    int max = INT_MAX;    for(int i = 1; i < n; i++){       if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {          min = arr[i - 1];       } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] <       max) {          max = arr[i - 1];       } else {          return true;       }    }    return false; } int main() {    int elements[] = {50, 30, 20, 25, 10};    int n = sizeof(elements)/sizeof(elements[0]);    if (canMakeBSTifHeightN(elements, n))       cout << "We can make BST of height " << n;    else       cout << "We can not make BST of height " << n; }

आउटपुट

We can make BST of height 5

  1. C++ में सरणी BST के प्रीऑर्डर ट्रैवर्सल को दर्शा सकती है या नहीं जांचें C++ में सरणी BST के प्रीऑर्डर ट्रैवर्सल को दर्शा सकती है या नहीं जांचें

    समस्या विवरण एक सरणी दी गई है, जांचें कि क्या यह किसी BST का वैध प्रीऑर्डर ट्रैवर्सल हो सकती है। उदाहरण: {40, 30, 35, 80, 100} → वैध BST प्रीऑर्डर एल्गोरिदम (स्टैक का उपयोग) खाली स्टैक और root = INT_MIN प्रत्येक तत्व के लिए: यदि तत्व < root → false स्टैक टॉप: स्टैक से पॉप करें, अंतिम पॉप

  1. C++ में जांचें कि दिया गया ट्री ग्राफ रैखिक है या नहीं C++ में जांचें कि दिया गया ट्री ग्राफ रैखिक है या नहीं

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

  1. C++ में जांचें कि आकार n की दी गई सरणी n लेवल के BST को दर्शा सकती है या नहीं C++ में जांचें कि आकार n की दी गई सरणी n लेवल के BST को दर्शा सकती है या नहीं

    हमारे पास एक सरणी A है, हमें जांचना है कि सरणी n लेवल के BST को दर्शा सकती है या नहीं। चूंकि लेवल n है, हम निम्न तरीके से ट्री बना सकते हैं। मान लीजिए एक संख्या k है, k से बड़ा मान दाईं ओर जाता है, और k से छोटा मान बाईं ओर जाता है। मान लीजिए दो सूचियां हैं: {50, 20, 9, 25, 10}, और {50, 30, 20, 25, 1