थ्रेडेड बाइनरी ट्री एक बाइनरी ट्री है जो एक विशेष क्रम में पेड़ को पार करने की सुविधा प्रदान करता है।
यह इनऑर्डर ट्रैवर्सल को तेजी से बनाता है और बिना स्टैक और बिना रिकर्सन के करता है। थ्रेडेड बाइनरी ट्री दो प्रकार के होते हैं।
एकल थ्रेडेड प्रत्येक नोड को या तो बाएँ या दाएँ अर्थ क्रम में पूर्ववर्ती या उत्तराधिकारी की ओर पिरोया जाता है। यहां, सभी दाएं नल पॉइंटर्स इनऑर्डर उत्तराधिकारी को इंगित करेंगे या सभी बाएं नल पॉइंटर्स इनऑर्डर पूर्ववर्ती को इंगित करेंगे।
डबल थ्रेडेड प्रत्येक नोड को बाएँ और दाएँ अर्थ में क्रम में पूर्ववर्ती और उत्तराधिकारी की ओर पिरोया गया है। यहां, सभी राइट नल पॉइंटर्स इनऑर्डर उत्तराधिकारी को इंगित करेंगे और सभी बाएं नल पॉइंटर्स इनऑर्डर पूर्ववर्ती को इंगित करेंगे।
यह थ्रेडेड बाइनरी ट्री को लागू करने के लिए एक C++ प्रोग्राम है।
कार्य और छद्म कोड
फ़ंक्शन इंसर्ट ()
Insert node as root if tree is completely empty. Otherwise, if newnode < current node then Go to left thread and set the newnode as left child. else Go to right thread and set the newnode as right child.
फ़ंक्शन खोज ()
If search key < root then Go to left thread else Go to right thread
फंक्शन डिलीट ()
नोड और उसके माता-पिता का पता लगाएं। नोड को हटाने के लिए तीन मामले हैं -
- नोड जिसके दो बच्चे हैं।
- केवल बच्चा बचा है।
- केवल सही बच्चा है।
उदाहरण
#include <iostream>
#include <cstdlib>
#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 makeEmpty() { //clear tree
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;
}
}
bool search(int key) {
N *temp = root->l;
for (;;) {
if (temp->k < key) { //search in left thread
if (temp->rightTh)
return false;
temp = temp->r;
} else if (temp->k > key) { //search in right thread
if (temp->leftTh)
return false;
temp = temp->l;
} else {
return true;
}
}
}
void Delete(int key) {
N *dest = root->l, *p = root;
for (;;) { //find Node and its parent.
if (dest->k < key) {
if (dest->rightTh)
return;
p = dest;
dest = dest->r;
} else if (dest->k > key) {
if (dest->leftTh)
return;
p = dest;
dest = dest->l;
} else {
break;
}
}
N *target = dest;
if (!dest->rightTh && !dest->leftTh) {
p = dest; //has two children
target = dest->l; //largest node at left child
while (!target->rightTh) {
p = target;
target = target->r;
}
dest->k= target->k; //replace mode
}
if (p->k >= target->k) { //only left child
if (target->rightTh && target->leftTh) {
p->l = target->l;
p->leftTh = true;
} else if (target->rightTh) {
N*largest = target->l;
while (!largest->rightTh) {
largest = largest->r;
}
largest->r = p;
p->l= target->l;
} else {
N *smallest = target->r;
while (!smallest->leftTh) {
smallest = smallest->l;
}
smallest->l = target->l;
p->l = target->r;
}
} else {//only right child
if (target->rightTh && target->leftTh) {
p->r= target->r;
p->rightTh = true;
} else if (target->rightTh) {
N *largest = target->l;
while (!largest->rightTh) {
largest = largest->r;
}
largest->r= target->r;
p->r = target->l;
} else {
N *smallest = target->r;
while (!smallest->leftTh) {
smallest = smallest->l;
}
smallest->l= p;
p->r= target->r;
}
}
}
void displayTree() { //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<<"ThreadedBinaryTree\n";
char ch;
int c, v;
while(1) {
cout<<"1. Insert "<<endl;
cout<<"2. Delete"<<endl;
cout<<"3. Search"<<endl;
cout<<"4. Clear"<<endl;
cout<<"5. Display"<<endl;
cout<<"6. Exit"<<endl;
cout<<"Enter Your Choice: ";
cin>>c;
//perform switch operation
switch (c) {
case 1 :
cout<<"Enter integer element to insert: ";
cin>>v;
tbt.insert(v);
break;
case 2 :
cout<<"Enter integer element to delete: ";
cin>>v;
tbt.Delete(v);
break;
case 3 :
cout<<"Enter integer element to search: ";
cin>>v;
if (tbt.search(v) == true)
cout<<"Element "<<v<<" found in the tree"<<endl;
else
cout<<"Element "<<v<<" not found in the tree"<<endl;
break;
case 4 :
cout<<"\nTree Cleared\n";
tbt.makeEmpty();
break;
case 5:
cout<<"Display tree: \n ";
tbt.displayTree();
break;
case 6:
exit(1);
default:
cout<<"\nInvalid type! \n";
}
}
cout<<"\n";
return 0;
} आउटपुट
ThreadedBinaryTree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 10 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 7 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 6 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 4 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 5 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 1 Enter integer element to insert: 3 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 3 4 5 6 7 10 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 3 Enter integer element to search: 7 Element 7 found in the tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 3 Enter integer element to search: 1 Element 1 not found in the tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 2 Enter integer element to delete: 3 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 4 5 6 7 10 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 4 Tree Cleared 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 5 Display tree 1. Insert 2. Delete 3. Search 4. Clear 5. Display 6. Exit Enter Your Choice: 6