Program to implement Left-In- And Right-InThreaded Binary Tree

Left-In-Threaded Binary Tree

Program to implement Left-In-Threaded Binary Tree:

/*Left In Threaded Binary Tree*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int lflag;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
void traverseDescending(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->lflag=1;/*1 for thread,0 for link*/
return temp;
}

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;
temp->left=newnode;
temp->lflag=0;
break;
}
else
temp=temp->left;
}
else
{temp->left=newnode;
temp->lflag=0;
break;
}
}
else
{if(temp->right)
temp=temp->right;
else
{
temp->right=newnode;
newnode->left=temp;
newnode->lflag=1;
break;
}
}
}
return root;
}

void traverseDescending(TBT *root)
{
TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->right;
}
printf(“%d\t”,temp->info);
if((temp->lflag==1) && (temp->left==NULL))
return;
if(temp->lflag==1)
temp=temp->left;
else
p=temp->left;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“\nMenu- Right-in-Threaded Binary Tree”);
printf(“\n\n1. Insert”);
printf(“\n2. Traverse Descending Order”);
printf(“\n3. Exit”);
printf(“\n\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
traverseDescending(root);
break;
case 3:
exit(0);
default:
printf(“\nChoice is invalid.”);
}
getch();
}
}

Program to implement Right-In-Threaded Binary Tree

Right-In-Threaded Binary Tree

Program to implement Right-In-Threaded Binary Tree:

/*Right In Threaded Binary Tree*/

#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

typedef struct threadedbinarytree
{int info;
struct threadedbinarytree *left,*right;
int rlink;
}TBT;

TBT *create();
TBT *makenode(int);
TBT *insert(TBT *,TBT *);
/*inorder or symmetric order*/
void inorder(TBT *);
/*Depth first order*/
void preorder(TBT *);

TBT *create()
{
TBT *temp=(TBT *)malloc(sizeof(TBT));
if(temp==NULL)
{printf(“Memory Allocation Error!”);
exit(1);
}
return temp;
}

TBT *makenode(int x)
{TBT *temp=create();
temp->info=x;
temp->left=NULL;
temp->right=NULL;
temp->rlink=1;/*1 for thread,0 for link*/
return temp;
}

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)
temp=temp->left;
else
{temp->left=newnode;
newnode->left=NULL;
newnode->right=temp;
newnode->rlink=1; /*set during making node*/
break;
}
}
else
{if(temp->right)
{if(temp->rlink==1)
{
newnode->right=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->rlink=1;/*set during making node*/
break;
}
else
temp=temp->right;
}
else
{p=temp->right;
temp->right=newnode;
temp->rlink=0;
newnode->left=NULL;
newnode->right=p;
newnode->rlink=1;
break;
}
}
}
return root;
}

void preorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
printf(“%d\t”,p->info);
p=p->left;
}
if((temp->rlink==1)&&(temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right->right;
else
temp=temp->right;
p=temp;
}
}

void inorder(TBT *root)
{TBT *p,*temp=root;
p=root;
while(temp!=NULL)
{while(p!=NULL)
{temp=p;
p=p->left;
}
printf(“%d\t”,temp->info);
if((temp->rlink==1) && (temp->right==NULL))
return;
if(temp->rlink==1)
temp=temp->right;
else
p=temp->right;
}
}

void main()
{
int x,ch;
TBT *node,*root=NULL;
while(1)
{
clrscr();
printf(“\nMenu- Right-in-Threaded Binary Tree”);
printf(“\n\n1. Insert”);
printf(“\n2. Traverse inorder”);
printf(“\n3. Traverse preorder”);
printf(“\n4. Exit”);
printf(“\n\nEnter your choice?”);
scanf(“%d”,&ch);
switch(ch)
{
case 1:
printf(“Enter number to insert?”);
scanf(“%d”,&x);
node=makenode(x);
root=insert(root,node);
break;
case 2:
inorder(root);
break;
case 3:
preorder(root);
break;
case 4:
exit(0);
default:
printf(“\nChoice is invalid.”);
}
getch();
}
}

Program to implement In-Threaded Binary Tree

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(“%d\t”,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(“\n\nEnter 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();
}
}