Oct 14: Trees

Layout Managers
General Trees
Implementing Trees
Binary Trees

Code discussed in lecture

Layout Managers

Demonstrate the GUI in PS-3. Display the code of Editor.java. Note two things:

JPanel objects are used to organize buttons. What is more, a JPanel is used to hold the three button JPanels.
We have discussed the FlowLayout layout manager. The GUI for PS-3 uses two additional managers: GridLayout and BorderLayout. The first of these has two parameters: the number of rows and number of columns. It lays components out on a grid of this size. It is used for the JPanel holding the three button panels to get them to line up in a vertical column.

A BorderLayout allows the user to put one thing at the top (NORTH), one at the bottom (SOUTH), one on the right side (EAST), one on the left side (WEST), and one in the middle (CENTER). The CENTER will expand to occupy all space not used by the other four. Here the JPanel holding the three rows of buttons goes in the NORTH and the canvas goes in the CENTER.

General Trees

A tree is a very useful data structure for representing heirarchical relations. A tree is built up from nodes. Tree terminology it taken from family trees. The top node is called the root. Each node has zero or more children. An edge connects a node with its child. Nodes having no children are called external nodes (or leaves) and nodes with children are called internal nodes. A child has exactly one parent (except for the root, which has no parent). Nodes with the same parent are siblings. Ancestors and descendents are what you would expect from family trees. A subtree of a node consists of all descendents of that node (including the node itself).

Here are some examples of things that can be represented by trees:

The Java inheritance hierarchy. Nodes represent classes and the children of a node are those classes that extend their parent class. The root is Object.
Organization charts. Nodes are divisions or groups within the organization and the children of a node are the sub-divisions of the parent division.
File systems on computers. Folders are nested within folders. Each folder can be represented by a tree node, and each enclosing folder is a child node. The root for the Unix system is called "/".
HTML documents. The way to indicate how to lay out a document in HTML is to use tags. Some tags used in the short document below are:
- html - the document itself
- h1 - the highest level of header
- p - a paragraph of text
- b - bold
Tags are enclosed within angle brackets. Tags come in pairs, with opening tags having the name of the tag and the corresponding closing tag having a "/" before the name. These tags can be nested, as shown below:
<html> <h1> Introduction </h1> <p> <b> Hi </b> there, CS 10 student! </p> <h1> Conclusion </h1> <p> Bye </p> </html> These are represented internally by a Document Object Model (DOM), which is a tree. Nodes are associated with an open/close tag pair or with a piece of text. You can see from the indentation how this tree would be organized. At the top level (the root) is an "html" node. It would have four children: an "h1" node, a "p" node, another "h1" node, and another "p" node. The two "h1" nodes would each have one child, a single text node. So would the second "p" node. However, the first "p" node would have two children, a "b" node and a "text" node. The "b" node would have a single child, a text node. (Draw the tree.)

The book gives additional examples. We will see a more examples as the course progresses.

Note that the examples above have some cases where the order of children does not matter (the Java inheritance hierarchy, file systems, and organization charts). However, for an HTML document the order is very important! In representing trees we end up imposing an order on children, whether it is important or arbitrary.

Implementing Trees

We will not use the tree code from our textbook, but feel free to read it.

The book classes use a slightly different approach than we have seen so far. We have built our linked lists from Element objects, where Element is an inner class. We access the elements directly from within SentinelDLL or SLL and access fields with expressions like current.next. However, we provide no access to Element objects from outside of the class. We instead have a current built into the class, or we provide an iterator. Java does the same thing.

Goodrich and Tamassia build up their lists, trees, graphs, etc. from Position objects. Position is an interface with a single method: element(). This method returns the data stored in the object. Their node classes for lists (Node), trees (TreeNode), etc. implement the Position interface. They then let the user get a reference to one of these nodes via methods like root() in the Tree interface. However, while root() actually returns a reference to a TreeNode object, its return type is Position.

This means that there are only two things that you can do with a Position:

Call the method element on it to get the data saved within it.
Pass them to methods of NodePositionList, LinkedTree, and other classes that deal with positions. These methods will cast the Position to the correct type (after verifying that it is the correct type!) and use it.

This partially protects against the user calling methods on the Position object (although if the user knows that the Position is really a LinkedTree

node he or she can cast it and call the functions). However, this approach complicates the tree code and hides its basic simplicity. Therefore we implemented our own tree code. We do not implement code for general trees (although we could do so), but concentrate on the common special case of binary trees.

Binary Trees

There is a special kind of tree called a binary tree, where each node has 0, 1, or 2 children. What is more important, each child is either a left child or a right child. Therefore while there is one general tree with n nodes, n-1 of which have 1 child and the last has no children, there are 2^n-1 binary trees that meet that description. (The child of the root can be a left or right child, the child of the second node will be a left or right child, etc.) We will be working mostly with binary trees in this class. They come up in lots of applications: decision trees, expression trees, code trees (e.g. Huffman encoding), and binary search trees. (Draw some binary trees.)

Rather than having an inner class to represent the nodes and manipulating them via an outer class (as we did for linked lists), this time we make the tree nodes themselves more powerful and manipulate them from other classes. This code is in BinaryTree.java. It has three instance variables, references to the left child, the right child, and the data saved in the tree node. The book also keeps a reference to the parent node, and this can be useful for certain applications.

The BinaryTree public methods are:

isInner()
isLeaf()
hasLeft()
hasRight()
getLeft()
getRight()
setLeft()
setRight()
getValue()
setValue()
size()
height()
equals() (tests two trees for equality)
fringe() (returns leaves in left-to-right order)
preorder()
inorder()
postorder()
reconstructTree(List preorder, List inorder) (reconstruct a tree from its preorder and inorder traversals)

Go through size, height, toString, equals, and fringe. For each, look at a tree and develop the recursive idea of how to get the answer. Then show how the code does this.

For toString note the the idea of indentation to represent the tree layout and show how this is handled in the code. The amount of indentation is passed to toStringHelper> and increased for each call to a child. Note further that we do right first and then left, so that when you look at the output with your head tipped to the left it looks like the structure of the binary tree.

For equals, point out that this is a function from Object which we override. This equals is used in all sorts of places withing Java. It would seem more sensible to make its parameter a BinaryTree, but if we did that we would overload, not override, the equals in Object. This is a common bug! So we instead make sure that other is a BinaryTree and then cast it. The "?" within the angle brackets is a feature of the way that generic types were implemented, which prevent checking whether the actual type is "E".

For fringe note that we create an empty ArrayList and pass it to fringeHelper. This ArrayList has data added to it if the node is a leaf, and passed to the left and right subtrees otherwise. We could have done something like we did for toString, but that would require appending two ArrayLists.