Lab 5 - Binary Tree Methods

Due: Sunday, March 15, 2009 by midnight

This week we'll gain some experience in writing recursive methods on unordered binary trees. I've provided a GUI-based Java application which you can use to test your methods. The lab5.jar file contains the following java files:
All the files are complete, except for TreeLoader.java, which contains only a stub of the loadFromFile method, and TreeMethods.java, which contains only stub routines for several recursive methods which operate on binary trees. Your assignment is to complete the methods in TreeLoader.java and TreeMethods.java.

The application's GUI frame has two text areas for output, and a group of buttons for user commands. The "load file" button allows the user to load a binary tree from a disk file. The jar file also contains some sample files you can use for testing, in the format described below.

When a file is loaded, a binary tree object is created, and the tree is displayed in the left area of the frame. The tree is displayed in inorder sequence, with the data from each node on a separate line. Each node is indented one space from its parent, so the structure of the tree is visible. (Basically, turn your head 90 degrees and you should see the tree as you might draw it on paper without edges.)

The area on the right side of the frame is used for the output of commands. The output may be a single number, as in the "height" method, or it may be another tree, as in the "mirror" method.

Note: Use Java generics in your code when declaring and instantiating a tree or stack. (Use BinaryTree<String> and Stack<BinaryTree<String>>.) Your code should not generate any warning messages when compiled.


Part One: Loading an Input File

The test files for the program list the nodes of the tree in postorder sequence, one node per line. Each line contains a string, which is the data value stored in the node, and two tag bits. The first tag bit indicates whether or not this node has a left child or not. (1=yes, 0=no). The second tag bit indicates whether the node has a right child or not.

For example, the tree

              34
           /      \
         74        83
           \     /    \
           32   63   18
               /
              29
is represented as
        32 0 0
        74 0 1
        29 0 0
        63 1 0
        18 0 0
        83 1 1
        34 1 1
The information in the file is sufficient to uniquely determine a binary tree. The tree can be constructed from the file using the following algorithm:
create an empty stack of binary trees;
while there is more input {
    read a line containing data and two tags;
    create a new binary tree with data at its root;

    if the right tag is 1, pop an element from the stack 
                           and make it the right subtree of the new tree;

    if the left tag is 1, pop an element from the stack 
                          and make it the left subtree of the new tree;

    push the new tree;
}
the stack should contain one element, which is the tree represented by the file data;

Your task is to implement this algorithm in a method called "loadFromFile" in the TreeLoader class. The signature of the method is

    public BinaryTree<String> loadFromFile(String filename);

The method should create a Scanner object to read strings from the file whose name is given as an argument. It should create a Stack of BinaryTree<String> objects to use as a work area. You can use the Scanner and Stack classes from java.util. Scanner has the following useful methods:

boolean hasNext();  //  returns true if the Scanner has tokens remaining, false otherwise
String next();      //  returns the next token from the Scanner as a String
int nextInt();      //  returns the next token from the Scanner as an int

I've written a simple testing program as the main method in TreeLoader.java. It accepts a filename as a command-line argument, loads a binary tree from the file, and then displays it in the same format that is used in TreeMethodApplication. E.g.,

    java TreeLoader tree1.txt


Part Two: Writing Binary Tree Methods

You are to write the following binary tree methods in the TreeMethods class. All of your methods should be recursive. Don't use an Iterator in any of your solutions.
  1. int height(BinaryTree<String> tree);

    Return the height of the tree. (By our definition, a tree with exactly one node has a height of 0. So, what about an empty tree? Return -1 in this case.)

  2. int nodeCount(BinaryTree<String> tree);

    Return a count of the number of nodes in a given tree.

  3. int leafCount(BinaryTree<String> tree);

    Return a count of the number of leaves a given tree.

  4. int levelCount(BinaryTree<String> tree, int level);

    Return a count of the nodes in a tree at a given level (depth). For example, the sample tree immediately above has 1 node at level 0, 2 nodes at level 1, and 2 nodes at level 2.

  5. int weightBalanceFactor(BinaryTree<String> tree);

    The "weight-balance factor" of a binary tree is a measure of how well-balanced it is; that is, how evenly its nodes are distributed between the left and right subtrees of each node. Define the weight-balance factor of a binary tree as follows: It is the maximum value of the absolute value of (number of nodes in left subtree - number of nodes in right subtree) for all nodes in the tree. This method returns the weight-balance factor of a given binary tree.

  6. BinaryTree mirrorImage(BinaryTree<String> tree);

    Return a new tree which looks like the mirror image of the given tree. For example, given

           A
         /   \
        B     C
       / \
      D   E
        
    you should return
           A
         /   \
        C     B
             / \
            E   D
        

    As in the clone() method for Collections, the new tree should contain all new nodes, not sharing any with the original tree. However, the data objects in the tree should be the same objects as those in the original tree -- those objects should not be cloned. (This is also known as a shallow copy.)

The remaining methods assume that the strings stored in the binary tree are actually integers. Your code will have to convert them to ints using the Integer.parseInt() method. (If you apply one of these methods to a tree containing non-integer data, an exception will be thrown and a message displayed in the right panel of the application window. Test files 6-10 contain integer data.)

  1. int nodeSum(BinaryTree<String> tree);

    Return the sum of the data values in the tree.

  2. void doubles(BinaryTree<String> tree);

    Double the integer value in every node of the tree.

  3. int maxPathSum(BinaryTree<String> tree);

    Define a "path sum" in a tree to be the sum of the data values in a path from the root to a leaf (including the data values in both the root and the leaf). This method returns the maximum of all the path sums in the tree.

Finally, you'll create some methods that will traverse the nodes in the tree. (Note that for efficiency, you'll want to use a StringBuffer to generate the string, then use its toString() method to create the string you return.)

  1. public String preOrder(BinaryTree<String> tree);

    Perform a preOrder traversal of the nodes, returning a String representing the order in which you "visit" the nodes. Embed a newline "\n" after each data element so the output looks like:

        A
        B
        D
        E
        C
        

  2. public String postOrder(BinaryTree<String> tree);

    Perform a postOrder traversal of the nodes, returning a String representing the order in which you "visit" the nodes. Embed a newline "\n" after each data element so the output looks like:

        D
        E
        B
        C
        A
        

  3. public String inOrder(BinaryTree<String> tree);

    Perform a inOrder traversal of the nodes, returning a String representing the order in which you "visit" the nodes. Embed a newline "\n" after each data element so the output looks like:

        D
        B
        E
        A
        C
        


Application

You can test your TreeMethods implementations by using the TreeMethodApplication class.

    java TreeMethodApplication 
    
and then Load File and push buttons!


Makefile

For those of you not using eclipse and developing your programs from the command line, I've included a Makefile you can use. This is a set of instructions for the program make which will make compilation simpler. Basically, you can compile your code by typing:

    % make

and it will compile any Java files you have changed, and only those that have changed!

You can also have it remove your class files by typing

    % make clean

and you should be sure to do this before handing in the project.


handin

Look through your programs and make sure you've included your name at the top of all of them.

README file

You need to create a file called "README" that contains the following information:

  1. Your name
  2. Any known problems or assumptions made in your classes or program
  3. Anything you've implemented for extra credit

Honor code

If you adhered to the honor code in this assignment, add the following statement to your README file:

I have adhered to the Honor Code in this assignment.

handin

You now just need to electronically handin all your files. Assignment is 5.

Don't forget to run lshand and verify that things were submitted.


Lab Goals

This lab is intended to:


Last Modified: March 09, 2009 - Benjamin A. KupermanVI Powered