In this project, we will be implementing the basic functionality of a Binary Search Tree.

Files provided in the project:

1) BinarySearchTree.h. 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.c:

a. BinarySearchTree newBinarySearchTree() which should allocate the memory for a new binary search tree, initialize the variables, and return the address.

b. void freeBinarySearchTree(BinarySearchTree tree) which should free the tree (including any nodes currently in the tree).

c. NodeT *allocateNode(Element value) which should allocate memory for a new node, store value inside this node, and return the address of the node.

d. 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 call this function with search(tree->pRoot, searchValue).

e. 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.

f. 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 printInOrder(tree->pRoot).

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 not in tree if it does not exist. If 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. 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.

/************************************************************************ BinarySearchTree.h Purpose: Define constants used in the project. Struct definitions for a general Binary Search Tree. Define function prototypes used by general Binary Search Trees. ************************************************************************/ #include  #include  #include  #include  //#define constant values #define MAX_URL_LENGTH 50 #define TRUE 1 #define FALSE 0 //typedef for the Element struct which constains a c string to store a URL in the BrowserList typedef struct { int key; } Element; //Typedef for a node in the doubly linked list (has next and previous pointers). typedef struct NodeT { Element element; struct NodeT *pLeft; struct NodeT *pRight; } NodeT; //Typedef for a binary search tree implementation. //Contains a pointer to the root node of the tree. typedef struct { NodeT *pRoot; } BinarySearchTreeImp; typedef BinarySearchTreeImp *BinarySearchTree; /*****Prototypes*******/ //Malloc a new BinarySearchTreeImp and return it's address. BinarySearchTree newBinarySearchTree(); //Free the BinarySearchTree and any nodes that still exist in the tree. void freeBinarySearchTree(BinarySearchTree tree); //Allocate a new node and store "value" as the Element in the node. Return the address of the node. NodeT *allocateNode(Element value); //Recursive algorithm for searching for a node with key value equal to searchValue. Return a pointer to the node if you find it or return NULL if it does not exist. NodeT *search(NodeT *p, int searchValue); //Create a node to store the given Element and add it as a leaf in the BinarySearchTree. Do not worry about balancing the tree for this project. //Return true if the insert worked successfully, and return false if the node already existed in the tree. int insert(BinarySearchTree tree, Element value); //Recursivly print the key values of all nodes in the subtree rooted at p in increasing order. void printInOrder(NodeT *p); //Recursivly print the key values of all nodes in the subtree rooted at p according to a preorder traversal. void printInOrder(NodeT *p); 

***********************************************************

p4input.txt

INSERT 8 INSERT 7 INSERT 10 INSERT 9 INSERT 4 INSERT 7 INSERT 1 INSERT 0 SEARCH 5 SEARCH 7 SEARCH 2 SEARCH 0 PRINT INORDER PRINT PREORDER 

********************************************

abc123p4.c

#include "BinarySearchTree.h" int main() { return 0; }