CSC 502 Binary Tree Exercises

1. Binary Trees Assignment

The goal is to gain experience writing code to perform different binary tree operations. Begin by downloading the zipped up folder of a Netbeans project BinTreeExercises.zip that contains a binary tree class with various methods, most of which are stubbed out.

The program will allow the user to enter the commands shown in the above image. The commands allow the user to

  1. add value: Add an integer value to a binary search tree. This is already implemented.
  2. randomAdd count : add a number of values to the tree. The number of values added is specified by count, and the values are randomly selected from the range 0..199. This is already implemented.
  3. remove value: remove a value from the binary search tree. This is already implemented.
  4. removeRightMost: remove the ``rightmost" value from the binary search tree. This is the value that you get when you start at the root and then keep passing from the node at which you are at to that node's right child. The process stops when you come to a node with no right child. The rightmost node is the node at which this process stops.
  5. removeLeftMost: remove the ``leftmost" value from the binary search tree. This is already implemented.
  6. size: returns the number of values that are currently stored in the tree.
  7. treeHeight: returns the height of the binary tree. The height of a tree is the length of the longest path from the root to a leaf. The length of a path is the number of links in the path: it is one less than the number of nodes in the path.
  8. preorder, inorder, postorder : return a preorder, inorder, or postorder list of the values stored in the tree.
  9. levelOf value: returns the least level of an occurrence of the value in the tree, or -1 if the value is not in the tree.
  10. atLevel int: returns a list of all values that inhabit the tree at the level specified by the integer.
  11. leaves: returns a list of all the leaves of the tree.
  12. getRightMost: returns the rightmost value in the tree without removing it from the tree.
  13. getLeftMost: returns the leftmost value in the tree without removing it from the tree.
  14. clear: removes all values from the tree.

Here are some screen shots of how the program should work, illustrating some of the above commands.

2. What You Have to do

Download the zip folder BinTreeExercices.zip and unzip it into a folder on your computer. Add your name as author, noting that some of the code was written by Dr. Muganda.

Next, note the following method, already implemented. Study them and understand them: it may help you in implementing the rest of the methods.

Next, implement the stubbed-out methods in the BinaryTree class. Do not change the parameters of any of the methods. Write one method at a time, and run the program to test the method you have just written. You can use the randomAdd and add commands, which are already implemented, to set up your tests. I recommend implementation in the following order:

        clear
        size
        treeHeight
        preorder, postorder, inorder
        getRightMost
        getLeftMost
        removeRightMost
        levelOf
        leaves
        atLevel
    

3. Due Date

This is due Saturday at end of week 4, at midnight.