In-Threaded-Binary Tree
Program to implement In-Threaded Binary Tree:
/*In-threaded Binary Tree*/
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
typedef struct threadedbinarytree
{
int info;
struct threadedbinarytree *left,*right;
int lflag,rflag;
}tbt;
tbt *create();
tbt *makenode(int);
tbt *insert(tbt *,tbt *);
int inorderSuccessor(tbt *,tbt *);
int inorderPredecessor(tbt *,tbt *);
void traverseInorder(tbt *);
/*Allocate memory*/
tbt *create()
{
tbt *temp=(tbt *)malloc(sizeof(tbt));
if(temp==NULL)
{printf(“nMemory Allocation Error!”);
exit(1);
}
return temp;
}
/*Make a new node*/
tbt *makenode(int x)
{
tbt *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1; /*default is thread*/
temp->rflag=1;/*default is thread*/
return temp;
}
/*Insert a newnode in the threaded tree*/
tbt *insert(tbt *root,tbt *newnode)
{
tbt *p,*temp=root;
if(root==NULL)
{root=newnode;
return root;
}
while(temp!=NULL)
{
if(newnode->info<temp->info)
{
if(temp->left)
{if(temp->lflag==1)
{
newnode->left=temp->left;
newnode->right=temp;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{newnode->left=temp->left;
temp->left=newnode;
temp->lflag=0;
newnode->right=temp;
break;
}
}
else
{if(temp->right)
{if(temp->rflag==1)
{newnode->right=temp->right;
newnode->left=temp;
temp->right=newnode;
temp->rflag=0;
newnode->rflag=1;
break;
}
else
{temp=temp->right;
}
}
else
{
p=temp->right;
temp->right=newnode;
temp->rflag=0;
newnode->right=p;
newnode->left=temp;
break;
}
}
}
return root;
}
/*Function that returns Inorder successor*/
int inorderSuccessor(tbt *root,tbt *node)
{int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{if(temp->lflag==0)
temp=temp->left;
else
temp=temp->right;
}
else if(node->info>temp->info)
{
if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*node->info==temp->info*/
{
if(temp->rflag==0)
{
p=temp->right;
while(p->lflag!=1)
p=p->left;
num=p->info;/*successor*/
break;
}
else
{
if(temp->right==NULL)
{num=0;
break;
}
else
{num=temp->right->info;
break;
}
}
}
}
return num;
}
/*Function that returns inorder predecessor*/
int inorderPredecessor(tbt *root,tbt *node)
{
int num;
tbt *p,*temp=root;
while(temp!=NULL)
{
if(node->info<temp->info)
{
if(temp->lflag==0)
temp=temp->left;
else /*move from left to right*/
temp=temp->right;
}
else if(node->info>temp->info)
{if(temp->rflag==0)
temp=temp->right;
else
{printf(“nGiven node does not exist.”);
return -1;
}
}
else/*if value is found*/
{if(temp->lflag==0)
{p=temp->left;
while(p->rflag!=1)
p=p->right;
num=p->info;/*predecssor*/
break;
}
else
{if(temp->left==NULL)
{num=0;
break;
}
else
{num=temp->left->info;
break;
}
}
}
}
return num;
}
/*Traverse in Inorder*/
void traverseInorder(tbt *root)
{tbt *temp=root;
while(temp->left)
temp=temp->left;
while(temp!=NULL)
{printf(“%dt”,temp->info);
if(temp->rflag==0)
{temp=temp->right;
while(temp->lflag==0)
temp=temp->left;
}
else
{temp=temp->right;
}
}
}
void main()
{
int x,ch,num;
tbt *node, *root=NULL;
while(1)
{
clrscr();
printf(“nMenu-In Threaded Binary Tree”);
printf(“n1. Insert”);
printf(“n2. Inorder Traversal”);
printf(“n3. Return Inorder Predecessor”);
printf(“n4. Return Inorder Successor”);
printf(“n5. Exit”);
printf(“nnEnter your choice(1 to 5)?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“nEnter the number?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseInorder(root);
break;
case 3:
printf(“nEnter the node whose predecessor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderPredecessor(root,node);
if(x!=-1)
printf(“nInorder predecessor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 4:
printf(“nEnter the node whose successor is required?”);
scanf(“%d”,&num);
node=makenode(num);
x=inorderSuccessor(root,node);
if(x!=-1)
printf(“nInorder successor of %d is %d”,node->info,x);
else
printf(“nWrong node entered.”);
break;
case 5:
exit(0);
default:
printf(“nInvalid Choice…!”);
}
getch();
}
}