A Binary tree nodes may have at most two children. But if
they have only one children, or no children, the link part in the linked list
representation remains null. Using threaded binary tree representation, we can
reuse that empty links by making some threads.
It makes inorder traversal faster and do it without stack and without recursion.
There are two types of threaded binary trees.
1. Single Threaded
Each node is threaded towards either left or right means in-order predecessor or successor. Here, all right null pointers will point to inorder successor or all left null pointers will point to inorder predecessor.
2. Double threaded
Each node is threaded towards either left and right means in-order predecessor and successor. Here, all right null pointers will point to inorder successor and all left null pointers will point to inorder predecessor.
C++ Program to implement Threaded Binary Tree
using namespace std;
struct Node
{
struct Node *left, *right;
int data;
bool lthread; //false if left pointers is a thread;
bool rthread; //false if right pointer is a thread;
};
struct Node* insert( struct Node* root, int key)
{
Node *ptr = root;
Node *parent= NULL; // parent of data to be inserted
while(ptr != NULL)
{
// if data already exists
if( ptr->data == key)
{
cout<<"Duplicate entry !\n";
return root;
}
parent = ptr; // update parent node
//moving on left subtree
if(key < ptr->data)
{
if(ptr -> lthread == false)
{
ptr = ptr -> left;
}
else
break;
}
//moving on right subtree
if(key > ptr->data)
{
if(ptr -> rthread == false)
{
ptr = ptr -> right;
}
else
break;
}
}
//creating a new node
Node *temp= new Node;
temp -> data = key;
temp -> lthread = true;
temp -> rthread = true;
if(parent == NULL)
{
root = temp;
temp -> left = NULL;
temp -> right = NULL;
}
else if(key < parent -> data )
{
temp -> left = parent -> left;
temp -> right= parent;
parent -> lthread = false;
parent -> left = temp;
}
else
{
temp -> left = parent;
temp -> right= parent -> right;
parent -> rthread = false;
parent -> right = temp ;
}
return root;
}
//returns inorder successor using rthread
struct Node *inordersuccessor (struct Node *ptr)
{
//if rthread is true, we can quickly find it
if( ptr -> rthread == true )
return ptr->right;
//else return leftmost child of right subtree
else
{
ptr = ptr -> right;
while(ptr -> lthread == false)
ptr = ptr -> left;
return ptr;
}
}
//printing inorder of threaded tree
void inorder ( struct Node *root )
{
if( root == NULL)
cout<<"Tree is empty\n";
else{
//reach leftmost Node
Node *ptr = root;
while( ptr -> lthread == false)
ptr = ptr -> left;
// print successor of each node one by one
while( ptr != NULL)
{
cout<<ptr -> data<<" ";
ptr=inordersuccessor(ptr);
}
cout<<"\n";
}
}
int main()
{
struct Node *root = NULL;
root = insert(root, 2);
root = insert(root, 10);
root = insert(root, 13);
root = insert(root, 50);
root = insert(root, 12);
root = insert(root, 14);
root = insert(root, 71);
root = insert(root, 66);
inorder(root);
return 0;
}
OUTPUT
2 10 12 13 14 50 66 71
Comments