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

C++ में बाइनरी ट्री की अधिकतम चौड़ाई


समस्या विवरण

एक बाइनरी ट्री दिया गया है, दिए गए ट्री की अधिकतम चौड़ाई प्राप्त करने के लिए एक फंक्शन लिखें। ट्री की चौड़ाई सभी स्तरों की चौड़ाई का अधिकतम है।

नीचे दिए गए ट्री पर विचार करें −

      10      / \     7   4    / \   \   9   2   1          / \         2   5 1. स्तर 1 पर चौड़ाई: 1 2. स्तर 2 पर चौड़ाई: 2 3. स्तर 3 पर चौड़ाई: 3 4. स्तर 4 पर चौड़ाई: 2 उपरोक्त ट्री के लिए उत्तर 3 है।

एल्गोरिदम

1. उत्तर खोजने के लिए लेवल ऑर्डर ट्रैवर्सल का उपयोग करें

उदाहरण

#include <bits/stdc++.h> using namespace std; struct node {    public:       int data;       node* left;       node* right; }; int getWidth(node* root, int level); int height(node* node); node* newNode(int data); int getMaxWidth(node* root){    int maxWidth = 0;    int width;    int h = height(root);    int i;    for (i = 1; i <= h; ++i) {       width = getWidth(root, i);       if (width > maxWidth) {          maxWidth = width;       }    }    return maxWidth; } int getWidth(node* root, int level){    if (root == NULL) {       return 0;    }    if (level == 1) {       return 1;    }    else if (level > 1) {       return getWidth(root->left, level - 1) + getWidth(root->right, level - 1);    } } int height(node* node){    if (node == NULL) {       return 0;    }    int lHeight = height(node->left);    int rHeight = height(node->right);    return (lHeight > rHeight)? (lHeight + 1): (rHeight + 1); } node* newNode(int data){    node* Node = new node();    Node->data = data;    Node->left = NULL;    Node->right = NULL;    return(Node); } int main(){    node *root = newNode(10);    root->left = newNode(7);    root->right = newNode(4);    root->left->left = newNode(9);    root->left->right = newNode(2);    root->right->right = newNode(1);    root->right->right->left = newNode(2);    root->right->right->right = newNode(5);    cout<<"Maximum width = " << getMaxWidth(root) << endl;    return 0; }

आउटपुट

जब आप उपरोक्त प्रोग्राम को कंपाइल और एक्जीक्यूट करते हैं। यह निम्नलिखित आउटपुट उत्पन्न करता है −

Maximum width = 3

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

    इस समस्या में, हमें एक बाइनरी ट्री दिया गया है और हमें प्रत्येक स्तर पर सभी नोड्स को उनके मानों के सॉर्ट क्रम में प्रिंट करना है। आइए एक उदाहरण लेकर अवधारणा को बेहतर ढंग से समझते हैं, इनपुट - आउटपुट - 20 6 15 2 17 32 78 इस समस्या को हल करने के लिए, हमें ट्री के प्रत्येक स्तर का सॉर्ट क्रम प्रिंट कर

  1. C++ में बाइनरी ट्री में अधिकतम लेवल उत्पाद ढूंढें C++ में बाइनरी ट्री में अधिकतम लेवल उत्पाद ढूंढें

    मान लीजिए, एक बाइनरी ट्री दिया गया है। इसमें पॉजिटिव और नेगेटिव नोड्स हैं। हमें इसके प्रत्येक लेवल पर अधिकतम उत्पाद ढूंढना है। इसे ट्री मानें, तो लेवल 0 का उत्पाद 4 है, लेवल 1 का उत्पाद 2 * -5 = -10 है, और लेवल 2 का उत्पाद -1 * 3 * -2 * 6 = 36 है। तो यह अधिकतम है। इसे हल करने के लिए, हम ट्री का

  1. बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में बाइनरी ट्री में अधिकतम वर्टिकल योग खोजें C++ में

    मान लीजिए हमारे पास एक बाइनरी ट्री है। कार्य वर्टिकल ऑर्डर ट्रैवर्सल में सभी नोड्स के योग के अधिकतम को प्रिंट करना है। तो यदि ट्री नीचे जैसा है - वर्टिकल ऑर्डर ट्रैवर्सल इस तरह है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग खोज