For this assignment, using C, you will implement a binary search tree that can store any arbitrary struct in its nodes. You will start by completing the recursive implementation of the binary search tree (BST) in Worksheet 29. You will then modify it to so it can store arbitrary structures at each node, provided you have a an implementation of a compare and print_type function for that structure. We are providing you with the following files: (Files are below, some need fixes and/or functions to be written) bst.c - This is the file in which you'll finish implementing the unfinished BSTree implementation. There is a main function in this file that you should modify to exercise your BST. The file contains several test cases such as testAddNode, testContainsBSTree, testLeftMost, testRemoveLeftMost, and testRemoveNode. Your implementation must pass all these test cases, and you are strongly encouraged to add your own tests as well. bst.h - This file should not be changed. structs.h - This file can be extended to test your code with different data types. compare.c- Put your compare and print functions in here. Worksheet 29 will get you started on your implementation. However, there is one function not mentioned in the worksheet. You will be using the compare function to test two values of a node to determine if one is less than, greater than, or equal to the other. This function is similar to the compareTo function in the Comparable interface in Java. Rather than embedding it into the data structure, as you would do in Java, we will declare it and assume that the user has provided an implementation of compare in the file compare.c. That way, the user can substitute an appropriate compare function for any data type that they plan to store in the tree. For example, if you want to store doubles in your tree, you might define the following struct to store at each node.

struct data { double num; } And then define your compare function to simply compare the two structs based on the num field. However, a user of your data structure could also do the following:

struct pizza { double cost; int numToppings; char *name; } And define a compare function that compares pizzas based on their name, cost, or number of toppings.

In this assignment, the TYPE macro is set to void*. This means that the type of value stored in a node is a void pointer, which means it can be a "pointer to anything". Whenever you dereference a void pointer, you must cast it to a specific type. For example, you can cast a void pointer to struct data* (see the definition in structs.h), then dereference it to get the struct data value the pointer points to. It is the programmer's responsibility to ensure that they cast the void pointer to the same type of value that was actually stored at that location. You should read up on void pointers in your C reference or on the internet. The compare function is needed because we need some way to compare the values stored in the tree nodes. Note that we can't just compare the pointers with the >, <, or == operations since this would just compare the memory addresses the pointers point to. Instead, we want to compare some field of the struct that the pointer points to (e.g. val->number < otherVal->number). The compare function will make changing this function for different structs much easier. Finally, we strongly recommend that you add to the main function to exercise your binary search tree by adding, removing, and testing for elements.

/* File: bst.c Implementation of the binary search tree data structure. */ #include #include #include #include "bst.h" #include "structs.h"

struct Node { TYPE val; struct Node *left; struct Node *right; };

struct BSTree { struct Node *root; int cnt; };

/*----------------------------------------------------------------------------*/ /* function to initialize the binary search tree. param tree pre: tree is not null post: tree size is 0 root is null */

void initBSTree(struct BSTree *tree) { tree->cnt = 0; tree->root = 0; }

/* function to create a binary search tree. param: none pre: none post: tree->count = 0 tree->root = 0; */

struct BSTree* newBSTree() { struct BSTree *tree = (struct BSTree *)malloc(sizeof(struct BSTree)); assert(tree != 0);

initBSTree(tree); return tree; }

/*----------------------------------------------------------------------------*/ /* function to free the nodes of a binary search tree param: node the root node of the tree to be freed pre: none post: node and all descendants are deallocated */

void _freeBST(struct Node *node) { if (node != 0) { _freeBST(node->left); _freeBST(node->right); free(node); } }

/* function to clear the nodes of a binary search tree param: tree a binary search tree pre: tree ! = null post: the nodes of the tree are deallocated tree->root = 0; tree->cnt = 0 */ void clearBSTree(struct BSTree *tree) { if ( tree->root != 0) { _freeBST(tree->root); tree->root = 0; } tree->cnt = 0; }

/* function to deallocate a dynamically allocated binary search tree param: tree the binary search tree pre: tree != null; post: all nodes and the tree structure itself are deallocated. */ void deleteBSTree(struct BSTree *tree) { if (tree->root != 0) { clearBSTree(tree); free(tree); } }

