In this lab, you will write a program that creates a binary search tree based on user input. Then, the user will indicate what order to print the values in. **Please write in C code**
Start with the bst.h and bst.c base code provided to you. You will need to modify the source and header file to complete this lab.
bst.h:
#ifndef BST_H
#define BST_H
typedef struct BSTNode
{
int value;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
BSTNode* insert( BSTNode*, BSTNode* );
BSTNode* create( int );
BSTNode* find( BSTNode*, int );
BSTNode* removeNode( BSTNode*, int );
BSTNode* deleteBST( BSTNode* );
void print( BSTNode* );
#endif
bst.c:
#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
/*
Function: create
-------------------
This function creates a new BSTNode.
v: the value to be addeded to the tree
Returns: New node for a Binary Search Tree
*/
BSTNode* create( int v )
{
BSTNode* n = (BSTNode*) malloc( sizeof( BSTNode ) );
n->value = v;
n->left = NULL;
n->right = NULL;
return n;
}
/*
Function: insert
-------------------
This function inserts a new BSTNode.
r: root of current subtree
n: node to be inserted
Returns: Root a Binary Search Tree
*/
BSTNode* insert( BSTNode* r, BSTNode* n )
{
/* once we find an empty spot, return the new node
*/
if( r == NULL )
{
return n;
}
/* searching left or right child depending on value */
if( n->value <= r->value )
{
r->left = insert( r->left, n );
}
else
{
r->right = insert( r->right, n );
}
/* return the root of the current subtree */
return r;
}
void print( BSTNode* r )
{
if( r == NULL )
{
return;
}
print( r->left );
printf( "%d\t", r->value );
print( r->right );
}
/*
Function: deleteBST
-------------------
This function deallocates all the nodes in the BST
r: root of the tree/subtree
Returns: NULL
*/
BSTNode* deleteBST( BSTNode* r )
{
/* base case for the traversal portion of the destruct function
*/
if( r == NULL )
{
return NULL;
}
/* these recursive calls simply traverse the tree and stops at the
base case
which is when it reaches a leaf node */
deleteBST( r->left );
deleteBST( r->right );
/* if we reach here, r is a leaf, so free it */
free( r );
return NULL;
}
/*
Function: find
-------------------
This function finds if a key value exists in a binary search
tree.
root: root of the tree/subtree
key: key value we are looking for
Returns: pointer to the node in which the value x was found
*/
BSTNode* find( BSTNode* root, int key )
{
/* if root is null: no tree or reached past a leaf
*/
if( root == NULL )
{
return NULL;
}
/* if key value was found */
if( root->value == key )
{
return root;
}
/* if the key value is actually less than the current root *
search to the left child; otherwise, search to the right child
*/
if( root->value > key )
return find( root->left, key );
else
return find( root->right, key );
}
/*
Function: removeNode
-------------------
This function removes a node with a specific value in a binary
search tree.
root: root of the tree/subtree
key: key value we are looking for that will be removed
Returns: root of the tree/subtree
*/
BSTNode* removeNode( BSTNode* root, int key )
{
/* if root is null: no tree or reached past a leaf
*/
if( root == NULL )
{
return NULL;
}
/* if key value is less than the current root's value,
search to left */
if( root->value > key )
{
root->left = removeNode( root->left, key );
}
/* if key value is greater than the current root's
value, search to right */
else if( root->value < key )
{
root->right = removeNode( root->right, key );
}
/* if the value was found */
else if( root->value == key )
{
/* the following if statements check the current
root's descendents.
there is a different set of actions depending.
*/
if( root->left == NULL && root->right == NULL )
{
free( root );
return NULL;
}
/* right child exists, but left does not */
if( root->left == NULL )
{
BSTNode *right = root->right;
free( root );
return right;
}
/* left child exists, but left right not */
if( root->right == NULL )
{
BSTNode *left = root->left;
free( root );
return left;
}
/* the root (the node) to be removed) gets the values of the
replacement
node */
BSTNode* t = root->right;
for( t = root->right; t != NULL && t->left != NULL; t
= t->left );
/* copy values */
root->value = t->value;
/* remove the actual successor node */
root->right = removeNode( root->right, t->value );
}
return root;
}
Add the following enum named BSTOrder which will create enumerators for each of the three BST orders. The enumerators are PREORDER, INORDER, and POSTORDER. Do not change the ordering of these enumerators in your declaration.
Add the following function to your source file along with its prototype in the header file:
Create a main.c source file with the main() that will do the following:
Example Output (the final line's values are actually separated by tabs).
How many nodes? 7 Enter a node value: 60 Enter a node value: 30 Enter a node value: 20 Enter a node value: 50 Enter a node value: 80 Enter a node value: 90 Enter a node value: 70 What order? 2 20 30 50 70 80 90 60
Compile command:
gcc bst.c main.c -Wall -o a.out -lm
// bst.h
#ifndef BST_H
#define BST_H
// enumerators for each of the three BST orders
typedef enum BSTOrder
{
PREORDER,
INORDER,
POSTORDER
}BSTOrder;
typedef struct BSTNode
{
int value;
struct BSTNode* left;
struct BSTNode* right;
} BSTNode;
BSTNode* insert( BSTNode*, BSTNode* );
BSTNode* create( int );
BSTNode* find( BSTNode*, int );
BSTNode* removeNode( BSTNode*, int );
BSTNode* deleteBST( BSTNode* );
void print( BSTNode* );
void traverseBST(BSTNode*, BSTOrder);
#endif
//end of bst.h
// bst.c
#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
/*
Function: create
-------------------
This function creates a new BSTNode.
v: the value to be addeded to the tree
Returns: New node for a Binary Search Tree
*/
BSTNode* create( int v )
{
BSTNode* n = (BSTNode*) malloc( sizeof( BSTNode ) );
n->value = v;
n->left = NULL;
n->right = NULL;
return n;
}
/*
Function: insert
-------------------
This function inserts a new BSTNode.
r: root of current subtree
n: node to be inserted
Returns: Root a Binary Search Tree
*/
BSTNode* insert( BSTNode* r, BSTNode* n )
{
/* once we find an empty spot, return the new node */
if( r == NULL )
{
return n;
}
/* searching left or right child depending on value */
if( n->value <= r->value )
{
r->left = insert( r->left, n );
}
else
{
r->right = insert( r->right, n );
}
/* return the root of the current subtree */
return r;
}
void print( BSTNode* r )
{
if( r == NULL )
{
return;
}
print( r->left );
printf( "%d\t", r->value );
print( r->right );
}
/*
Function: deleteBST
-------------------
This function deallocates all the nodes in the BST
r: root of the tree/subtree
Returns: NULL
*/
BSTNode* deleteBST( BSTNode* r )
{
/* base case for the traversal portion of the destruct function
*/
if( r == NULL )
{
return NULL;
}
/* these recursive calls simply traverse the tree and stops at
the base case
which is when it reaches a leaf node */
deleteBST( r->left );
deleteBST( r->right );
/* if we reach here, r is a leaf, so free it */
free( r );
return NULL;
}
/*
Function: find
-------------------
This function finds if a key value exists in a binary search
tree.
root: root of the tree/subtree
key: key value we are looking for
Returns: pointer to the node in which the value x was found
*/
BSTNode* find( BSTNode* root, int key )
{
/* if root is null: no tree or reached past a leaf */
if( root == NULL )
{
return NULL;
}
/* if key value was found */
if( root->value == key )
{
return root;
}
/* if the key value is actually less than the current root
*
search to the left child; otherwise, search to the right child
*/
if( root->value > key )
return find( root->left, key );
else
return find( root->right, key );
}
/*
Function: removeNode
-------------------
This function removes a node with a specific value in a binary
search tree.
root: root of the tree/subtree
key: key value we are looking for that will be removed
Returns: root of the tree/subtree
*/
BSTNode* removeNode( BSTNode* root, int key )
{
/* if root is null: no tree or reached past a leaf */
if( root == NULL )
{
return NULL;
}
/* if key value is less than the current root's value, search to
left */
if( root->value > key )
{
root->left = removeNode( root->left, key );
}
/* if key value is greater than the current root's value, search
to right */
else if( root->value < key )
{
root->right = removeNode( root->right, key );
}
/* if the value was found */
else if( root->value == key )
{
/* the following if statements check the current root's
descendents.
there is a different set of actions depending. */
if( root->left == NULL && root->right == NULL )
{
free( root );
return NULL;
}
/* right child exists, but left does not */
if( root->left == NULL )
{
BSTNode *right = root->right;
free( root );
return right;
}
/* left child exists, but left right not */
if( root->right == NULL )
{
BSTNode *left = root->left;
free( root );
return left;
}
/* the root (the node) to be removed) gets the values of the
replacement
node */
BSTNode* t = root->right;
for( t = root->right; t != NULL && t->left != NULL; t
= t->left );
/* copy values */
root->value = t->value;
/* remove the actual successor node */
root->right = removeNode( root->right, t->value );
}
return root;
}
/*
* Function traverseBST
* --------------------
* This function traverses and displays the nodes of the tree in the
input order.
* It will recursively traverse the binary search tree and print out
each value separated by a space.
* node - BSTNode pointer to a node of the tree
* order - enumerator containing the order the nodes must be
displayed
*/
void traverseBST(BSTNode* node, BSTOrder order)
{
// validate node is not null
if(node != NULL)
{
// pre-order traversal
if(order == PREORDER)
{
printf("%d ",node->value); // display the node's value
traverseBST(node->left, order); // apply traversalBST on the
left subtree of node
traverseBST(node->right, order); // apply traversalBST on the
right subtree of node
}
else if(order == INORDER) // in-order traversal
{
traverseBST(node->left, order); // apply traversalBST on the
left subtree of node
printf("%d ",node->value); // display the node's value
traverseBST(node->right, order); // apply traversalBST on the
right subtree of node
}
else
{
// post-order traversal
traverseBST(node->left, order); // apply traversalBST on the
left subtree of node
traverseBST(node->right, order); // apply traversalBST on the
right subtree of node
printf("%d ",node->value); // display the node's value
}
}
}
//end of bst.c
// main.c : C program to implement the BST
#include <stdio.h>
#include <stdlib.h>
#include "bst.h"
int main()
{
int n, value, i, order;
BSTNode *root = NULL; // create an empty tree
// input of number of nodes to create
printf("How many nodes? ");
scanf("%d",&n);
// loop to input n node values (integers)
for(i=0;i<n;i++)
{
printf("Enter a node value: ");
scanf("%d",&value);
root = insert(root, create(value)); // insert value into the
tree
}
// input of traversal order
printf("What order? ");
scanf("%d",&order);
if(order == 0) // pre-order
traverseBST(root, PREORDER);
else if(order == 1) // in-order
traverseBST(root, INORDER);
else if(order == 2) // post-order
traverseBST(root, POSTORDER);
else
printf("Invalid order input");
// Deallocate the binary search tree nodes
deleteBST(root);
return 0;
}
//end of main.c
Output:
Get Answers For Free
Most questions answered within 1 hours.