Binary Tree Editor Suggestions
Dave Matuszek, Spring 2003

Your binary tree editor is a lot like any other editor. Think of a text editor, such as MS Word--you can use it to create a document from scratch, save it, load it in again, and modify it in various ways. Your binary tree editor should also be able to create (starting from nothing) a binary tree, save it, load it in again, and modify it in various ways.

Remember that a Binary Tree is not the same thing as a Sorted Binary Tree--it's much simpler. Since you don't have to keep the binary tree "sorted" or "balanced," you don't need to perform any fancy algorithms to ensure that the binary tree stays sorted or balanced.

The two classes:

Your BinaryTree class should be a general-purpose class, like Java's Vector or HashMap classes. It is not an application itself; it is a class that someone might use in writing some other program. It doesn't do anything by itself, in the same way that a Vector doesn't do anything--it is just an ADT. All you need to write is the methods that I specified. You can add other methods if you like, but be sure that they don't make any assumptions about how the binary tree is going to be used.

You do need to test your BinaryTree class. You can do this by writing a separate Test class, or by adding a public static void main(String[] args) method to BinaryTree to do the testing. Either way, we won't be using it; we will use your API (as described in the assignment and in your javadocs) to create and test binary trees.

Your BinaryTreeEditor is a complete program. It reads, writes, and edits binary trees. To avoid a lot of unnecessary complexity, however, it only works with binary trees that happen to contain Strings as their value fields. Do not modify the definition of BinaryTree to have Strings as the values of nodes, however--that should be a limitation of the editor, not of the binary trees themselves.

Editing operations:

Here are some things that you do need to be able to do:

Here are some things that it would a good idea to be able to do:

Here are some things that you should not do:

For some operations, such as detaching a subtree and reattaching it elsewhere, you may find it convenient to keep track of a second binary tree in your program. (Think about ctrl-X and ctrl-V, cut and paste, in a text editor.) This second binary tree need not be displayed, just as cut text is not displayed between the time you cut it and the time you paste it somewhere else.

Displaying the tree:

You can display the tree (in your editor) with a picture or with text. Here is a picture:

A picture is much harder to construct than a tree, and has these limitations:

  • You can't put much text in the nodes.
  • You can't display a very large tree.

If you choose to do it this way, we will test your editor with small trees and short text strings as values.

Here is the same binary tree, displayed as text in a couple of different ways. Line numbers could be added to any of these versions, to help specify the nodes.

This is approximately the way that my print() method (from the Powerpoint presentation) would do it. This is a somewhat easier to understand version. The only difference is that I've replaced some of the initial spaces with vertical bars and underscores.

Here is yet another way. Notice that in this version, I put the right child above the left child (it seemed more natural).

56
   26
      08
         07
         10
      31
         null
         50
   73
      72
         62
         null
      74
56
 |__26
 |   |__08
 |   |   |__07
 |   |   |__10
 |   |__31
 |       |__null
 |       |__50
 |__73
     |__72
     |   |__62
     |   |__null
     |__74
56
  \__73
  |   \__74
  |    \_72
  |       \__null
  |        \_62
  \__26
      \__31
       |  \__50
       |   \_null
       \_08
          \__10
           \_07

In the above text examples, if you mix spaces with other characters, it is important to use a monospaced font, such as Courier, otherwise things may not line up the way you expect. It's probably a good idea to use a monospaced font in any case.

Here is another example of a binary tree:

Does it live in the water?
     Does it hop?
         Frog
         Fish
     Does it have stripes?
         Zebra
         Does it hop?
             Kangaroo
             Snake

In this example (from the "Animals" game), internal nodes represent questions; leaves represent answers. A "yes" answer goes to the left child (written first); a "no" answer goes to the right child (written second).

Notice that every node either has two children or is a leaf; no node has a single child. This is not something that a general binary tree editor should enforce.

Notice also that you cannot assume every node has a unique value.

Loading and saving:

This is easy. Make your binary trees Serializable, and use the methods I told you about in class to read and write objects to a file. Come to think of it, you probably do need to redefine the value field to be a Serializable, rather than an arbitrary Object. Just say private Serializable value;.

It is important to understand that a file containing a serialized object is not human-readable. That is, if you open it in a text editor, you will see what looks like gibberish. Serialized objects are written out in some binary format that Java understands, and the format enables Java to read it back in and reconstruct the object.

When you load an object, you may get a ClassCastException. This exception should only occur if you save a binary tree, change the definition of the BinaryTree class, and try to read in the old binary tree using the new definition.

A (not very good) example:

Here is a little applet that I wrote some time ago for showing how the Stack operations worked. It's not a great example because (1) stacks are much simpler than binary trees, and (2) I don't supply "load" or "save" operations. It does, however, demonstrate how to "edit" a stack from a GUI.