Overview:

In this assignment you will combine the code you have written for Binary Search Trees (BSTs) and Red Black 'Rees (RBTs) in previous labs to produce a tree ADT which can be either a simple BST or a self-balancing RBT. You must write a main .c which will create a tree, fill it with words read from stdin, and then print them out in alphabetical order.

Specific details

• All instances of bst/rbt should be replaced with tree in your tree .c file.

• Add an enumerated type to tree .h so that tree_new() can be called like this tree t = tree_new(RBT);

• By default your program should create a tree which is a simple BST. If given -r as a command-line option it should create a tree which is an RBT instead.

• Words should be read using the getword() function from the lab book. It should not be possible to add duplicate words to your tree.

• By default your program should print out all of the words contained in your tree (one word per line) by passing a print_key() function to your tree_inorder () function.

• If given -p as a command-line option words should be printed using a pre-order traversal instead of an in-order one.

• Don't implement a tree_remove() function since removing nodes from an RBT can be a bit tricky. Get rid of your old bst_remove 0 code since using it would break an RBT.

• Add a tree_depth 0 function which should return the length of the path between the root node and the most distant leaf node (excluding the nils at the end of an RBT). If given -d as a command-line option the tree depth should be printed to stderr.

• You may have noticed that the RBT you implemented in labs doesn't ensure that the root is always black. This doesn't affect the structure of the tree at all, but we would like you to remedy this situation.

• We have provided a couple of functions for you to add to your tree .c which you can find in the file /home/cshome/coursework/242/Asgn3/out put -dot . txt

These functions will produce a representation of your tree in the DOT graph description language. This DOT representation can be converted to a pdf (as described in tree_output_dot 0's comment) to help you visualise what your tree looks like.

• If -o output-filename is given as a command-line option then you should call tree_output_dot 0 with output-filename and your tree as arguments (after your tree has been filled).

• If -h is given as a command-line option then a usage message should be printed and your program should exit.

• All memory allocated should be deallocated before your program finishes.