CIS 22 - Data Structures

Spring 2005

Assignment #6 - Binary Search Trees

Due: May 16, 2005

Overview

This assignment consists of implementing several features of binary search trees :

Code and test a full implementation - including the remove method - of a binary search tree class. (You may choose how to handle remove: you may either actually remove the node, or you may flag it as being deleted)
Write the method findmax for the Binary Search Tree class. (It should be different than the version you wrote for the binary tree class.)
Insert data into the Binary Search Tree and print it out in preorder, inorder, and postorder. Test this on several different trees - draw pictures of the trees on the output to convince me that your program works!
Also test the binary search tree using the test driver you used for Homework #5. (The tests of count and countleaves and sumdata, etc. should all work for a binary search tree as well!)

Many opportunities for Extra Credit are given below.

NOTE: You must test the Binary Search Tree class fully Choose your test cases carefully to test all cases. If you do not fully test your class, it will be assumed that it doesn't work properly. Annotate the output - draw pictures (by hand) of the trees - to illustrate the test cases.

You must implement the remove function of the BSTree class. You may either actually remove the item from the tree, or you may flag the item as "deleted". Note that if you choose to use a flag, you may need to modify the BinTree and TNode classes as well.

Testing

As usual, design test data that will test your code thoroughly. For example, make sure that you test remove thoroughly - remove an item that is in a leaf, remove an item that is in a node with one child, remove an item that is in a node with two children, remove the root, remove from a tree with only one node, etc.

Extra Credit

You may do any or all of the options below for extra credit. Be sure to indicate on your submission which extra credit items you did.

Implement and test a level-order traversal using queues.
Implement and test a non-recursive traversal using the father pointers.
Implement the tree using right inorder threads. (You will have to add a boolean field to the tree node, isthread, to be able to identify whether a right pointer field is a true child or is a thread.) At the end of the program, print out the trees using the recursive traversal, and then also print them out non-recursively using the threads. You can read more about threads and the nonrecursive traversal in your textbook.
Implement a binary tree iterator. At the end of the program, after printing out the trees recursively, also print it them out non-recursively using the iterator. Code for a binary tree iterator is on this web site.

If you choose to do extra credit, please note what you have done on the cover page of what you hand in, as well as in your comments.