|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:
BinaryTree class should be a general-purpose class, like
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
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)
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.
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
value fields. Do not modify the definition of
Strings as the values of nodes, however--that should be
a limitation of the editor, not of the binary trees themselves.
Here are some things that you do need to be able to do:
Stringvalues in nodes.
Serializableobject 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:
Undooperation (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:
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:
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
||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
to be a
Serializable, rather than an arbitrary
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
exception should only occur if you save a binary tree, change the definition
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
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