Implement a binary search tree of positive integers 0) in LC-3 assembly language
ID: 3920118 • Letter: I
Question
Implement a binary search tree of positive integers 0) in LC-3 assembly language. The binary search tree will be manipulated interactively using a menu system with single-letter commands: P: print the contents of the tree, in order, one per line I: insert a new value into the tree R: remove a value from the tree D: print the maximum depth of the tree Q: quit the program For the insert and remove commands, your program will need to read a positive (15-bit) hexadecimal integer value from the keyboard. Write code that will read a positive integer value from the keyboard, one digit at a time, stopping when Enter is pressed, and return it. Input validation and error checking are not required. You may either implement this as a subroutine or as a new TRAP at location x30 that will return the complete value in RO. You will also need to be able to print positive integers. Again, write either a subroutine or a TRAP at location x31 that will print the value in RO as a hexadecimal integer. The rest of the program should use subroutines appropriately. For the remove operation, you do not need to remove the node from the tree: it is enough to mark" the node as deleted and ignore it when doing other operations (this is known as "lazy deletion"). For the insert operation, each new node in the tree will be added after the last one in memory, as represented by the LAST label. This will cause the tree to grow forward in memory; the stack of course will grow in the opposite direction. You do not need to implement stack safety, but be careful when testing! Start out your tree with the data in a4q3-data.asm. You may add extra fields to the nodes, but keep those initial values and its tree structure. The nodes correspond to the following C struct struct Node short value; // though we only use unsigned values struct Node left_child, *right_child; b;Explanation / Answer
# include <stdio.h>
# include <malloc.h>
struct node
{
int info;
struct node *lchild;
struct node *rchild;
}*root;
void find(int item,struct node **par,struct node **loc)
{
struct node *ptr,*ptrsave;
if(root==NULL) /*tree empty*/
{
*loc=NULL;
*par=NULL;
return;
}
if(item==root->info) /*item is at root*/
{
*loc=root;
*par=NULL;
return;
}
/*Initialize ptr and ptrsave*/
if(item<root->info)
ptr=root->lchild;
else
ptr=root->rchild;
ptrsave=root;
while(ptr!=NULL)
{
if(item==ptr->info)
{ *loc=ptr;
*par=ptrsave;
return;
}
ptrsave=ptr;
if(item<ptr->info)
ptr=ptr->lchild;
else
ptr=ptr->rchild;
}/*End of while */
*loc=NULL; /*item not found*/
*par=ptrsave;
}/*End of find()*/
void insert(int item)
{ struct node *tmp,*parent,*location;
find(item,&parent,&location);
if(location!=NULL)
{
printf("Item already present");
return;
}
tmp=(struct node *)malloc(sizeof(struct node));
tmp->info=item;
tmp->lchild=NULL;
tmp->rchild=NULL;
if(parent==NULL)
root=tmp;
else
if(item<parent->info)
parent->lchild=tmp;
else
parent->rchild=tmp;
}/*End of insert()*/
void case_a(struct node *par,struct node *loc )
{
if(par==NULL) /*item to be deleted is root node*/
root=NULL;
else
if(loc==par->lchild)
par->lchild=NULL;
else
par->rchild=NULL;
}/*End of case_a()*/
void case_b(struct node *par,struct node *loc)
{
struct node *child;
/*Initialize child*/
if(loc->lchild!=NULL) /*item to be deleted has lchild */
child=loc->lchild;
else /*item to be deleted has rchild */
child=loc->rchild;
if(par==NULL ) /*Item to be deleted is root node*/
root=child;
else
if( loc==par->lchild) /*item is lchild of its parent*/
par->lchild=child;
else /*item is rchild of its parent*/
par->rchild=child;
}/*End of case_b()*/
void case_c(struct node *par,struct node *loc)
{
struct node *ptr,*ptrsave,*suc,*parsuc;
/*Find inorder successor and its parent*/
ptrsave=loc;
ptr=loc->rchild;
while(ptr->lchild!=NULL)
{
ptrsave=ptr;
ptr=ptr->lchild;
}
suc=ptr;
parsuc=ptrsave;
if(suc->lchild==NULL && suc->rchild==NULL)
case_a(parsuc,suc);
else
case_b(parsuc,suc);
if(par==NULL) /*if item to be deleted is root node */
root=suc;
else
if(loc==par->lchild)
par->lchild=suc;
else
par->rchild=suc;
suc->lchild=loc->lchild;
suc->rchild=loc->rchild;
}/*End of case_c()*/
int del(int item)
{
struct node *parent,*location;
if(root==NULL)
{
printf("Tree empty");
return 0;
}
find(item,&parent,&location);
if(location==NULL)
{
printf("Item not present in tree");
return 0;
}
if(location->lchild==NULL && location->rchild==NULL)
case_a(parent,location);
if(location->lchild!=NULL && location->rchild==NULL)
case_b(parent,location);
if(location->lchild==NULL && location->rchild!=NULL)
case_b(parent,location);
if(location->lchild!=NULL && location->rchild!=NULL)
case_c(parent,location);
free(location);
}/*End of del()*/
int preorder(struct node *ptr)
{
if(root==NULL)
{
printf("Tree is empty");
return 0;
}
if(ptr!=NULL)
{
printf("%d ",ptr->info);
preorder(ptr->lchild);
preorder(ptr->rchild);
}
}/*End of preorder()*/
int maxDepth(struct node* node)
{
if (node==NULL)
return 0;
else
{
/* compute the depth of each subtree */
int lDepth = maxDepth(node->left);
int rDepth = maxDepth(node->right);
/* use the larger one */
if (lDepth > rDepth)
return(lDepth+1);
else return(rDepth+1);
}
}
void inorder(struct node *ptr)
{
if(root==NULL)
{
printf("Tree is empty");
return;
}
if(ptr!=NULL)
{
inorder(ptr->lchild);
printf("%d ",ptr->info);
inorder(ptr->rchild);
}
}/*End of inorder()*/
void postorder(struct node *ptr)
{
if(root==NULL)
{
printf("Tree is empty");
return;
}
if(ptr!=NULL)
{
postorder(ptr->lchild);
postorder(ptr->rchild);
printf("%d ",ptr->info);
}
}/*End of postorder()*/
void display(struct node *ptr,int level)
{
int i;
if ( ptr!=NULL )
{
display(ptr->rchild, level+1);
printf(" ");
for (i = 0; i < level; i++)
printf(" ");
printf("%d", ptr->info);
display(ptr->lchild, level+1);
}/*End of if*/
}/*End of display()*/
main()
{
int num, depth;
char choice;
root=NULL;
while(1)
{
printf(" ");
printf("P.Print the contents of Tree in Inorder Traversal ");
printf("I.Insert a new value into the tree ");
printf("R.Remove a value from the tree ");
printf("D.Print the maximum depth of the tree ");
printf("Q.Quit ");
printf("Enter your choice : ");
scanf("%c",&choice);
switch(choice)
{
case ‘P’:
inorder(root);
break;
case ‘I’:
printf("Enter the number to be inserted : ");
scanf("%d",&num);
insert(num);
break;
case ‘R’:
printf("Enter the number to be removed : ");
scanf("%d",&num);
del(num);
break;
case ‘D’:
depth=maxDepth(root);
break;
case ‘Q’:
postorder(root);
break;
default:
printf("Wrong choice ");
}/*End of switch */
}/*End of while */
}/*End of main()*/
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.