Binary Tree Structure

Summary: Explains the binary tree structure, and gives a sample implementation in Java, along with example tree algorithms.

Up until now, we have been organizing data in a "linear" fashion: one item after another. The corresponding data structures are the immutable scheme list (IList) and the mutable linear recursive structure (LRStruct). Now, suppose we want to model something like the following organization chart.

Figure 1

A structure of data such as the above is called a tree. We first design a special kind of mutable tree structure called binary trees.

1. Binary Tree Object Model

DEFINITION 1: Binary Tree

A (mutable) binary tree, BiTree, can be in an empty state or a non-empty state:

• When it is empty, it contains no data.
• When it is not empty, it contains a data object called the root element, and 2 distinct BiTree objects called the left subtree and the right subtree.

We implement the above object structure with a combination of state/composite/visitor patterns, in a manner analogous to LRStruct.

Below is the public interface of the binary tree framework. Click here for javadoc documentation.

Figure 2

The implementation details are given in the following UML class diagram. Click here for javadoc documentation.

Figure 3

2. Implementation Details

SOURCE CODE: 

Click here for source code.

The code for BiTree is trivial, as it simply delegates most calls to its state, the root node. The real work is done in the state. The code for EmptyNode and DatNode for the most part are equally trivial. The insertion and removal of the root data of a BiTree require some work and need some explanation. When does it make sense to remove the root node from a (binary) tree? That is, when can one unambiguously remove the root node from a binary tree?

Clearly, when both subtrees of a root node are non-empty, then removing the root node is problematic. However, it makes sense to allow root removal when at least one of the subtrees is empty. Suppose one of the subtrees is empty, then BiTree.remRoot() will change the state of this BiTree to the state of the other subtree. For example, when the left subtree is empty, root removal of the parent tree will set the parent tree to its right subtree.

Figure 4

EmptyNode DatNode (a) EmptyNode (b) DatNode /** * Asks the owner tree to set the root node to a new * DatNode containing dat, * resulting in a state change from empty to non-empty. * @param dat a given data Object. * @param owner the context of this state. */ void insertRoot(Object dat, BiTree owner) { owner.setRootNode(new DatNode(dat)); } /** * Throws java.util.NoSuchElementException. * @param owner the BiTree holding this EmptyNode. */ Object remRoot (BiTree owner) { throw new NoSuchElementException ("EmptyNode.remRoot()"); } /** * Calls algo's emptyCase() method to execute the algorithm algo. * @param owner the BiTree holding this EmptyNode. * @param algo an algorithm on owner. * @param inp the input algo needs. * @return the output for the emptyCase() of algo. */ Object execute(BiTree owner, IVisitor algo, Object... inp) { return algo.emptyCase (owner, inp); } /** * Stores data and represents a non-empty state. * @author Dung X. Nguyen - Copyright 2005 - All rights reserved. */ class DatNode extends ANode { /** * Data Invariant: != null. */ private BiTree _leftTree = new BiTree (); /** * the stored data element. */ private Object _dat; /** * Data Invariant: != null. */ private BiTree _rightTree = new BiTree (); /** * Throws an IllegalStateException because the owner tree is not empty. * @exception IllegaStateException. */ void insertRoot(Object dat, BiTree owner) { throw new IllegalStateException ("DatNode.insertRoot()."); } /** * Removes and returns the root element from the owner tree by asking the * left subtree and, if necessary, the right subtree to help do the job. * The subtrees help determine whether or not the root element can be removed * by executing appropriate anonymous visitors. * @param owner the BiTree holding this DatNode. Why is it final? * @exception IllegaStateException if both subtrees of owner are non-empty. */ Object remRoot(final BiTree owner) { return _leftTree.execute(new IVisitor() { /** * The left subtree is empty. The parent tree can simply become the * right subtree. */ public Object emptyCase(BiTree host, Object... notUsed) { owner.setRootNode(_rightTree.getRootNode()); return _dat; } /** * The left subtree is not empty! The right subtree must determine * whether or not the parent root can be removed. */ public Object nonEmptyCase(BiTree host, Object... notUsed) { return _rightTree.execute(new IVisitor() { /** * At this point both the lef and right subtrees are empty. */ public Object emptyCase(BiTree h, Object... notUsed) { owner.setRootNode(_leftTree.getRootNode()); return _dat; } /** * Both left and right subtrees are not empty! Cannot remove root. */ public Object nonEmptyCase(BiTree h, Object... notUsed) { throw new IllegalStateException ("Both subtrees are non-empty"); } }); } }); } /** * Calls algo's nonEmptyCase() method to execute the algorithm algo. * @param owner the BiTree holding this DatNode. * @param algo an algorithm on owner. * @param inp the input algo needs. * @return the output for the nonEmptyCase() of algo. */ Object execute(BiTree owner, IVisitor algo, Object... inp) { return algo.nonEmptyCase (owner, inp); } }

