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

এখানে আমরা থ্রেডেড বাইনারি ট্রি ডাটা স্ট্রাকচার দেখব। আমরা জানি যে বাইনারি ট্রি নোডগুলিতে সর্বাধিক দুটি সন্তান থাকতে পারে। কিন্তু যদি তাদের শুধুমাত্র একটি সন্তান থাকে, বা কোন সন্তান না থাকে, তাহলে লিঙ্ক করা তালিকার প্রতিনিধিত্বের লিঙ্ক অংশটি শূন্য থাকে। থ্রেডেড বাইনারি ট্রি উপস্থাপনা ব্যবহার করে, আমরা কিছু থ্রেড তৈরি করে সেই খালি লিঙ্কগুলি পুনরায় ব্যবহার করতে পারি।

যদি একটি নোডে কিছু খালি বাম বা ডান চাইল্ড এলাকা থাকে, তাহলে সেটি থ্রেড হিসেবে ব্যবহার করা হবে। দুই ধরনের থ্রেডেড বাইনারি গাছ আছে। একক থ্রেডেড ট্রি বা সম্পূর্ণ থ্রেডেড বাইনারি ট্রি।

সম্পূর্ণ থ্রেডেড বাইনারি ট্রির জন্য, প্রতিটি নোডে পাঁচটি ক্ষেত্র রয়েছে। সাধারণ বাইনারি ট্রি নোডের মতো তিনটি ক্ষেত্র, বুলিয়ান মান সঞ্চয় করার জন্য আরও দুটি ক্ষেত্র যাতে বোঝা যায় সেই পাশের লিঙ্কটি প্রকৃত লিঙ্ক বা থ্রেড কিনা।

এটি সম্পূর্ণ থ্রেডেড বাইনারি ট্রি

অ্যালগরিদম

inorder():
Begin
   temp := root
   repeat infinitely, do
   p := temp
   temp = right of temp
   if right flag of p is false, then
      while left flag of temp is not null, do
         temp := left of temp
      done
   end if
   if temp and root are same, then
      break
   end if
      print key of temp
   done
End

উদাহরণ

#include <iostream>
#define MAX_VALUE 65536
using namespace std;
class N { //node declaration
   public:
      int k;
      N *l, *r;
      bool leftTh, rightTh;
};
class ThreadedBinaryTree {
   private:
   N *root;
   public:
   ThreadedBinaryTree() { //constructor to initialize the variables
      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) { //move to right thread
         if (p->rightTh)
            break;
         p = p->r;
      }
      else if (p->k > key) { // move to left thread
         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() { //print the tree
   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();
   cout<<"\n";
}

আউটপুট

Threaded Binary Tree
12 20 23 30 56 85 89