/*----------------------------------------------------------------------------*/ /* function to determine if a binary search tree is empty.

param: tree the binary search tree pre: tree is not null */ int isEmptyBSTree(struct BSTree *tree) { return (tree->cnt == 0); }

/* function to determine the size of a binary search tree

param: tree the binary search tree pre: tree is not null */ int sizeBSTree(struct BSTree *tree) { return tree->cnt; }

/*----------------------------------------------------------------------------*/ /* recursive helper function to add a node to the binary search tree. HINT: You have to use the compare() function to compare values. param: cur the current root node val the value to be added to the binary search tree pre: val is not null */ struct Node *_addNode(struct Node *cur, TYPE val) { /*write this*/ return 0; }

/* function to add a value to the binary search tree param: tree the binary search tree val the value to be added to the tree

pre: tree is not null val is not null pose: tree size increased by 1 tree now contains the value, val */ void addBSTree(struct BSTree *tree, TYPE val) { tree->root = _addNode(tree->root, val); tree->cnt++; }

/* function to determine if the binary search tree contains a particular element HINT: You have to use the compare() function to compare values. param: tree the binary search tree val the value to search for in the tree pre: tree is not null val is not null post: none */

/*----------------------------------------------------------------------------*/ int containsBSTree(struct BSTree *tree, TYPE val) { /*write this*/ return 0; }

/* helper function to find the left most child of a node return the value of the left most child of cur param: cur the current node pre: cur is not null post: none */

/*----------------------------------------------------------------------------*/ TYPE _leftMost(struct Node *cur) { /*write this*/ return NULL; }

/* recursive helper function to remove the left most child of a node HINT: this function returns cur if its left child is NOT NULL. Otherwise, it returns the right child of cur and free cur.

Note: If you do this iteratively, the above hint does not apply.

param: cur the current node pre: cur is not null post: the left most node of cur is not in the tree */ /*----------------------------------------------------------------------------*/ struct Node *_removeLeftMost(struct Node *cur) { /*write this*/ return NULL; } /* recursive helper function to remove a node from the tree HINT: You have to use the compare() function to compare values. param: cur the current node val the value to be removed from the tree pre: val is in the tree cur is not null val is not null */ /*----------------------------------------------------------------------------*/ struct Node *_removeNode(struct Node *cur, TYPE val) { /*write this*/ return NULL;

} /* function to remove a value from the binary search tree param: tree the binary search tree val the value to be removed from the tree pre: tree is not null val is not null val is in the tree pose: tree size is reduced by 1 */ void removeBSTree(struct BSTree *tree, TYPE val) { if (containsBSTree(tree, val)) { tree->root = _removeNode(tree->root, val); tree->cnt--; } }

/*----------------------------------------------------------------------------*/

#if 1 #include

/*----------------------------------------------------------------------------*/ void printNode(struct Node *cur) { if (cur == 0) return; printf("("); printNode(cur->left); /*Call print_type which prints the value of the TYPE*/ print_type(cur->val); printNode(cur->right); printf(")"); }

void printTree(struct BSTree *tree) { if (tree == 0) return; printNode(tree->root); } /*----------------------------------------------------------------------------*/

#endif

#if 1 /* function to built a Binary Search Tree (BST) by adding numbers in this specific order the graph is empty to start: 50, 13, 110 , 10

*/ struct BSTree *buildBSTTree() { /* 50 13 110 10 */ struct BSTree *tree = newBSTree(); /*Create value of the type of data that you want to store*/ struct data *myData1 = (struct data *) malloc(sizeof(struct data)); struct data *myData2 = (struct data *) malloc(sizeof(struct data)); struct data *myData3 = (struct data *) malloc(sizeof(struct data)); struct data *myData4 = (struct data *) malloc(sizeof(struct data)); myData1->number = 50; myData1->name = "rooty"; myData2->number = 13; myData2->name = "lefty"; myData3->number = 110; myData3->name = "righty"; myData4->number = 10; myData4->name = "lefty of lefty"; /*add the values to BST*/ addBSTree(tree, myData1); addBSTree(tree, myData2); addBSTree(tree, myData3); addBSTree(tree, myData4); return tree; }

