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

C++ में बाइनरी ट्री में मौजूद बाइनरी सर्च ट्री की संख्या गिनना


हमें एक बाइनरी ट्री इनपुट के रूप में दिया गया है। लक्ष्य उसमें मौजूद बाइनरी सर्च ट्री (BST) सबट्री की संख्या ज्ञात करना है। BST एक बाइनरी ट्री है जिसमें बायां चाइल्ड रूट से कम और दायां चाइल्ड रूट से अधिक होता है।

उदाहरण के लिए

इनपुट

मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

C++ में बाइनरी ट्री में मौजूद बाइनरी सर्च ट्री की संख्या गिनना

आउटपुट

Count the Number of Binary Search Trees present in a Binary Tree are: 2

व्याख्या

हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या इसमें कोई बाइनरी सर्च ट्री मौजूद है। प्रत्येक रूट नोड एक बाइनरी सर्च ट्री को दर्शाता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि कोई अन्य बाइनरी सर्च ट्री मौजूद नहीं है इसलिए गिनती 2 है जो बाइनरी ट्री में लीफ नोड्स की कुल संख्या है।

इनपुट

मानों को इनपुट करने के बाद जो ट्री बनेगा वह नीचे दिया गया है:

C++ में बाइनरी ट्री में मौजूद बाइनरी सर्च ट्री की संख्या गिनना

आउटपुट

Count the Number of Binary Search Trees present in a Binary Tree are: 6

व्याख्या

हमें पूर्णांक मानों की एक सरणी दी गई है जिसका उपयोग बाइनरी ट्री बनाने के लिए किया जाता है और हम जांचेंगे कि क्या इसमें कोई बाइनरी सर्च ट्री मौजूद है। प्रत्येक रूट नोड एक बाइनरी सर्च ट्री को दर्शाता है इसलिए दिए गए बाइनरी ट्री में हम देख सकते हैं कि 4 लीफ नोड्स और दो सबट्री हैं जो BST बना रहे हैं इसलिए गिनती 6 है।

C++ में बाइनरी ट्री में मौजूद बाइनरी सर्च ट्री की संख्या गिनना

C++ में बाइनरी ट्री में मौजूद बाइनरी सर्च ट्री की संख्या गिनना

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:

इस दृष्टिकोण में हम नोड N के बाएं सबट्री में नोड के सबसे बड़े मान को ढूंढते हैं और जांचते हैं कि क्या यह N से कम है। साथ ही, हम नोड N के दाएं सबट्री में सबसे छोटे मान को ढूंढते हैं और जांचते हैं कि क्या यह N से अधिक है। यदि सही है, तो यह एक BST है। बाइनरी ट्री को बॉटम-अप तरीके से ट्रैवर्स करें और उपरोक्त शर्तों की जांच करें और BST की गिनती बढ़ाएं।

  • प्रत्येक नोड के नोड_डेटा में उस ट्री में मौजूद BST की संख्या, उस ट्री में अधिकतम मान, न्यूनतम मान, बूलियन ट्रू यदि वह सबट्री BST है जैसी जानकारी होती है।

  • फ़ंक्शन BST_present(struct tree_node* parent) parent पर रूटेड बाइनरी ट्री के अंदर मौजूद BST की संख्या ढूंढता है।

  • यदि parent NULL है तो { 0, min, max, true } लौटाएं जहां min INT_MIN है और max INT_MAX है।

  • यदि बाएं और दाएं चाइल्ड NULL हैं तो { 1, parent->data, parent->data, true } लौटाएं।

  • node_data Left = BST_present(parent->left); और node_data Right = BST_present(parent->right); सेट करें।

  • नोड n1 लें और n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest))) को उसके दाएं सबट्री में सबसे कम मान के रूप में सेट करें।

  • n1.highest = max(parent->data, (max(Left.highest, Right.highest))); को उसके बाएं सबट्री में सबसे अधिक मान के रूप में सेट करें।

  • if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest) ट्रू लौटाता है तो n1.check = true सेट करें क्योंकि यह एक BST है।

  • BST की गिनती बढ़ाएं: n1.total_bst = 1 + Left.total_bst + Right.total_bst;

  • अन्यथा n1.check = false सेट करें और गिनती को n1.total_bst = Left.total_bst + Right.total_bst के रूप में सेट करें।

  • अंत में n1 लौटाएं।

