UNC-CH COMP 410

Binary Search Tree Implementation

Part 1: BST with manual interactive driver

You will write code that implements, exercises, and analyzes binary search trees. We are eventually going to build splay trees but will get there one chunk at a time, and the first chunk is the basic BST. There are plenty of implementations of "tree" stuff out there. Please do not copy those. I want you to write your own code. The learning in this activity comes from actually powering through all the reasoning needed to get the pointers (objects) and recursive calls hooked up correctly.

What to Hand-in

Hand in your code as per the instructions under Assignment 4 Part 1 in the WorkBase.

Submit a single text file containing the entire Java source... main driver class, random and keyboard code as needed, as well as BST classes. Basically, the text should be all source code needed to compile and run your program.

The program will be the basic BST classes with a main driver that interacts with the user to get operations and data to perform. It will loop until the user indicates to stop. Make one of the possible user selections be to print out the tree. If you wish you can make one of the user selections also be to put some amount of random string data into the tree.

Details

BST first

You can get started by writing a class that implements a Binary Search Tree (BST). Make the tree contain string values. You may do this with generics, or you may do it by writing the classes to use String directly. Both are fine.

Start with a class for a tree node. In this class will be the value field (String data). Also this class will have links to the R and L subtrees (also tree nodes). You may also want or need a parent pointer, bookkeeping information (like child height counts if it were an AVL tree), etc. In this node class can go the methods to do insert, remove, contains, get and other tree manipulation functions. Use the BST ADT signature from the class powerpoint slides to tell what methods to include in your code.

In the approach just described, an entire "tree" would then be no different from a tree node. You may wish instead to design your code like in your text, where you write a separate class BST to point to the root of an entire tree, as well as to contain information that is related to the whole tree (like what is its size, height, etc.). In this "tree" class you have a field "root" that points to a BSTnode and off you go. This "BST" class would then contain special insert etc. methods that would invoke the insert etc. methods on the main root node. You decide which way works best for you.

Just get the basic structure going and grow the functionality as needed.

Driver/tester main method

As with the Bridge Queue, make the main method be a test driver. This test driver will be interactive, requesting keyboard input from the user (see keyboard code below). It basically will be a big loop, asking for an operation to do on a tree, doing it, and going back for more (until the user says stop). In this loop it will first ask the user what operation to perform. Based on what the user selects, it may then have to get more input from the user. Following the BST ADT signature given in the powerpoint slides, it should provide these operations:

new: make a new empty tree
i: insert a string (get the value from the user)
r: remove a node contaning a string (remove it from the tree)
c: contains a string (return and report a boolean indicating success)
g: get a node that has a string as value
x: findMax, returns a string
n: findMin, returns a string
v: val, gets the value stored in the root node
s: size
e: empty
q: quit the tester loop
p: print the tree for inspection (see below)
f: (optional) fill the tree with some amount of random string data (see random code below)

Make your driver accept the short character strings shown as commands so there is less typing for the user to do. You can have your BST and your driver do more ops/things if you wish, but I want to see there so I can test counting on them being there and named this way.

Note on optional random fill: We will be generating random string data for part 2 of this assignment. If you wish to go ahead and get that functionality working now, it may help you in testing your BST code without typing a lot of strings at the keyboard.

Tree Print method

Write a method to allow the tree contents to be printed to see its structure visibly. You may not wish to run this method on large trees, but it will be useful in debugging your code on small trees.

To print a tree, lets do something simple. Let's make print a recursive method, and make it traverse the tree using one of two traversal orders (your choice). Examples of each are shown below for a small binary search tree. Make your choice based on which approach produces a print form that helps you see the tree structure most clearly.

pre-order: This means the root will be the first thing printed, then the entire left child subtree (with its root first etc.) then the entire right subtree. Use indentation to show levels; this means when you print the root of a subtree, indent it a few spaces more than its parent node. Feel free to decorate your printing in any way you like to help the reader to see the tree structure.

reverse in-order: In this case, you do an in-order traversal, but you visit the right subtree before the left. Use indentation to show levels. This form will generate a tree that, if you tilt your head to the left, will look "tree like" and you may find it easier to see the structure for testing purposes.

example: reverse in-order

         weathervane
    stovepipe
         pattern
machine
         jackstand
    garage
         airplane

example: pre-order

machine
  garage
    airplane
    jackstand
  stovepipe
    pattern
    weathervane

Code you may find useful

Random strings

You may find this code useful. It is a class that generates random strings of characters from "a" to "z". It will generate strings that are 5 to 25 characters in length by default if you call MyRandom.nextString() with no arguments. If you wish to control the string lengths better, then you can call it with arguments. Calling MyRandom.nextString(3,11) for example will generate string that vary in length from 3 to 11 characters. The nextString methods are declared static so you can call them as shown with the class name qualifier and don't need to instantiate an object in your code.

Keyboard input

You may also find this code useful. It shows how to do keyboard input in Java. You will be writing a "driver" class to build and exercise the tree (BST and then SPT) and it will take commands from the user at the keyboard. The driver class will contain public static void main and will get the ball rolling.