/* function to print the result of a test function param: predicate: the result of the test nameTestFunction : the name of the function that has been tested message

*/ void printTestResult(int predicate, char *nameTestFunction, char *message){ if (predicate) printf("%s(): PASS %s ",nameTestFunction, message); else printf("%s(): FAIL %s ",nameTestFunction, message); }

/* fucntion to test each node of the BST and their children

*/ void testAddNode() { struct BSTree *tree = newBSTree(); struct data myData1, myData2, myData3, myData4; myData1.number = 50; myData1.name = "rooty"; addBSTree(tree, &myData1); //check the root node if (compare(tree->root->val, &myData1) != 0) { printf("addNode() test: FAIL to insert 50 as root "); return; } //check the tree->cnt value after adding a node to the tree else if (tree->cnt != 1) { printf("addNode() test: FAIL to increase count when inserting 50 as root "); return; } else printf("addNode() test: PASS when adding 50 as root "); myData2.number = 13; myData2.name = "lefty"; addBSTree(tree, &myData2); //check the position of the second element that is added to the BST tree if (compare(tree->root->left->val,& myData2) != 0) { printf("addNode() test: FAIL to insert 13 as left child of root "); return; } else if (tree->cnt != 2) { printf("addNode() test: FAIL to increase count when inserting 13 as left of root "); return; } else printf("addNode() test: PASS when adding 13 as left of root "); myData3.number = 110; myData3.name = "righty"; addBSTree(tree, &myData3); //check the position of the third element that is added to the BST tree if (compare(tree->root->right->val,& myData3) != 0) { printf("addNode() test: FAIL to insert 110 as right child of root "); return; } else if (tree->cnt != 3) { printf("addNode() test: FAIL to increase count when inserting 110 as right of root "); return; } else printf("addNode() test: PASS when adding 110 as right of root "); myData4.number = 10; myData4.name = "righty of lefty"; addBSTree(tree, &myData4); //check the position of the fourth element that is added to the BST tree if (compare(tree->root->left->left->val, &myData4) != 0) { printf("addNode() test: FAIL to insert 10 as left child of left of root "); return; } else if (tree->cnt != 4) { printf("addNode() test: FAIL to increase count when inserting 10 as left of left of root "); return; } else printf("addNode() test: PASS when adding 10 as left of left of root "); deleteBSTree(tree);

}

