C++ में थ्रेडेड बाइनरी ट्री का इनऑर्डर ट्रैवर्सल

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

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

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

यह फुली थ्रेडेड बाइनरी ट्री है।

एल्गोरिदम

inorder(): Begin
    temp := root
    अनंत बार दोहराएं, करें
        p := temp
        temp = temp का दायां
        यदि p का दायां फ्लैग गलत है, तो
            जबकि temp का बायां फ्लैग शून्य नहीं है, करें
                temp := temp का बायां
            किया
        अंत यदि
        यदि temp और root समान हैं, तो
            ब्रेक
        अंत यदि
        temp की कुंजी प्रिंट करें
    किया
End

उदाहरण

#include <iostream>
#define MAX_VALUE 65536
using namespace std;

class N { // नोड घोषणा
public:
    int k;
    N *l, *r;
    bool leftTh, rightTh;
};

class ThreadedBinaryTree {
private:
    N *root;
public:
    ThreadedBinaryTree() { // चर आरंभ करने के लिए कंस्ट्रक्टर
        root = new N();
        root->r = root->l = root;
        root->leftTh = true;
        root->k = MAX_VALUE;
    }

    void insert(int key) {
        N *p = root;
        for (;;) {
            if (p->k < key) { // दाएं थ्रेड पर जाएं
                if (p->rightTh)
                    break;
                p = p->r;
            } else if (p->k > key) { // बाएं थ्रेड पर जाएं
                if (p->leftTh)
                    break;
                p = p->l;
            } else {
                return;
            }
        }
        N *temp = new N();
        temp->k = key;
        temp->rightTh = temp->leftTh = true;
        if (p->k < key) {
            temp->r = p->r;
            temp->l = p;
            p->r = temp;
            p->rightTh = false;
        } else {
            temp->r = p;
            temp->l = p->l;
            p->l = temp;
            p->leftTh = false;
        }
    }

    void inorder() { // ट्री प्रिंट करें
        N *temp = root, *p;
        for (;;) {
            p = temp;
            temp = temp->r;
            if (!p->rightTh) {
                while (!temp->leftTh) {
                    temp = temp->l;
                }
            }
            if (temp == root)
                break;
            cout << temp->k << " ";
        }
        cout << endl;
    }
};

int main() {
    ThreadedBinaryTree tbt;
    cout << "थ्रेडेड बाइनरी ट्री\n";
    tbt.insert(56);
    tbt.insert(23);
    tbt.insert(89);
    tbt.insert(85);
    tbt.insert(20);
    tbt.insert(30);
    tbt.insert(12);
    tbt.inorder();
    cout << "\n";
}

आउटपुट

थ्रेडेड बाइनरी ट्री
12 20 23 30 56 85 89