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

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


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

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

इसे जांचने के लिए, हम एक सरल तरकीब अपनाएंगे। हम बाएं और दाएं सबट्री के तत्वों का योग निकालेंगे। यदि योग का मान रूट के समान है, तो वह सम-ट्री है। यह एक पुनरावर्ती दृष्टिकोण होगा।

उदाहरण

#include <bits/stdc++.h> using namespace std; class node {    public:    int data;    node* left, *right; }; int sum_of_nodes(node *root) {    if(root == NULL)       return 0;    return sum_of_nodes(root->left) + root->data + sum_of_nodes(root->right); } int isSumTree(node* node) {    int left_sum, right_sum;    if(node == NULL || (node->left == NULL && node->right == NULL))       return 1;    left_sum = sum_of_nodes(node->left);    right_sum = sum_of_nodes(node->right);    if((node->data == left_sum + right_sum) && isSumTree(node->left) && isSumTree(node->right))       return 1;    return 0; } node* getNode(int data) {    node* newNode = new node();    newNode->data = data;    newNode->left = newNode->right = NULL;    return newNode; } int main() {    node *root = getNode(26);    root->left = getNode(10);    root->right = getNode(3);    root->left->left = getNode(4);    root->left->right = getNode(6);    root->right->right = getNode(3);    if(isSumTree(root))       cout << "The tree is Sum Tree";    else       cout << "The tree is not a Sum Tree"; }

आउटपुट

The tree is Sum Tree

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

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

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

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

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

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