3. The Best Tree Printing Algorithm in Texas

Consider the binary tree displayed in the following "horizontal" manner:

                                               62                   
                                 _______________|_________________
                                |                                 |  
                               20                                 7
                           _____|____________               ______|______
                          |                  |             |             |
                         [ ]                 18           [ ]           [ ]
                                    _________|______
                                   |                |
                                   39              [ ]
                               _____|_____
                              |           |
                             [ ]         [ ]

Such horizontal display of a tree is not very convenient when the tree is wide. It is more convenient to display the tree in a "vertical" manner.

The following visitor and its helper print the above tree "vertically" as shown below:

62
|_ 20
| |_ []
| |_ 18
|    |_ 39
|    |  |_ []
|    |  |_ []
|    |_ []
|_ 7
   |_ []
   |_ []

Let's study the algorithm.

Figure 5

(a) (b) /** * Computes a String representation of the binary tree host so * that it can be * printed vertically. * @author Dung X. Nguyen - Copyright 2005 - All rights reserved. */ public class ToString implements IVisitor { public final static ToString Singleton = new ToString (); private ToString () { } /** * Returns "[]", a String representation of an empty binary * tree. * @param host an empty binary tree. * @param nu not used. * @return String */ public Object emptyCase(BiTree host, Object... nu) { return "[]"; } /** * Computes a String representation of the binary tree host * so that it can be printed vertically. There is no '\n' * at the end of the String. Passes appropriate leftmost * leading String to a * helper visitor to compute the * String representations of the left and right subtrees. * @param host a non-empty binary tree. * @param nu not used. * @return String */ public Object nonEmptyCase(BiTree host, Object... nu) { String ls = (String)host.getLeftSubTree().execute(ToStringHelp.Singleton, "| "); String rs = (String)host.getRightSubTree().execute(ToStringHelp.Singleton, " "); return (host.getRootDat() + "\n" + ls + "\n" + rs); // EXERCISE FOR STUDENTS: Rewrite using anonymous inner classes. } } /** * Computes a String representation of the binary tree host so * that it can be printed vertically, given a leftmost leading * string for the two subtrees. * Called by ToString. * Should be implemented as an anonymous inner class in the * call by ToString. * @author Dung X. Nguyen - Copyright 2005 - All rights reserved. */ public class ToStringHelp implements IVisitor { public final static ToStringHelp Singleton = new ToStringHelp (); private ToStringHelp () { } /** * Returns "|_[]" to denote an empty tree subtree. * @param host an empty binary (sub)tree. * @param nu not used. * @return String */ public Object emptyCase(BiTree host, Object... nu) { return "|_ []"; } /** * Computes a String representation of the binary tree host * so that it can be printed vertically. * There is no '\n' at the end of the String. * @param host a non-empty binary (sub)tree. * @param leftLead[0] appropriate leftmost leading String to * help compute the * String representations of the left and right subtrees. * @return String */ public Object nonEmptyCase(BiTree host, Object... leftLead) { String ls = (String)host.getLeftSubTree().execute(this, leftLead[0] + "| "); String rs = (String)host.getRightSubTree().execute(this, leftLead[0] + " "); return ("|_ " + host.getRootDat()+ "\n" + leftLead[0] + ls + "\n" + leftLead[0] + rs); } }