Binary Tree Structure

/**
 * Asks the owner tree to set the root node to a new
 * DatNode containing dat,
 * resulting in a state change from empty to non-empty.
 * @param dat a given data Object.
 * @param owner the context of this state.
 */
void insertRoot(Object dat, BiTree owner) {
	owner.setRootNode(new DatNode(dat));
}

/**
 * Throws java.util.NoSuchElementException.
 * @param owner the BiTree holding this EmptyNode.
 */
Object remRoot (BiTree owner) {
	throw new NoSuchElementException ("EmptyNode.remRoot()");
}

/**
 * Calls algo's emptyCase() method to execute the algorithm algo.
 * @param owner the BiTree holding this EmptyNode.
 * @param algo an algorithm on owner.
 * @param inp the input algo needs.
 * @return the output for the emptyCase() of algo.
 */
Object execute(BiTree owner, IVisitor algo, Object... inp) {
	return algo.emptyCase (owner, inp);
}

/**
* Stores data and represents a non-empty state.
* @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
*/
class DatNode extends ANode {
    /**
     * Data Invariant: != null.
     */
    private BiTree _leftTree = new BiTree ();

    /**
    * the stored data element.
    */
    private Object _dat;
    /**
    * Data Invariant: != null.
    */
    private BiTree _rightTree = new BiTree ();

    /**
    * Throws an IllegalStateException because the owner tree is not empty.
    * @exception IllegaStateException.
    */
    void insertRoot(Object dat, BiTree owner) {
        throw new IllegalStateException ("DatNode.insertRoot().");
    }

    /**
    * Removes and returns the root element from the owner tree by asking the
    * left subtree and, if necessary, the right subtree to help do the job.
    * The subtrees help determine whether or not the root element can be removed
    * by executing appropriate anonymous visitors.
    * @param owner the BiTree holding this DatNode.  Why is it final?
    * @exception IllegaStateException if both subtrees of owner are non-empty.
    */
    Object remRoot(final BiTree owner) {
        return _leftTree.execute(new IVisitor() {
            /**
             * The left subtree is empty. The parent tree can simply become the
             * right subtree.
             */
            public Object emptyCase(BiTree host, Object... notUsed) {
                owner.setRootNode(_rightTree.getRootNode());
                return _dat;
            }

            /**
             * The left subtree is not empty!  The right subtree must determine
             * whether or not the parent root can be removed.
             */
            public Object nonEmptyCase(BiTree host, Object... notUsed) {
                 return _rightTree.execute(new IVisitor() {

                    /**
                     * At this point both the lef and right subtrees are empty.
                     */
                    public Object emptyCase(BiTree h, Object... notUsed) {
                        owner.setRootNode(_leftTree.getRootNode());
                        return _dat;
                    }

                    /**
                    * Both left and right subtrees are not empty!  Cannot remove root.
                    */
                    public Object nonEmptyCase(BiTree h, Object... notUsed) {
                        throw new IllegalStateException ("Both subtrees are non-empty");
                    }
                });
            }
        });
    }

    /**
    * Calls algo's nonEmptyCase() method to execute the algorithm algo.
    * @param owner the BiTree holding this DatNode.
    * @param algo an algorithm on owner.
    * @param inp the input algo needs.
    * @return the output for the nonEmptyCase() of algo.
    */
    Object execute(BiTree owner, IVisitor algo, Object... inp) {
        return algo.nonEmptyCase (owner, inp);
    }
}

/**
 * Computes a String representation of the binary tree host so
 * that it can be
 * printed vertically.
 * @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
 */
public class ToString implements IVisitor {
   
    public final static ToString Singleton = new ToString ();
   
    private ToString () {
    }

   

    /**
     * Returns "[]", a String representation of an empty binary
     * tree.
     * @param host an empty binary tree.
     * @param nu not used.
     * @return String
    */
   
    public Object emptyCase(BiTree host, Object... nu) {
       
        return "[]";
    }

   

    /**
     * Computes a String representation of the binary tree host
     * so that it can be printed vertically. There is no '\n'
     * at the end of the String.  Passes appropriate leftmost
     * leading String to a
     * helper visitor to compute the
     * String representations of the left and right subtrees.
     * @param host a non-empty binary tree.
     * @param nu not used.
     * @return String
     */
   
    public Object nonEmptyCase(BiTree host, Object... nu) {
        String ls
        = (String)host.getLeftSubTree().execute(ToStringHelp.Singleton, "|  ");
       
        String rs
        = (String)host.getRightSubTree().execute(ToStringHelp.Singleton, "   ");
       
        return (host.getRootDat() + "\n" + ls + "\n" + rs);
       
        // EXERCISE FOR STUDENTS: Rewrite using anonymous inner classes.
    }
}

/**
 * Computes a String representation of the binary tree host so
 * that it can be printed vertically, given a leftmost leading
 * string for the two subtrees.
 * Called by ToString.
 * Should be implemented as an anonymous inner class in the
 * call by ToString.
 * @author Dung X. Nguyen - Copyright 2005 - All rights reserved.
 */
public class ToStringHelp implements IVisitor {
   
    public final static ToStringHelp Singleton = new ToStringHelp ();
   
    private ToStringHelp () {
    }

   

    /**
    * Returns "|_[]" to denote an empty tree subtree.
    * @param host an empty binary (sub)tree.
    * @param nu not used.
    * @return String
    */
   
    public Object emptyCase(BiTree host, Object... nu) {
       
        return "|_ []";
    }

   

    /**
    * Computes a String representation of the binary tree host
        * so that it can be printed vertically.
    * There is no '\n' at the end of the String.
    * @param host a non-empty binary (sub)tree.
    * @param leftLead[0] appropriate leftmost leading String to
       * help compute the
    * String representations of the left and right subtrees.
    * @return String
    */

   

    public Object nonEmptyCase(BiTree host, Object... leftLead) {
        String ls
            = (String)host.getLeftSubTree().execute(this, leftLead[0] + "|  ");
        String rs
            = (String)host.getRightSubTree().execute(this,
      						leftLead[0] + "   ");
       
        return ("|_ " + host.getRootDat()+ "\n" +
                leftLead[0] + ls + "\n" +
                leftLead[0] + rs);
    }
}