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