C++ प्रोग्राम: बाइनरी ट्री का डबल ऑर्डर ट्रैवर्सल कार्यान्वित करें

एल्गोरिदम

BST क्लास बनाएं जिसमें insert() फ़ंक्शन ट्री में आइटम डालने के लिए और doubleOrder() फ़ंक्शन डबल ऑर्डर ट्रैवर्सल के लिए हो। doubleOrder() में: यदि रूट null है तो "ट्री खाली है" प्रिंट करें। अन्यथा: रूट पर जाएं, बाएं सब-ट्री पर जाएं, रूट पर दोबारा जाएं, दाएं सब-ट्री पर जाएं।

उदाहरण कोड

#include <iostream>
#include <cstdlib>
using namespace std;

struct nod {
    int info;
    struct nod *l;
    struct nod *r;
} *r;

class BST {
public:
    void insert(nod *, nod *);
    void doubleOrder(nod *);
    void show(nod *, int);
    BST() { r = NULL; }
};

void BST::insert(nod *tree, nod *newnode) {
    if (r == NULL) {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout << "रूट नोड जोड़ा गया" << endl;
        return;
    }
    if (tree->info == newnode->info) {
        cout << "तत्व पहले से ट्री में है" << endl;
        return;
    }
    if (tree->info > newnode->info) {
        if (tree->l != NULL) {
            insert(tree->l, newnode);
        } else {
            tree->l = newnode;
            (tree->l)->l = NULL;
            (tree->l)->r = NULL;
            cout << "नोड बाएं जोड़ा गया" << endl;
            return;
        }
    } else {
        if (tree->r != NULL) {
            insert(tree->r, newnode);
        } else {
            tree->r = newnode;
            (tree->r)->l = NULL;
            (tree->r)->r = NULL;
            cout << "नोड दाएं जोड़ा गया" << endl;
            return;
        }
    }
}

void BST::doubleOrder(nod *ptr) {
    if (r == NULL) {
        cout << "ट्री खाली है" << endl;
        return;
    }
    if (ptr != NULL) {
        cout << ptr->info << " ";
        doubleOrder(ptr->l);
        cout << ptr->info << " ";
        doubleOrder(ptr->r);
    }
}

void BST::show(nod *ptr, int level) {
    int i;
    if (ptr != NULL) {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r)
            cout << "रूट->: ";
        else {
            for (i = 0; i < level; i++)
                cout << " ";
        }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main() {
    int c, n;
    BST bst;
    nod *t;
    while (1) {
        cout << "1. तत्व डालें" << endl;
        cout << "2. डबल-ऑर्डर ट्रैवर्सल" << endl;
        cout << "3. दिखाएं" << endl;
        cout << "4. बाहर निकलें" << endl;
        cout << "अपनी पसंद दर्ज करें: ";
        cin >> c;
        switch (c) {
            case 1:
                t = new nod;
                cout << "डालने के लिए संख्या दर्ज करें: ";
                cin >> t->info;
                bst.insert(r, t);
                break;
            case 2:
                cout << "BST का डबल-ऑर्डर ट्रैवर्सल:" << endl;
                bst.doubleOrder(r);
                cout << endl;
                break;
            case 3:
                cout << "BST प्रिंट करें:" << endl;
                bst.show(r, 1);
                cout << endl;
                break;
            case 4:
                exit(1);
            default:
                cout << "गलत पसंद" << endl;
        }
    }
}

आउटपुट

1. तत्व डालें
2. डबल-ऑर्डर ट्रैवर्सल
3. दिखाएं
4. बाहर निकलें
अपनी पसंद दर्ज करें: 1
डालने के लिए संख्या दर्ज करें: 7
रूट नोड जोड़ा गया
1. तत्व डालें
2. डबल-ऑर्डर ट्रैवर्सल
3. दिखाएं
4. बाहर निकलें
अपनी पसंद दर्ज करें: 1
डालने के लिए संख्या दर्ज करें: 6
नोड बाएं जोड़ा गया
...
डबल-ऑर्डर ट्रैवर्सल: 7 6 4 2 2 4 6 7 10 10