BINARY TREE OPERATIONS: 1. Insert a new node (requires two functions) The public
ID: 3702051 • Letter: B
Question
BINARY TREE OPERATIONS: 1. Insert a new node (requires two functions) The public function (insertNode) should accept a new customer's name and the number of Krabby Patties they ate. This function should create a new TreeNode and fill it with these new values and then call the private function (insert). The insert function (recursive function) inserts the node in the correct position. a. b. 2. Delete a node (requires three functions) a. The public function (remove) accepts a customer's name in order to identify the node that should be removed This function prints, "You are trying to delete [name]." This function will call the private deleteNode function (a recursive function) The deleteNode function tries to find the node that needs deleted. If deleteNode finds the node, it calls the private makeDeletion function. If deleteNode does not find the node, it should print "I'm sorry. That customer can't be found in the Krusty Krab." The makeDeletion function removes the node and reattaches the branches of the tree below the node. b. c. 3. Display names of customers (requires two functions) The public function (displaylnOrder) will call the private overloaded function also called displaylnOrder. The private displaylnOrder accepts a TreeNode as an argument and it is a recursive function which traverses the nodes using the inorder method and prints the customer's name from each node. a. b. 4. Search for a customer The searchNode function accepts the customer's name as an argument and then it will look at each node (traverse the tree) to find the node with that name. If the name is found, the function returns the number of Krabby Patties that customer ate. If not, then it will return -1 instead. a.Explanation / Answer
Operations on Binary Search Tree's
A parallel tree is a double pursuit tree (BST) if and just if an inorder traversal of the paired tree brings about an arranged succession. The possibility of a twofold pursuit tree is that information is put away as per a request, so it can be recovered proficiently.
A BST is a double tree of nodes requested in the accompanying way:
Every node contains one key (additionally one of a kind)
The keys in the left subtree are < (less) than the key in its parent node
The keys in the privilege subtree > (more noteworthy) than the key in its parent node
Duplicate node keys are not permitted.
BST OPERATIONS
There are various activities on BST's that are essential to get it. We will talk about a portion of the essential activities, for example, how to embed a node into a BST, how to delete a node from a BST and how to look for a node in a BST.
Inserting a node
An innocent calculation for embeddings a node into a BST is that, we begin from the root node, if the node to embed is not as much as the root, we go to left youngster, and else we go to the correct offspring of the root. We proceed with this procedure (every node is a root for some sub tree) until the point when we locate an invalid pointer (or leaf node) where we can't go any further. We at that point embed the node as a left or right offspring of the leaf node in light of node is less or more prominent than the leaf node. We take note of that another node is constantly embedded as a leaf node. A recursive calculation for embeddings a node into a BST is as per the following. Accept we embed a node N to tree T. on the off chance that the tree is void, the we return new node N as the tree. Something else, the issue of embeddings is diminished to embeddings the node N to left of right sub trees of T, contingent upon N is less or more prominent than T. A definition is as per the following.
Insert(N, T) = N if T is vacant
= insert(N, T.left) if N < T
= insert(N, T.right) if N > T
Searching a node
Searching a node is like embeddings a node. We begin from root, and after that go left or ideal until the point when we find (or not discover the node). A recursive meaning of pursuit is as per the following.
On the off chance that the node is equivalent to root, at that point we return genuine. On the off chance that the root is invalid, at that point we return false.
Else we recursively take care of the issue for T.left or T.right, contingent upon N < T or N > T. A recursive definition is as per the following.
Search(N, T) = false if T is vacant
= genuine if T = N
= search(N, T.left) if N < T
= search(N, T.right) if N > T
Deleting a node
A BST is an associated structure. That is, all nodes in a tree are associated with some other node. For instance, every node has a parent, unless node is the root. In this manner erasing a node could influence all sub trees of that node.
Source Code
#include<stdio.h>
#include<alloc.h>
#include<conio.h>
#include<stdio.h>
struct tree
{
int data;
struct tree *l;
struct tree *r;
};
struct tree *insert(struct tree *,int);
void inorder(struct tree *);
struct tree *delet(struct tree *,int);
struct tree *search(struct tree *);
int main(void)
{
struct tree *root;
int ch, item,item_no;
root = NULL;
clrscr();
/* rear = NULL;*/
do
{
do
{
printf(" 1. Insert in Binary Tree ");
printf(" 2. Delete from Binary Tree ");
printf(" 3. Inorder traversal of Binary tree");
printf(" 4. Search and replace ");
printf(" 5. Exit ");
printf(" Enter ch : ");
scanf(" %d",&ch);
if(ch<1 || ch>7)
printf(" Invalid ch - try again");
}while (ch<1 || ch>7);
switch(ch)
{
case 1:
printf(" Enter new element: ");
scanf("%d", &item);
root= insert(root,item);
printf(" root is %d",root->data);
printf(" Inorder traversal of binary tree is : ");
inorder(root);
break;
case 2:
printf(" Enter the element to be deleted : ");
scanf(" %d",&item_no);
root=delet(root,item_no);
inorder(root);
break;
case 3:
printf(" Inorder traversal of binary tree is : ");
inorder(root);
break;
case 4:
printf(" Search and replace operation in binary tree ");
root=search(root);
break;
default:
printf(" End of program ");
} /* end of switch */
}while(ch !=5);
return(0);
}
struct tree *insert(struct tree *root, int x)
{
if(!root)
{
root=(struct tree*)malloc(sizeof(struct tree));
root->data = x;
root->l = NULL;
root->r = NULL;
return(root);
}
if(root->data > x)
root->l = insert(root->l,x);
else
{
if(root->data < x)
root->r = insert(root->r,x);
}
return(root);
}
void inorder(struct tree *root)
{
if(root != NULL)
{
inorder(root->l);
printf(" %d",root->data);
inorder(root->r);
}
return;
}
/* FUNCTION TO DELETE A NODE FROM A BINARY TREE */
struct tree *delet(struct tree *ptr,int x)
{
struct tree *p1,*p2;
if(!ptr)
{
printf(" Node not found ");
return(ptr);
}
else
{
if(ptr->data < x)
{
ptr->r = delet(ptr->r,x);
/*return(ptr);*/
}
else if (ptr->data >x)
{
ptr->l=delet(ptr->l,x);
return ptr;
}
else /* no. 2 else */
{
if(ptr->data == x) /* no. 2 if */
{
if(ptr->l == ptr->r) /*i.e., a leaf node*/
{
free(ptr);
return(NULL);
}
else if(ptr->l==NULL) /* a r subtree */
{
p1=ptr->r;
free(ptr);
return p1;
}
else if(ptr->r==NULL) /* a l subtree */
{
p1=ptr->l;
free(ptr);
return p1;
}
else
{
p1=ptr->r;
p2=ptr->r;
while(p1->l != NULL)
p1=p1->l;
p1->l=ptr->l;
free(ptr);
return p2;
}
}/*end of no. 2 if */
}/* end of no. 2 else */
/* check which path to search for a given no. */
}
return(ptr);
}
/* function to search and replace an element in the binary tree */
struct tree *search(struct tree *root)
{
int no,i,ino;
struct tree *ptr;
ptr=root;
printf(" Enter the element to be searched :");
scanf(" %d",&no);
fflush(stdin);
while(ptr)
{
if(no>ptr->data)
ptr=ptr->r;
else if(no<ptr->data)
ptr=ptr->l;
else
break;
}
if(ptr)
{
printf(" Element %d which was searched is found and is = %d",no,ptr->data);
printf(" Do you want replace it, press 1 for yes : ");
scanf(" %d",&i);
if(i==1)
{
printf(" Enter new element :");
scanf(" %d",&ino);
ptr->data=ino;
}
else
printf(" It's okay");
}
else
printf(" Element %d does not exist in the binary tree",no);
return(root);
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.