Question

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:

  • Write a traversal function named traverseBST(). It takes in a pointer to a BSTNode and a BSTOrder enumerator as its parameters. This function will print out all the values in the binary search tree in the order that is determined by its BSTOrder parameter. It will recursively traverse the binary search tree and print out each value separated by a space. The traversal code is the same for all three orders, but where you print in the function depends on the order. Use the BSTOrder parameter to indicate when the print will happen.

• Create a main.c source file with the main() that will do the following:

  • Prompt the user for how many values they want to enter into the binary search tree.
  • Then, prompt the user to enter values which will then be inserted in the binary search tree. Assume that the user will also enter an integer.
  • Lastly, ask the user to enter which order they want to print their tree. For simplicity, the user will enter 0 for PREORDER, 1 for INORDER, and 2 for POSTORDER. These are default values for the enumerators. The program will then print out the binary search tree in the desired order. Assume that the user will only one of these three values for the order.
  • Deallocate your binary search tree at the end of the program.

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

Answer 1

// 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: