Description
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 an
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
Part 4 – Submission
● Required code organization:
○ program6.c – contains the driver code, and executable program code
○ bst.c/h – Your header file should have (at minimum) the following function
declarations:
■ Data struct
● value (int)
■ Node struct
● data (Data)
● left (Node *)
● right (Node *)
■ Tree struct
● root (Node *)
● Data * (*insert)(Tree *, Data);
● Data * (*search)(Tree * bst, Data value);
● void (*sort)(Tree *, Data *);
● int (*compare)(Tree *t, Tree * copy);
● Tree * (*clone)(Tree *t);
● void (*delete)(Tree * bst);
● void (*removeData)(Tree * bst, Data value);
■ Node * newNode(Data d, Node * parent);
■ Tree * newTree();
■ makefile
● You must have the following labels in your makefile:
○ all – to compile all your code to an executable called
‘program6’ (no extension). Do not run.
○ run – to compile if necessary and run
○ checkmem – to compile and run with valgrind
○ clean – to remove all executables and object files
● While inside your program 6 folder, create a zip archive with the following command
○ zip -r _program6
■ This creates an archive of all file and folders in the current directory called
_program6.zip
■ Do not zip the folder itself, only the files required for the program
● Upload the archive to Blackboard under Program 6.
CS 580U
