C++ प्रोग्राम: दिए गए बाइनरी ट्री का इनऑर्डर नॉन-रिकर्सिव ट्रैवर्सल करना

यदि एक बाइनरी ट्री को इन-ऑर्डर में ट्रैवर्स किया जाता है, तो पहले लेफ्ट सबट्री देखी जाती है, फिर रूट और बाद में राइट सब-ट्री। इनऑर्डर ट्रैवर्सल में आउटपुट कुंजी आरोही क्रम में होती है। यह रिकर्सन के बिना इनऑर्डर ट्री ट्रैवर्सल के लिए एक C++ प्रोग्राम है।

एल्गोरिदम

Begin
    n स्ट्रक्चर घोषित करें।
        d को इंटीजर डेटा टाइप के रूप में घोषित करें।
        स्ट्रक्चर n के विरुद्ध एक पॉइंटर l घोषित करें।
        स्ट्रक्चर n के विरुद्ध एक पॉइंटर r घोषित करें।
        स्ट्रक्चर n का कंस्ट्रक्टर घोषित करें।
            एक इंटीजर वेरिएबल d को पैरामीटर के रूप में पास करें।
            this->d = d
            l = r = NULL
    inOrder(struct n *root) फंक्शन घोषित करें।
        एक स्टैक s घोषित करें।
        स्ट्रक्चर n के विरुद्ध एक पॉइंटर current घोषित करें।
            n *current = root आरंभ करें।
        while (current != NULL || s.empty() == false)
            while (current != NULL)
                s.push(current)
                current = current->l
            current = s.top()
            s.pop()
            current->d प्रिंट करें।
            current = current->r.
    ट्री के नोड्स में मान डालें।
    ट्री को ट्रैवर्स करने के लिए inOrder(root) फंक्शन कॉल करें।
End.

उदाहरण

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

struct n {
    int d;
    struct n* l;
    struct n* r;
    n (int d) {
        this->d = d;
        l = r = NULL;
    }
};

void inOrder(struct n *root) {
    stack<n *> s;
    n *current = root;
    while (current != NULL || s.empty() == false) {
        while (current != NULL) {
            s.push(current);
            current = current->l;
        }
        current = s.top();
        s.pop();
        cout << current->d << " ";
        current = current->r;
    }
}

int main() {
    struct n* root = new n(6);
    root->l = new n(4);
    root->r= new n(7);
    root->l->l = new n(8);
    root->l->r= new n(5);
    root->r->l = new n(9);
    root->r->r = new n(10);
    inOrder(root);
    return 0;
}

आउटपुट

8 4 5 6 9 7 10