CS580U - asgn-6 - Munjal511 - Solved

 Binary Search Trees


Driver Code and Test Input Files
●         Provided Files
○         program6.c //Driver Code



You may research online for additional resources; however, you may not use code that was written specifically to solve the problem you have been given, and you may not have anyone else help you write the code or solve the problem. You may use code snippets found online
Part 1: BST
 

●     Create a link based Binary Search tree composed of a Node and Tree struct. You should have a header file, bst.h, with the following:

○     Node struct containing left, right, and parent pointers, in addition to holding a Data struct value.

○     Tree struct containing a pointer to the root of the tree. 

○     A function declaration for a function that allocates a tree, and initializes the root to NULL;

○     A function declaration for a function that takes a Data struct as a parameter, allocates a node, and initializes the left, right, parent fields to NULL.

●     You should also have a source file, bst.c, that implements the two declared functions:

○     Tree * newTree();

○     Node * newNode(Data d, Node * parent);

●     Test your functions and structure to ensure everything is initialized correctly by creating a Tree and adding a root to it.

Part 2: BST Operations
●     Alter your tree struct declaration in your header file to contain the function pointers for insert, search, removeData. Implement the operations in your BST.c file.

●     INSERT:

○     Create a function, Data * (*insert)(Tree * bst, Data value), that inserts into the tree – Helpful hints:

■     Return a pointer to the Data value inserted into the tree

■     Make sure you check for the special case of an empty tree [if(bst->root == NULL)],

■     After checking for the root, use a separate helper function to insert a value into the tree, Data * insertNode(Node * node, Data value), that you can use for the recursive call

■     If the value is already in the tree, return NULL

●     SEARCH:

○     Create a function, Data * (*search)(Tree * bst, Data value), that searches for a value in the tree. Return a pointer to the Data object if found – Helpful hints:

■     Make sure you check for the special case of an empty tree [if(bst->root == NULL)],

■     After checking for the root, use a separate helper function to search the tree, Node * searchNode(Node * node, Data value), that you can use for the recursive call

●     REMOVE:

○     Create a function, void (*removeData)(Tree * bst, Data value), that removes a value from the tree – Helpful hints:

■     Use your (hopefully) working search auxiliary function to find the node you need to delete

●     Your auxiliary search function can return a node pointer, and you primary search function returns the data from that pointer.

■     You will have 3 cases requiring 3 separate functions:

●     remove a leaf node : void removeLeaf(Tree * bst, Node * d_node);

●     remove a node with 1 branch: void shortCircuit(Tree * bst, Node * d_node)

●     remove a node with 2 branches: void promotion(Tree * bst, Node * d_node)

○     You will need to use your removeLeaf() and shortCircuit() functions in your promotion function, so make sure they are working before starting on the promotion function.

Part 3: Testing Your Tree

●     In the driver code provided below, we do the following to test your tree:

○     Using your insert function, insert the following values into your tree (in this order)

■     5,3,10,4,8,2,1,7,9,6,12,11,13

●     The following will be tested:

○     Insertion of the above value set

○     Search on each value

○     Search on a value not in the tree

○     Deletion of each value using the following algorithms

■     Delete leaf

■     Delete 1 child

■     Delete 2 child

■     Delete root

■     Delete 1 child root

■     Delete leaf root

●     You will also need to implement the following:

○     Tree * (*clone)(Tree*): Takes a tree and uses preorder traversal algorithm to return a clone of the tree

○     int (*compare)(Tree*, Tree*): Takes a tree and uses preorder traversal algorithm to determine if the trees are equal

○     void (*sort)(Tree *, Data *): Takes a tree and a data array buffer as parameters, and fills the buffer with the tree data in sorted order using the inorder traversal algorithm.

○     void (*delete)(Tree * bst): Add a post-order deleteTree() function that deletes all nodes and the tree

■     Remember, post order only deletes leafs, so you need only call deleteLeaf()

○     Hint: Each of the above functions is easier to implement if you use an auxiliary recursive function