Lab 8 -- Binary Tree Methods

Today we'll gain some experience in writing recursive methods on binary trees.  I've provided a Java application which you can use to test your methods.  The lab8.jar file contains the following files:

• BinaryTree.java
• BinarySearchTree.java
• TreeMethodApplication.java
• TreeMethodFrame.java
• TreeMethods.java
• TreeLoader.java

All the files are complete, except for TreeMethods.java, which contains only stub routines (except for nodeCount, which we wrote in class).  Your assignment is to complete the methods in TreeMethods.java.  The specifications for the methods you are to write are given below.

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.  (See the description of the file formats below.)  The jar file also contains some sample files you can use for testing. Test files 1-5 contain words which are loaded into a binary search tree. Test files 6-10 are integer files.

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 two spaces 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.

Method specifications

You are to write the following binary tree methods:

1.    int height(BinaryTree 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.    BinaryTree mirrorImage(BinaryTree 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 we wrote in class, 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.

3.    int leafCount(BinaryTree tree);

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

4.    int levelCount(BinaryTree tree, int level);

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

5.    boolean isAVL(BinaryTree tree);

Return true if the tree is an AVL tree, false otherwise. Assume that the data items in the tree are Comparable.

For problems 6, 7, and 8, assume that the tree contains Integer objects as its data objects.  (To convert the data item in a node to an int value on which you can operate, you first have to cast it to an Integer, then call the intValue method of the Integer.)  (Test these methods on the Integer trees from files tree6.txt to tree10.txt.)

6.    int nodeSum(BinaryTree tree);

Return the sum of the data values in the tree.

7.    void doubles(BinaryTree tree);

Double the integer value in every node of the tree.

8.    int maxPathSum(BinaryTree 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.

File formats

If you would like to create your own test files, here are some guidelines for creating them:

The "Load File" button can accept either an ordinary text file, or a file containing the description of a tree of integers in a specific format.

In the case of a text file, the program extracts "words" from the file (a word is any sequence of alphanumeric characters) and inserts them, as String objects, into a binary search tree.  If a word occurs more than once in the file, it is added to the tree only once.

The format of the integer files is described as follows:

• The file contains a description of a binary tree of integers.
• An empty tree is represented by a period (".").
• A leaf node is represented by a single integer value, which represents the data item in the node.
  
• A non-empty tree is represented by its root data item (an integer) and left and right subtrees, enclosed in parentheses.
• The first character in the file must be '('.
  

For example, the tree

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

is represented as

( 34 ( 74 . 32 ) ( 83 ( 63 29 . ) 18 ) )