/* fucntion to test that the BST contains the elements that we added to it

*/ void testContainsBSTree() { struct BSTree *tree = buildBSTTree(); struct data myData1, myData2, myData3, myData4, myData5; myData1.number = 50; myData1.name = "rooty"; myData2.number = 13; myData2.name = "lefty"; myData3.number = 110; myData3.name = "righty"; myData4.number = 10; myData4.name = "lefty of lefty"; myData5.number = 111; myData5.name = "not in tree"; printTestResult(containsBSTree(tree, &myData1), "containsBSTree", "when test containing 50 as root"); printTestResult(containsBSTree(tree, &myData2), "containsBSTree", "when test containing 13 as left of root"); printTestResult(containsBSTree(tree, &myData3), "containsBSTree", "when test containing 110 as right of root"); printTestResult(containsBSTree(tree, &myData4), "containsBSTree", "when test containing 10 as left of left of root");

//check containsBSTree fucntion when the tree does not contain a node printTestResult(!containsBSTree(tree,& myData5), "containsBSTree", "when test containing 111, which is not in the tree"); deleteBSTree(tree); }

/* fucntion to test the left_Most_element

*/ void testLeftMost() { struct BSTree *tree = buildBSTTree(); struct data myData3, myData4;

myData3.number = 110; myData3.name = "righty"; myData4.number = 10; myData4.name = "lefty of lefty"; printTestResult(compare(_leftMost(tree->root), &myData4) == 0, "_leftMost", "left most of root"); printTestResult(compare(_leftMost(tree->root->left),& myData4) == 0, "_leftMost", "left most of left of root"); printTestResult(compare(_leftMost(tree->root->left->left),& myData4) == 0, "_leftMost", "left most of left of left of root"); printTestResult(compare(_leftMost(tree->root->right),& myData3) == 0, "_leftMost", "left most of right of root");

deleteBSTree(tree);

}

void testRemoveLeftMost() { struct BSTree *tree = buildBSTTree(); struct Node *cur; cur = _removeLeftMost(tree->root);

printTestResult(cur == tree->root, "_removeLeftMost", "removing leftmost of root 1st try"); cur = _removeLeftMost(tree->root->right); printTestResult(cur == NULL, "_removeLeftMost", "removing leftmost of right of root 1st try"); cur = _removeLeftMost(tree->root); printTestResult(cur == tree->root, "_removeLeftMost", "removing leftmost of root 2st try");

deleteBSTree(tree);

}

void testRemoveNode() { struct BSTree *tree = buildBSTTree(); struct Node *cur; struct data myData1, myData2, myData3, myData4; myData1.number = 50; myData1.name = "rooty"; myData2.number = 13; myData2.name = "lefty"; myData3.number = 110; myData3.name = "righty"; myData4.number = 10; myData4.name = "lefty of lefty"; _removeNode(tree->root, &myData4); printTestResult(compare(tree->root->val,& myData1) == 0 && tree->root->left->left == NULL, "_removeNode", "remove left of left of root 1st try"); _removeNode(tree->root, &myData3); printTestResult(compare(tree->root->val, &myData1) == 0&& tree->root->right == NULL, "_removeNode", "remove right of root 2st try"); _removeNode(tree->root, &myData2); printTestResult(compare(tree->root->val, &myData1) == 0&& tree->root->left == 0, "_removeNode", "remove right of root 3st try"); cur = _removeNode(tree->root,& myData1); printTestResult(cur == NULL, "_removeNode", "remove right of root 4st try");

deleteBSTree(tree);

}

/*

Main function for testing different fucntions of the Assignment#4.

*/

int main(int argc, char *argv[]){

//After implementing your code, please uncommnet the following calls to the test functions and test your code

// testAddNode(); printf(" "); //testContainsBSTree(); printf(" "); // testLeftMost(); printf(" "); //testRemoveLeftMost(); printf(" "); //testRemoveNode(); return 0; }

#endif

compare.c file

#include #include #include "bst.h" #include "structs.h"

/*---------------------------------------------------------------------------- very similar to the compareTo method in java or the strcmp function in c. it returns an integer to tell you if the left value is greater then, less then, or equal to the right value. you are comparing the number variable, letter is not used in the comparison.

if left < right return -1 if left > right return 1 if left = right return 0 */

/*Define this function, type casting the value of void * to the desired type. The current definition of TYPE in bst.h is void*, which means that left and right are void pointers. To compare left and right, you should first cast left and right to the corresponding pointer type (struct data *), and then compare the values pointed by the casted pointers.

DO NOT compare the addresses pointed by left and right, i.e. "if (left < right)", which is really wrong. */ int compare(TYPE left, TYPE right) { /*FIXME: write this*/ return 0;

}

/*Define this function, type casting the value of void * to the desired type*/ void print_type(TYPE curval) { /*FIXME: write this*/

}

bst.h

/* File: bst.h Interface definition of the binary search tree data structure. */

#ifndef __BST_H #define __BST_H

/* Defines the type to be stored in the data structure. These macros * are for convenience to avoid having to search and replace/dup code * when you want to build a structure of doubles as opposed to ints * for example. */

# ifndef TYPE # define TYPE void* # endif

/* function used to compare two TYPE values to each other, define this in your compare.c file */ int compare(TYPE left, TYPE right); /* function used to print TYPE values, define this in your compare.c file */ void print_type(TYPE curval);

struct BSTree; /* Declared in the c source file to hide the structure members from the user. */

/* Initialize binary search tree structure. */ void initBSTree(struct BSTree *tree);

/* Alocate and initialize search tree structure. */ struct BSTree *newBSTree();

/* Deallocate nodes in BST. */ void clearBSTree(struct BSTree *tree);

/* Deallocate nodes in BST and deallocate the BST structure. */ void deleteBSTree(struct BSTree *tree);

/*-- BST Bag interface --*/ int isEmptyBSTree(struct BSTree *tree); int sizeBSTree(struct BSTree *tree);

void addBSTree(struct BSTree *tree, TYPE val); int containsBSTree(struct BSTree *tree, TYPE val); void removeBSTree(struct BSTree *tree, TYPE val); void printTree(struct BSTree *tree); # endif

structs.h

/* You can modify the structure to store whatever you'd like in your BST */

struct data { int number; char *name; };