Lab 7 - Binary Tree Methods

Due: Sunday, April 15, 2007 by midnight

• BinaryTree.java
• TreeMethodApplication.java
• TreeMethodFrame.java
• TreeMethods.java (incomplete)
• TreeLoader.java (incomplete)

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.

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

For example, the tree

              34
           /      \
         74        83
           \     /    \
           32   63   18
               /
              29

        32 0 0
        74 0 1
        29 0 0
        63 1 0
        18 0 0
        83 1 1
        34 1 1

    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

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. 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.)

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

   Return the sum of the data values in the tree.

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

   Double the integer value in every node of the tree.

9. 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.

Application

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

    java TreeMethodApplication