ICS 211 Homework 9

Trees

In this assignment, you implement a method to convert a tree to a string.

Your class must include the BinaryNode.java code.

Your class must have an instance variable that refers to (points to) the root of a tree, and some way(s) for your main method to build an arbitrary tree specified by the user.

Your class must provide a public String toString() method that converts the tree to a string, in the same way that folders are printed, with the root first, then the children of the node indented 4 spaces, the grandchildren indented 8 spaces, and so on. For example, consider a tree with root "hello". "hello" has two children, "foo" and "bar". "foo" has children "world", and "baz", and "bar" has children "bug" and "loop". That tree would be converted to the following string:

hello
    foo
        world
        baz
    bar
        bug
        loop

The above example shows what the string looks like when it is printed. As a string, it actuall looks like this:

"hello\n    foo\n        world\n        baz\n    bar\n        bug\n        loop\n"

As many of you already know, "\n" is the newline character in Java.

Your implementation of the toString method must be recursive. The recursion may be in a helper method. Recursion is also usually the simplest way to implement this pre-order tree traversal.

You must also create a driver program that builds a tree specified by the user, then prints it as above. For example, you may use the following user interface, where the l/r indicate whether to go down the tree to the left or right before inserting, and for the last l/r, whether to insert as the left or right subtree.

Starting program, tree is empty.
enter string to add: hello

Adding new root node hello
Your tree is:
hello

enter string to add, and position in the tree: foo l

Adding new node foo as the left
Your tree is:
hello
    foo

enter string to add, and position in the tree: baz l r

Adding new node baz as the left right
Your tree is:
hello
    foo
        baz

enter string to add, and position in the tree: bar r

Adding new node bar as the right
Your tree is:
hello
    foo
        baz
    bar

enter string to add, and position in the tree: bug r l

Adding new node bug as the right left
Your tree is:
hello
    foo
        baz
    bar
        bug

enter string to add, and position in the tree: world l l

Adding new node world as the left left
Your tree is:
hello
    foo
        world
        baz
    bar
        bug

enter string to add, and position in the tree: loop r r

Adding new node loop as the right right
Your tree is:
hello
    foo
        world
        baz
    bar
        bug
        loop

enter string to add, and position in the tree: fum r l r

Adding new node world as the right left right
Your tree is:
hello
    foo
        world
        baz
    bar
        bug
            fum
        loop

Turning in the Assignment

Email all the java source code for your assignment to the TA following the instructions posted here.