Program to implement Left-In-Threaded 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(“%dt”,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(“nn1. Insert”);
printf(“n2. Traverse Descending Order”);
printf(“n3. Exit”);
printf(“nnEnter 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();
}
}