Binary Trees

Here are some examples:

Exercise 1:  Examine the tree T1 above to see if you find any pattern or order to the arrangement.  Can you think of any interpretation of the structure of T1?
 
Exercise 2:  Examine the tree T2 above to see if you find any pattern or order to the arrangement.  Can you think of any interpretation of the structure of T2?
 
Exercise 3:  Examine the tree T3 above to see if you find any pattern or order to the arrangement.  Can you think of any interpretation of the structure of T3?

Exercise 4:  Examine the tree T4 above to see if you find any pattern or order to the arrangement.  Can you think of any interpretation of the structure of T4? (Hint: consider a rule for going left and right based on a binary sequence - 0 means left, 1 means right.)
 

A Tree Node

public class TreeNode
{
  private Object value;
  private TreeNode left;
  private TreeNode right;

  public TreeNode(Object initValue)
  {
    value = initValue;
    left = null;
    right = null;
  }

  public TreeNode(Object initValue, TreeNode initLeft, TreeNode initRight)
  {
    value = initValue;
    left = initLeft;
    right = initRight;
  }

  public Object getValue()
  {
    return value;
  }

  public TreeNode getLeft()
  {
    return left;
  }

  public TreeNode getRight()
  {
    return right;
  }

  public void setValue(Object theNewValue)
  {
    value = theNewValue;
  }

  public void setLeft(TreeNode theNewLeft)
  {
    left = theNewLeft;
  }

  public void setRight(TreeNode theNewRight)
  {
    right = theNewRight;
  }  
}

With this definition, the following declaration of a node would create a new node containing the string "example".

node = new TreeNode("example", null, null);

At this point in the code node would contain the string "example" in its data field and both its child references would be null, meaning it has no children.
 

Creating a Binary Tree

The simplest means of adding a node to a tree is to create a new node with both child pointers null and make it the child of a node in the tree with at least one null child. Typically the function that adds a node to a binary tree returns a references to the node where the insertion has occurred. In this way if the original node is null, the method can create and return a node to replace the null reference; otherwise it returns the original node. Different patterns can be developed, depending on how the attachment location is selected   Here is one example:

TreeNode insert(TreeNode node, String name)
{
  if(node == null)
    return new TreeNode(name, null, null);
  else if(name.compareTo(node.getValue()) < 0){
    node.setLeft(insert(node.getLeft(), name));
  else
    node.setRight(insert(node.getRight(), name));

  return node;
}

Note how the search for an insertion point is done recursively.  This is quite common.

Exercise 4:  Which of the example trees T1, T2, T3, T4 given above could have been created with this insertion function?

Here is a second example of creating a tree by reading in a sequence of data to be placed in the nodes (in this case string tokens from a StringTokenizer).

TreeNode createTree(StringTokenizer in)
{
  TreeNode root;

  Queue nodeQueue = new QueueAL();
  TreeNode node;
  String name;

  if(in.hasMoreTokens()){
    root = new TreeNode(in.nextToken(), null, null);
    nodeQueue.enqueue(root);
    while(in.hasMoreTokens()){
      nodeQueue.dequeue(node);
      node.setLeft(new TreeNode(in.nextToken(), null, null));
      nodeQueue.enqueue(node.getLeft());
      if(in.hasMoreTokens()){
        node.setRight(new TreeNode(in.nextToken(), null, null));
        nodeQueue.enqueue(node.getRight());
      }
    }
  }
  return root;
}

Exercise 5:  If the StringTokenizer in contains the following names, draw the tree that would be formed by a call to createTree:
Corinne, Evan, Gretchen, Kellyn, Marlene, Matt, Sameer, Shannon, Tyler.

Tree Traversals

For trees, traversals are most commonly (but not exclusively) done using recursion.  Think of traversing a tree as the following three operations, in no particular order:

1.  Visit the item stored at this (root) node.
2.  Traverse the left sub-tree
3.  Traverse the right sub-tree.

If we have defined a function visit, which carries out the operation on a node of a tree for a traversal, then we could implement a traversal of a tree, using a function traverse, as follows:

void traverse(TreeNode t)
{
1   if(t != null){
2     visit(t);
3     traverse(t.getLeft());
4     traverse(t.getRight());
  }
}

In line 1 we check for a null reference, in which case this (sub)tree is empty and there is nothing to be done.  Then lines 2, 3, 4, carry out the steps suggested above.  Note that there is nothing magic about the order of steps 2, 3, 4.  If we did these operations in a different order we would traverse the whole tree, but visit the nodes in a different order.  Sometimes the order of the visits is important, in which case we need to select the ordering of steps 2, 3, 4 correctly.

There are six ways in which the three steps can be placed in order.  Three of those orderings are commonly used and are given names.  We usually view trees with a crude sense of order, namely that the left side comes before the right side, so the three common traversal orderings always have the recursive call to traverse the left subtree before the recursive call to traverse the right subtree.  Then there are three variations:

• preorder traversal        visit the root node first, then go left, then go right
• inorder traversal          go left, visit the root node, then go right
• postorder traversal      go left, go right, visit the root node

void preorder(TreeNode t)
//  executes a preorder traversal of the tree t
{
  if(t != null){
    visit(t);
    preorder(t.getLeft());
    preorder(t.getRight());
}

void inorder(TreeNode t)
//  executes an inorder traversal of the tree t
{
  if(t != null){
    inorder(t.getLeft());
    visit(t);
    inorder(t.getRight());
}

void postorder(TreeNode t)
//  executes a postorder traversal of the tree t
{
  if(t != null){
    postorder(t.getLeft());
    postorder(t.getRight());
    visit(t);
}

For example, if the function visit simple printed the contents of the node, we could use each of these to traverse the list given in example T1 above and print it out:

void visit(TreeNode t)
{
  System.out.println(t.getValue());
}

 Exercise 6:  Write out the list which would be printed for each of the three traversals using the given Visit function applied to the tree T1 above.