সি++-এ থ্রেডেড বাইনারি ট্রির ইনঅর্ডার ট্রাভার্সাল

থ্রেডেড বাইনারি ট্রি হলো বাইনারি ট্রির একটি ভেরিয়েশন যেখানে খালি লিংক (NULL পয়েন্টার)গুলোকে থ্রেড হিসেবে ব্যবহার করা হয়। ফুলি থ্রেডেড ট্রিতে প্রতিটি নোডের পাঁচ ফিল্ড থাকে: লেফট থ্রেড ফ্ল্যাগ, লেফট লিংক, ডেটা, রাইট লিংক, রাইট থ্রেড ফ্ল্যাগ।

এলগরিদম (ইনঅর্ডার)

inorder():
    temp = root
    repeat infinitely:
        p = temp
        temp = temp->right
        if p->rightTh == false:
            while temp->leftTh == false:
                temp = temp->left
        if temp == root: break
        print temp->key

উদাহরণ কোড

#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 << "Threaded Binary Tree\n";
    tbt.insert(56); tbt.insert(23); tbt.insert(89);
    tbt.insert(85); tbt.insert(20); tbt.insert(30); tbt.insert(12);
    tbt.inorder();
    return 0;
}

আউটপুট

Threaded Binary Tree
12 20 23 30 56 85 89