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:

• Create a new, empty binary tree (remember that a binary tree can be empty).
• Add nodes, as leaves, to the "bottom" of the binary tree.
• Remove leaves from the binary tree.
• Edit the String values in nodes.
• Display the binary tree, in some comprehensible form, to the user.
• Load and save the binary tree as a Serializable object on a file.

  The bottom line here is that it must be possible to create any given binary tree, and to convert any binary tree into any other binary tree.

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

• Detach a subtree (rooted at some node) from the binary tree and move it to some other place in the binary tree.
• Swap two subtrees.
• Delete an internal node. If you do this, something has to happen to its children.
  • You might delete the entire subtree rooted at that node.
  • You might give the user a choice of various things to do with the children.
• Have an Undo operation (but this is probably much too difficult).

  The bottom line here is that you want to make it reasonably convenient for the user to construct any binary tree, and to convert any binary tree into any other binary tree.

Here are some things that you should not do:

• Rearrange nodes automatically in order to keep the tree sorted or balanced.
• Assume that the value in a node uniquely identifies that node.

  What is important here is that you do not make any assumptions about how the binary tree is to be used.

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.

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

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.