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

C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना


इस समस्या में, हमें एक बाइनरी ट्री दी गई है और हमें बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना है।

उदाहरण

इनपुट -

C++ में बाइनरी ट्री के सभी लीफ नोड्स को दाएं से बाएं प्रिंट करना

आउटपुट - 7 4 1

इस समस्या को हल करने के लिए, हमें बाइनरी ट्री को पार करना होगा। यह ट्रैवर्सल दो तरीकों से किया जा सकता है -

प्रीऑर्डर ट्रैवर्सल

यह ट्रैवर्सल रिकर्सन का उपयोग करता है। यहां, हम रूट फिर बाएं और फिर दाएं सबट्री को पार करेंगे। यदि हम एक लीफ नोड का सामना करते हैं तो हम इसे प्रिंट करेंगे, अन्यथा हम नोड के चाइल्ड्रन की जांच करेंगे और लीफ नोड ढूंढने के लिए उन्हें एक्सप्लोर करेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम:

#include <iostream> 
using namespace std; 

struct Node { 
    int data; 
    struct Node *left, *right; 
}; 

Node* insertNode(int data) { 
    Node* temp = new Node; 
    temp->data = data; 
    temp->left = temp->right = NULL; 
    return temp; 
} 

void findLeafNode(Node* root) { 
    if (!root) 
        return; 
    if (!root->left && !root->right) { 
        cout << root->data << "\t"; 
        return; 
    } 
    if (root->right) 
        findLeafNode(root->right); 
    if (root->left) 
        findLeafNode(root->left); 
} 

int main() { 
    Node* root = insertNode(21); 
    root->left = insertNode(5); 
    root->right = insertNode(11); 
    root->left->left = insertNode(8); 
    root->left->right = insertNode(98); 
    root->right->left = insertNode(2); 
    root->right->right = insertNode(8); 
    cout << "Leaf nodes of the tree from right to left are:\n"; 
    findLeafNode(root); 
    return 0; 
}

आउटपुट

Leaf nodes of the tree from right to left are - 18 2 98 8

पोस्टऑर्डर ट्रैवर्सल

लीफ नोड ढूंढने के लिए यह ट्रैवर्सल इटरेशन का उपयोग करेगा। हम डेटा संग्रहीत करने के लिए एक स्टैक का उपयोग करेंगे और ट्री को पोस्टऑर्डर तरीके से पार करेंगे (पहले दायां सबट्री फिर बायां सबट्री और फिर रूट) और लीफ नोड्स प्रिंट करेंगे।

उदाहरण

हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम:

#include<bits/stdc++.h> 
using namespace std; 

struct Node { 
    Node* left; 
    Node* right; 
    int data; 
}; 

Node* insertNode(int key) { 
    Node* node = new Node(); 
    node->left = node->right = NULL; 
    node->data = key; 
    return node; 
} 

void findLeafNode(Node* tree) { 
    stack<Node*> treeStack; 
    while (1) { 
        if (tree) { 
            treeStack.push(tree); 
            tree = tree->right; 
        } else { 
            if (treeStack.empty()) 
                break; 
            else { 
                if (treeStack.top()->left == NULL) { 
                    tree = treeStack.top(); 
                    treeStack.pop(); 
                    if (tree->right == NULL) 
                        cout << tree->data << "\t"; 
                } 
                while (tree == treeStack.top()->left) { 
                    tree = treeStack.top(); 
                    treeStack.pop(); 
                    if (treeStack.empty()) 
                        break; 
                } 
                if (!treeStack.empty()) 
                    tree = treeStack.top()->left; 
                else 
                    tree = NULL; 
            } 
        } 
    } 
} 

int main() { 
    Node* root = insertNode(21); 
    root->left = insertNode(5); 
    root->right = insertNode(11); 
    root->left->left = insertNode(8); 
    root->left->right = insertNode(98); 
    root->right->left = insertNode(2); 
    root->right->right = insertNode(18); 
    cout << "Leaf nodes of the tree from right to left are:\n"; 
    findLeafNode(root); 
    return 0; 
}

आउटपुट

Leaf nodes of the tree from right to left are - 18 2 98 8

  1. C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना C++ में बाइनरी सर्च ट्री के सभी विषम नोड्स प्रिंट करना

    इस समस्या में, हमें एक बाइनरी सर्च ट्री दी गई है और हमें उन सभी नोड्स को प्रिंट करना है जिनके मान विषम हैं। बाइनरी सर्च ट्री बाइनरी सर्च ट्री एक विशेष प्रकार का ट्री है जिसमें निम्नलिखित गुण होते हैं: बायां सबट्री हमेशा रूट नोड से छोटे मान रखता है। दायां सबट्री हमेशा रूट नोड से बड़े मान रखता है।

  1. C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में सभी नोड्स के लेवल प्रिंट करना

    दिए गए बाइनरी ट्री में, कार्य 1 से n तक शुरू होने वाले प्रत्येक कुंजी से जुड़े लेवल को प्रिंट करना है जो एक नोड में संग्रहीत है। उपरोक्त ट्री में नोड्स हैं - 10 at level 1 3 and 211 at level 2 140, 162, 100 and 146 at level 3 दिए गए कुंजी के लिए प्रोग्राम को उस विशेष कुंजी का लेवल प्रिंट करना होगा।

  1. C++ प्रोग्राम: बाइनरी ट्री में लीफ नोड्स को बाएं से दाएं एक स्टैक का उपयोग करके प्रिंट करना C++ प्रोग्राम: बाइनरी ट्री में लीफ नोड्स को बाएं से दाएं एक स्टैक का उपयोग करके प्रिंट करना

    प्रोग्राम को बाइनरी ट्री के लीफ नोड्स को बाएं से दाएं प्रिंट करना चाहिए लेकिन चुनौती केवल एक स्टैक का उपयोग करना है। push() फ़ंक्शन के माध्यम से बाइनरी ट्री के नोड्स डालें और pop() ऑपरेशन के माध्यम से लीफ नोड्स प्रदर्शित करें। लीफ नोड्स अंतिम नोड्स हैं जिनका बाएं और दाएं पॉइंटर NULL होता है जिसका अर