Files provided in the project 1) BinansearchTreeh. This file contains the struct
ID: 3605973 • Letter: F
Question
Files provided in the project 1) BinansearchTreeh. This file contains the structs needed for the BinarySearchTree as well as the prototypes for several functions that you will need to implement. In particular you need to implement the following functions in the file BinarySearchTree newBinarySearchTree) which should allocate the memory for a new binary search tree, initialize the variables, and return the address. a. b. void Tree tree) which should free the tree (including any nodes currently in the tree). NodeT .allocateNode(Element value) which should allocate memory for a new node, store "value" inside this node, and return the address of the node NodeT *search(NodeT *p, int searchValue) which should recursively search the subtree rooted at p for a node containing a key value equal to searchValue. If such a node exists, return a pointer to the node. If no such node exists, return NULL Note that to search the entire tree, we would cal this function with search(tree->pRoot, searchValue). int insert(BinarySearchTree tree, Element value) which will insert a node with the element value into the tree as a leaf node if it does not already exist in the tree. If the node is inserted then return true. If the node already exists, return false void printinOrder(NodeT·P) which will recursively print the values of the nodes in the tree in increasing order. We would call this function with c. d. e. f, g void printPreOrder(NodeT p) which will recursively print the values of the nodes in the tree according to a preorder traversal (discussed in class on Thursday). We would call this function with printPreOrder(tree->pRoot). 2) p4input.txt. This file contains a sample input file that you should process. Each line will contain either INSERT X, SEARCH X, PRINT INORDER, or PRINT PREORDER If the line contains INSERT X, then you should insert a new node into the binary search tree containing the value X If the value inserted correctly, print Inserted X into tree". If the node was already in the tree, print "X already is in the tree". If the line contains SEARCH X, you should search the tree for a node containing X. Print"Found X" if it exists and print "X notin tree" if it does not exist.the line contains PRINT INORDER or PRINT PREORDER then print the contents of the tree with an inorder traversal or a preorder traversal respectively 3) abc123p4.c. Rename this file to your abc123. This file is mostly empty right now. It contains the main) function that you should complete. In main, you should create a new BinarySearchTree, read a line from p4input.txt (you can do this however you would like), and perform the appropriate operation on the tree. 5) Makefile. Update the makefile to reflect your abc123. Compile using make p4. Execute the program using /p4p4input.txtExplanation / Answer
HI,
I have made all the required function in c for you.
You can use and include them in your desired c file in your desired order.
Also, I have commented the answer so that code is easy to understand!
//Program to create new binary search tree
#include<stdio.h>
#include<stdlib.h>
struct binarySearchTree
{
int key;
struct binarySearchTree *left, *right;
};
/* Given a binary search tree and a key, this function deletes the key
and returns the new root */
struct binarySearchTree* freeBinarySearchTree(struct binarySearchTree* root, int key)
{
// base case
if (root == NULL) return root;
// If the key to be deleted is smaller than the root's key,
// then it lies in left subtree
if (key < root->key)
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater than the root's key,
// then it lies in right subtree
else if (key > root->key)
root->right = deleteNode(root->right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root->left == NULL)
{
struct node *temp = root->right;
free(root);
return temp;
}
else if (root->right == NULL)
{
struct node *temp = root->left;
free(root);
return temp;
}
// node with two children: Get the inorder successor (smallest
// in the right subtree)
struct node* temp = minValueNode(root->right);
// Copy the inorder successor's content to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right, temp->key);
}
return root;
}
// A utility function to create a new BST node
struct binarySearchTree *allocateNode(int value)
{
struct binarySearchTree *temp = (struct binarySearchTree *)malloc(sizeof(struct binarySearchTree));
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// C Program to search a given key in a given BST
struct binarySearchTree* search(struct binarySearchTree* root, int searchValue)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->key == key)
return root;
// Key is greater than root's key
if (root->key < key)
return search(root->right, key);
// Key is smaller than root's key
return search(root->left, key);
}
// C program to demonstrate insert operation in binary search tree
struct binarySearchTree* insert(struct binarySearchTree* node, int value)
{
/* If the tree is empty, return a new node */
if (node == NULL) return newNode(key);
/* Otherwise, recur down the tree */
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
/* return the (unchanged) node pointer */
return node;
}
// A C program to do inorder traversal of BST
void printInorder(struct binarySearchTree *root)
{
if (root != NULL)
{
printInorder(root->left);
printf("%d ", root->key);
printInorder(root->right);
}
}
/* Given a binary tree, print its nodes in preorder*/
void printPreorder(struct binarySearchOrder* node)
{
if (node == NULL)
return;
/* first print data of node */
printf("%d ", node->data);
/* then recur on left sutree */
printPreorder(node->left);
/* now recur on right subtree */
printPreorder(node->right);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.