उदाहरण

#include <bits/stdc++.h> using namespace std; struct tree_node{ struct tree_node* left; struct tree_node* right; int data; tree_node(int data){ this->data = data; this->left = NULL; this->right = NULL; } }; struct node_data{ int total_bst; int highest, lowest; bool check; }; node_data BST_present(struct tree_node* parent){ if(parent == NULL){ int max = INT_MAX; int min = INT_MIN; return { 0, min, max, true }; } if(parent->left == NULL){ if(parent->right == NULL){ return { 1, parent->data, parent->data, true }; } } node_data Left = BST_present(parent->left); node_data Right = BST_present(parent->right); node_data n1; n1.lowest = min(parent->data, (min(Left.lowest, Right.lowest))); n1.highest = max(parent->data, (max(Left.highest, Right.highest))); if(Left.check && Right.check && parent->data > Left.highest && parent->data < Right.lowest){ n1.check = true; n1.total_bst = 1 + Left.total_bst + Right.total_bst; } else{ n1.check = false; n1.total_bst = Left.total_bst + Right.total_bst; } return n1; } int main(){ struct tree_node* root = new tree_node(3); root->left = new tree_node(7); root->right = new tree_node(4); root->left->left = new tree_node(5); root->right->right = new tree_node(1); root->left->left->left = new tree_node(10); cout<<"Count the Number of Binary Search Trees present in a Binary Tree are: "<<BST_present(root).total_bst; return 0; }

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा:

Count the Number of Binary Search Trees present in a Binary Tree are: 2

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

    एक बाइनरी ट्री एक विशेष प्रकार का ट्री है जिसमें ट्री का प्रत्येक नोड अधिकतम दो चाइल्ड नोड रख सकता है। इन चाइल्ड नोड्स को राइट चाइल्ड और लेफ्ट चाइल्ड के नाम से जाना जाता है। एक साधारण बाइनरी ट्री है - बाइनरी सर्च ट्री (BST) एक विशेष प्रकार का ट्री है जो निम्नलिखित नियमों का पालन करता है - बाएं चाइ

  1. C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें C++ में बाइनरी सर्च ट्री में न्यूनतम मान वाला नोड ज्ञात करें

    मान लीजिए हमारे पास एक बाइनरी सर्च ट्री है। हमें बाइनरी सर्च ट्री में न्यूनतम तत्व ढूंढना है। इसलिए यदि BST नीचे की तरह है: न्यूनतम तत्व 1 होगा। जैसा कि हम जानते हैं कि बायां उपट्री हमेशा छोटे तत्वों को धारण करता है। इसलिए यदि हम बाएं उपट्री के माध्यम से तब तक ट्रैवर्स करते हैं जब तक बायां NULL नही

  1. C++ प्रोग्राम: बाइनरी ट्री के प्रत्येक नोड में सेट बिट्स की संख्या प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री के प्रत्येक नोड में सेट बिट्स की संख्या प्रिंट करना

    दिए गए बाइनरी ट्री में, फ़ंक्शन नोड्स में संग्रहीत कुंजियों के बाइनरी मान उत्पन्न करेगा और फिर उस बाइनरी समतुल्य में सेट बिट्स (1) की संख्या लौटाएगा। उदाहरण बाइनरी ट्री जिसमें कुंजियां हैं: 10 3 211 140 162 100 और 146 कुंजी बाइनरी समतुल्य सेट बिट्स (आउटपुट) 10 1010 2 3 0011 2 211 1101001