Threaded Binary Tree

TBT - Threaded Binary Tree

In computing, a threaded binary tree is a binary tree variant that allows fast traversal: given a pointer to a node in a threaded tree, it is possible to cheaply find its in-order successor (and/or predecessor).

Below is an implementation of a TBT in C++ language.

More about TBT

C++ Code

#‎include‬ <iostream>
using namespace std;
C++-code-Threaded-Binary-Tree
C++ code -TBT
class Node{ //class definition for node
friend class Tree;
private:
int data;
Node *left,*right;
int lbit,rbit; //lbit or rbit equal to zero implies threaded child
int child; //child equal to one denotes right child
public:
Node(int data=0){ //constructor for class node
this->data=data;
lbit=rbit=0;
this->left=NULL;
this->right=NULL;
child=0;//by default left child
}
};
class Tree{ //class definition for TBT
public:
Node *headnode;
Tree(){ //constructor
headnode=new Node(0);
headnode->lbit=0;
headnode->rbit=1;
headnode->left=headnode->right=headnode;
}

void create(Node *p,int child){ //to create a threaded binary tree. First call is (root,0)
//DFS creation using recursion,similar to preorder
cout<<"Enter data for the node(-1 for no data)"<<endl;
int x;
cin>>x;
if(x==-1)
return;
Node *temp=new Node(x);
if(child==0){
temp->child=0;
temp->lbit=p->lbit;
temp->left=p->left;
p->left=temp;
p->lbit=1;
temp->rbit=0;
temp->right=p;
}
else{

temp->child=1;
temp->rbit=p->rbit;
temp->right=p->right;
temp->lbit=0;
temp->left=p;
p->right=temp;
p->rbit=1;
}
cout<<"Enter the left child of "<<x<<endl;
create(temp,0);
cout<<"Enter the right child of "<<x<<endl;
create(temp,1);
}

Node* insuc(Node *p){ //traversal is left root right
if(p->rbit==0)
return p->right; //threaded right link points to inorder successor

p=p->right;
while(p->lbit==1)
p=p->left;

return p;
}

Node* presuc(Node *p){ //traversal is left right root
if(p->lbit==1)
return p->left;
while(p->rbit==0)
p=p->right;
return p->right;
}
Node* postsuc(Node *p){ //traversal is left right root
if(p->child==1){ //if p is a right child
while(p->lbit==1)
p=p->left;
return p->left;
}
while(p->rbit==1)//p is a left child
p=p->right;
p=p->right;
if(p->rbit==0)
return p;
p=p->right; //ENTER THE RIGHT SUBTREE
while(p->lbit==1||p->rbit==1){
if(p->lbit==1)
p=p->left;
else
p=p->right;
}
return p;
}
void inorder(){
Node *p=headnode;
while(p->lbit==1)
p=p->left;
while(p!=headnode){
cout<<p->data<<"\t";
p=insuc(p);
}
}
void preorder(){
Node *p=headnode;
p=p->left;
while(p!=headnode){
cout<<p->data<<"\t";
p=presuc(p);
}
}
void postorder(){
Node *p=headnode;
while(p->lbit==1||p->rbit==1){
if(p->lbit==1)
p=p->left;
else
p=p->right;
}
while(p!=headnode->left){
cout<<p->data<<"\t";
p=postsuc(p);
}
cout<<p->data;
}
};
int main() {
cout<<"Program for TBT traversal"<<endl;
Tree a;
int choice;
a.create(a.headnode,0);
cout<<"Tree has been created"<<endl;
while(true){
cout<<"\nEnter your choice"<<endl;
cout<<"1.In-order 2.Pre-order 3.Post-order 4.Exit"<<endl;
cin>>choice;
switch(choice){
case 1:
a.inorder();
break;
case 2:
a.preorder();
break;
case 3:
a.postorder();
break;
case 4:
cout<<"Terminating Program\n"<<endl;
break;
default:
cout<<"Invalid choice\n"<<endl;
}
if(choice==4)
break;
}
//cout << "Threaded binary tree" << endl; // prints Threaded binary tree
return 0;
}

Output

Program for TBT traversal
Enter data for the node(-1 for no data)
20
Enter the left child of 20
Enter data for the node(-1 for no data)
50
Enter the left child of 50
Enter data for the node(-1 for no data)
-1
Enter the right child of 50
Enter data for the node(-1 for no data)
90
Enter the left child of 90
Enter data for the node(-1 for no data)
5
Enter the left child of 5
Enter data for the node(-1 for no data)
-1
Enter the right child of 5
Enter data for the node(-1 for no data)
-1
Enter the right child of 90
Enter data for the node(-1 for no data)
6
Enter the left child of 6
Enter data for the node(-1 for no data)
-1
Enter the right child of 6
Enter data for the node(-1 for no data)
-1
Enter the right child of 20
Enter data for the node(-1 for no data)
60
Enter the left child of 60
Enter data for the node(-1 for no data)
8
Enter the left child of 8
Enter data for the node(-1 for no data)
-1
Enter the right child of 8
Enter data for the node(-1 for no data)
-1
Enter the right child of 60
Enter data for the node(-1 for no data)
100
Enter the left child of 100
Enter data for the node(-1 for no data)
80
Enter the left child of 80
Enter data for the node(-1 for no data)
-1
Enter the right child of 80
Enter data for the node(-1 for no data)
-1
Enter the right child of 100
Enter data for the node(-1 for no data)
-1
Tree has been created
Enter your choice
1.In-order 2.Pre-order 3.Post-order 4.Exit
1
50 5 90 6 20 8 60 80 100
Enter your choice
1.In-order 2.Pre-order 3.Post-order 4.Exit
2
20 50 90 5 6 60 8 100 80
Enter your choice
1.In-order 2.Pre-order 3.Post-order 4.Exit
3
5 6 90 50 8 80 100 60 20
Enter your choice
1.In-order 2.Pre-order 3.Post-order 4.Exit
4
Terminating Program