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

:

BinarySearchTree newBinarySearchTree() which should allocate the memory

for a new binary search tree, initialize the variables, and return the address.

void freeBinarySearchTree(BinarySearchTree tree) which should free the

tree (including any nodes currently in the tree).

NodeT *allocateNode(Element value) which should allocate memory for a

new node, store value inside this node, and return the address of the node.

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

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.

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

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

/************************************************************************ 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);