Lab 5: Binary Search Trees (DUE: At the end of Lab)
Preliminaries
You will need your notes from class about binary search trees.
This week you will be writing your code in the files called lab5.c, bst.c and bst.h.
Part 1 - Binary Search Tree Library
Create a binary search tree library (i.e. bst.h and bst.c) where each node has an integer value as its data value.
For example:
The above image is an example of a BST that needs to be created where each data value for a node is an int. Refer to your notes for creating the struct for a binary search tree.
Implement the following functions in your library:
/* Adds an integer to the tree. */ BST* bst_insert(BST* tree, int value); /* Returns the number of nodes in the tree. */ int bst_size(const BST* tree); /* * Prints all the nodes in the order (i.e. from smallest value in tree to the largest value). * Each value should be followed by a newline. */ void bst_inOrder(const BST* tree); /* * Returns the number of leaf nodes in the tree. * A leaf node in a tree is a node with no children. * For example, the tree shown above contains 4 leaf nodes. */ int bst_leavesCount(const BST* tree); /* * Returns true if all the integers inside the "intArray" are in the BST, otherwise returns false. * Hint: think about having a helper function that checks to see if an integer is inside the BST. */ bool bst_containsAll(const BST* tree, const int* intArray, int len);
An example of calling the bst_inOrder on the tree in the image above should print the following:
1 3 4 6 7 8 10 13 14
Make sure to test your functions in your binary search tree inside the lab5.c file (i.e., enough cases to convince a moderate skeptic that your code does, in fact, work). You do not need to test the inOrder or insert functions.
Once completed, commit all files to your repository.