PLEASE DO THIS IN C programming language. Do not SOLVE THIS IN C++ You will use

Question

PLEASE DO THIS IN C programming language. Do not SOLVE THIS IN C++

You will use the following structure to implement a binary search tree:

You will write the following functions:

This function will create a new node having the specified value and return it. The steps are:

call malloc to create the new node, assigning it to a Node* variable called node.

Assign the value of the int value parameter to node->value.

Assign NULL to left.

Assign NULL to right.

return node.

This function returns the node in the tree with the smallest value. The steps are:

Assign tree to a Node* variable called current.

while current->left is not null, set current to current->left.

return current.

This recursive function will insert a new node into the tree and return it. The steps are:

if tree is NULL, call your Create function with the specified value and return the resulting node.

if the specified value is less than tree->left, call Insert with tree->left and the specified value.

else if the specified value is greater than tree->right, call Insert with tree->right and the specified value.

return tree.

This recursive function will delete the specified node from the specified tree. The steps are:

If tree is NULL, return NULL.

if value is less than tree-> value, call Delete with tree->left and value as parameters, and assign the result to tree->left.

else if value is greater than tree->value, call Delete with tree->right and value as parameters, and assign the result to tree->right.

else {

if tree->left is null, assign tree->right to a temp variable, call free(tree), and return temp.

else if tree ->right is null, assign tree->left to a temp variable, call free(tree), and return temp.

declare a Node* min variable, and call your Min function with tree->right as the parameter, assigning the return value to min.

assign min->value to tree->value.

call Delete, passing tree->right and min->right as parameters, and assign the result to tree->right. }

return tree.

This recursive function finds the node in the tree with the specified value. The steps are:

if tree is NULL or tree->value equals value, return tree.

if value is less than tree->value, return the result of calling Find using tree->left and value as parameters.

return the result of calling Find using tree->right and value as parameters.

Prints the tree in alphabetical order. The steps are:

if list is NULL, return NULL.

call Print using tree>left as the parameter.

print tree->value, followed by a space, to stdout.

call Print using tree>right as the parameter.

Explanation / Answer

The code in given in c language as per your requirement with comments so please thumbs up and if you have any doubts please comment, Thank You

Code:

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

typedef struct node
{
int data;
struct node *left;
struct node *right;

}node;

node* FindMin(node *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
if(node->left) /* Go to the left sub tree to find the min element */
return FindMin(node->left);
else
return node;
}
node* FindMax(node *node)
{
if(node==NULL)
{
/* There is no element in the tree */
return NULL;
}
if(node->right) /* Go to the left sub tree to find the min element */
FindMax(node->right);
else
return node;
}

node * Insert(node *node,int data)
{
if(node==NULL)
{
node *temp;
temp = (node *)malloc(sizeof(node));
temp -> data = data;
temp -> left = temp -> right = NULL;
return temp;
}

if(data >(node->data))
{
node->right = Insert(node->right,data);
}
else if(data < (node->data))
{
node->left = Insert(node->left,data);
}
/* Else there is nothing to do as the data is already in the tree. */
return node;

}

node * Delete(node *node, int data)
{
node *temp;
if(node==NULL)
{
printf("Element Not Found");
}
else if(data < node->data)
{
node->left = Delete(node->left, data);
}
else if(data > node->data)
{
node->right = Delete(node->right, data);
}
else
{
/* Now We can delete this node and replace with either minimum element
in the right sub tree or maximum element in the left subtree */
if(node->right && node->left)
{
/* Here we will replace with minimum element in the right sub tree */
temp = FindMin(node->right);
node -> data = temp->data;
/* As we replaced it with some other node, we have to delete that node */
node -> right = Delete(node->right,temp->data);
}
else
{
/* If there is only one or zero children then we can directly
remove it from the tree and connect its parent to its child */
temp = node;
if(node->left == NULL)
node = node->right;
else if(node->right == NULL)
node = node->left;
free(temp); /* temp is longer required */
}
}
return node;

}

node * Find(node *node, int data)
{
if(node==NULL)
{
/* Element is not found */
return NULL;
}
if(data > node->data)
{
/* Search in the right sub tree. */
return Find(node->right,data);
}
else if(data < node->data)
{
/* Search in the left sub tree. */
return Find(node->left,data);
}
else
{
/* Element Found */
return node;
}
}

void PrintInorder(node *node)
{
if(node==NULL)
{
return;
}
PrintInorder(node->left);
printf("%d ",node->data);
PrintInorder(node->right);
}

void PrintPreorder(node *node)
{
if(node==NULL)
{
return;
}
printf("%d ",node->data);
PrintPreorder(node->left);
PrintPreorder(node->right);
}

void PrintPostorder(node *node)
{
if(node==NULL)
{
return;
}
PrintPostorder(node->left);
PrintPostorder(node->right);
printf("%d ",node->data);
}

int main()
{
node *root = NULL;
root = Insert(root, 5);
root = Insert(root, -1);
root = Insert(root, 3);
root = Insert(root, -14);
root = Insert(root, 8);
root = Insert(root, 10);
root = Insert(root, 9);
root = Insert(root, 6);
PrintInorder(root);
printf(" ");
root = Delete(root,5);
root = Delete(root,-1);
PrintInorder(root);
printf(" ");
node * temp;
temp = FindMin(root);
printf("Minimum element is %d ",temp->data);
temp = FindMax(root);
printf("Maximum element is %d ",temp->data);
temp = Find(root,8);
if(temp==NULL)
{
printf("Element 8 not found ");
}
else
{
printf("Element 8 Found ");
}
temp = Find(root,2);
if(temp==NULL)
{
printf("Element 2 not found ");
}
else
{
printf("Element 6 Found ");
}
}

Hope this Helps

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.