Assignment 9 - COP 3530, Fall 2007

Please read the assignment submission rules and the academic dishonesty page before you start work on this assignment. Failure to comply by these rules will cost a significant percentage of your assignment grade.

Make sure your classes are in the package dataStructures. If you do not understand what packages are you can read this tutorial. If you have trouble with the classpath settings you could try reading this tutorial.
Unless stated otherwise, you are not allowed to use any classes from the dataStructures or the java.util packages.

For any coding question below, even in cases where you may not use any of the methods of the class you are extending, you MAY use the constructor of the class to be extended when you create the constructor of your new class. For example, you may do something like this:

public ALLExtended (){
super();
}

public ALLExtended( int n ){
super(n);
}

In lec19.ppt, you learnt that we can use a binary tree to store an arithmetic expression. For example, the expression

      C*(A-B)/(G+(-E)-F)

can be stored in a binary tree like this:


In this problem, you will extend the LinkedBinaryTree class to support several additional functions.
PLEASE put all your solutions in one single java file. Name this file   MyLinkedBinaryTree.java.
You are NOT allowed to call any methods of the LinkedBinaryTree class. Calling one of these methods can cost up to 100% of the question grade.
You may use java.util.Vector.
a)
Implement a method print(), which will print the tree in prefix order, where each node is printed on a different line and its indentation clearly shows its level. So the example tree would be printed in the following fashion:

/

*

C

-

A

B

+

G

-

-

null

E

F

Note that if a non-leaf node does not have a left child or right child, you have to put a "null" there.
b)
Implement a method findDeepest(), which will find the deepest leaf in the tree and print the path from root to it. For example, in the tree above, E is the deepest leaf node, so your output should be:
/ + - - E
c)
Implement a method printExpression(), which will output the (infix) expression contained within the tree. For the tree above, your output should look like this:
C*(A-B)/(G+(-E)-F)
Note:
  1. You should take care of the parentheses. Your expression should have only the necessary parantheses, with the possible exception of having (unnecessary) paranthesis around unary operations.(For example -E-F vs (-E)-F)
  2. Only four operators + - * / are considered here. + and - are also used as unary operators.

The template is:

package dataStructures;

public class MyLinkedBinaryTree extends LinkedBinaryTree {

    //You may add additional data members here.
    public void findDeepest()
    {
        // Your code goes here.
    }
    public void printExpression()
    {
        // Your code goes here.
    }
    public void print()
    {
        // Your code goes here.
    }
    /** test program */
    public static void main(String[] args) {

        MyLinkedBinaryTree nul = new MyLinkedBinaryTree();

        MyLinkedBinaryTree x = new MyLinkedBinaryTree();

        MyLinkedBinaryTree y = new MyLinkedBinaryTree();


        MyLinkedBinaryTree l = new MyLinkedBinaryTree();
        MyLinkedBinaryTree r = new MyLinkedBinaryTree();

        l.makeTree("A", nul, nul);
        r.makeTree("B", nul, nul);
        x.makeTree("-", l, r);

        l.makeTree("C", nul, nul);
        x.makeTree("*", l, x);

        l.makeTree("E", nul, nul);
        l.makeTree("-", nul, l);
        r.makeTree("F", nul, nul);
        l.makeTree("-", l, r);

        r.makeTree("G", nul, nul);
        y.makeTree("+", r, l);
        y.makeTree("/", x, y);

        System.out.println("The tree:");
        y.print();
        System.out.println("\n\n");

        System.out.println("The path to the deepest leaf:");
        y.findDeepest();
        System.out.println("\n\n");

        System.out.println("The expression:");
        y.printExpression();
        System.out.println("\n\n");

    }

}