Question

In this lab, you will write a program that creates a binary search tree based on...

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

Homework Answers

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:

Know the answer?
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for?
Ask your own homework help question
Similar Questions
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class...
The Binary Search Tree implementation for bst.zip. The code in the destructor of the BST class is empty. Complete the destructor so the memory allocated for each node in the BST is freed. Make a couple of different trees in your main method or in a function to test the destructor (the program should not crash upon exiting). bst.zip (includes the following files below in c++): bst.h: #pragma once #include #include "node.cpp" using namespace std; template class BST { public:...
1. Assume the key of the right child below the root node of a binary search...
1. Assume the key of the right child below the root node of a binary search tree is 40. The value in the root node could be ________. 2. On average, searching for an item in a balanced binary search tree is _________ operation. 3. Where is the inorder successor of a node A in a binary search tree?
do a code trace on how a key gets deleted package interview; import java.util.*; public class...
do a code trace on how a key gets deleted package interview; import java.util.*; public class binarySearchTree { Node root; void insert(int key) { root = insertRec(root,key); } void delete(int key) { root = deleteRec(root,key); } Node insertRec(Node root, int key) { if(root == null) { root = new Node(key); return root; } if(key < root.key) { root.leftChild = insertRec(root.leftChild,key); } else if(key > root.key){ root.rightChild = insertRec(root.rightChild,key); } return root; } Node deleteRec(Node root, int key) { if(root ==...
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class....
Complete the redblacktree in Java. Add a public boolean isBlack field to the Node inner class. Make every Node object have a false isBlack field, all new node is red by default. In the end of the insert method, set the root node of your red black tree to be black. Implement the rotate() and recolor() functions, and create tests for them in a separate class. import java.util.LinkedList; public class BinarySearchTree<T extends Comparable<T>> { protected static class Node<T> { public...
‏What is the output of the Euler tour in the normal binary search tree if the...
‏What is the output of the Euler tour in the normal binary search tree if the key insert order is 5 , 2 , 8 , 5 , 9 , 5 , 1 , 3 , 4 , 2 , 8 ? All keys equal to the node should be the right subtree of that node. ____________________________________________________________ ‏Construct the binary max - heap for the keys given below. Once all the keys are inserted, perform the remove maximum operation, and...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None:...
Create an add method for the BST (Binary Search Tree) class. add(self, new_value: object) -> None: """This method adds new value to the tree, maintaining BST property. Duplicates must be allowed and placed in the right subtree.""" Example #1: tree = BST() print(tree) tree.add(10) tree.add(15) tree.add(5) print(tree) tree.add(15) tree.add(15) print(tree) tree.add(5) print(tree) Output: TREE in order { } TREE in order { 5, 10, 15 } TREE in order { 5, 10, 15, 15, 15 } TREE in order {...
This is in java and you are not allowed to use Java API classes for queues,...
This is in java and you are not allowed to use Java API classes for queues, stacks, arrays, arraylists and linkedlists. You have to write your own implementations for them. You should construct a BST by inserting node values starting with a null tree. You can re-use the code for the insert method given in the sample code from the textbook. -insert method is provided below Your code should have a menu driven user interface at the command line with...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted...
Here is a modification of the BST program that includes a recursive find method: BinarySearchTree2C.java (posted below) Implement the following methods using recursion: int depth() // returns the length of the deepest path from root to any leaf int node_count() // returns the number of nodes in the tree void insert(int n) // inserts value n into the tree BinarySearchTree2C clone() // returns a clone (deep copy) of the tree Add code to the main method to test these methods....
For this question, consider the following class which will be used to construct binary trees. Use...
For this question, consider the following class which will be used to construct binary trees. Use the convention that there is no "empty tree"; each node points to the nodes containing it's two children; and if a node has no left or right child, then the corresponding pointer will be set to null public class TreeNode { public double root; public TreeNode left; public TreeNode right; } Draw a diagram for what a tree of this model would look like...
Please ask the user to input a low range and a high range and then print...
Please ask the user to input a low range and a high range and then print the range between them. Add printRang method to BST.java that, given a low key value, and high key value, print all records in a sorted order whose values fall between the two given keys from the inventory.txt file. (Both low key and high key do not have to be a key on the list). ****Please seperate the information in text file by product id,...
ADVERTISEMENT
Need Online Homework Help?

Get Answers For Free
Most questions answered within 1 hours.

Ask a Question
ADVERTISEMENT