12.5 Binary Trees

Although linear lists are useful for many applications, more complex structures are often required. In this section, we will begin to examine another extremely useful data type -- the binary tree.

Example 1

The following diagram shows a binary tree containing the nodes A, B, ..., I.

In talking about trees, the terminology is taken partially from family trees and partially from organic trees. Considering the tree shown in Example 1 as a family tree, the nodes F and G are the children of C, with F being the left child and G being the right child. Since F and G both have C as a parent, they are siblings. From organic trees, we get the terms root and leaf. The node A is the root of the tree while H, E, F, and I are the leaves. (In computer science, trees usually grow upside down.) The root is the only node that has no parent while the leaves are the only nodes that have no children.

The nodes B, D, E, and H form the left subtree of the tree while C, F, G, and I form the right subtree. Each subtree is itself a tree so that, for example, B, D, E, and H form a binary tree whose root is B.

To implement a binary tree, we can use arrays but, in this text, we will only be looking at linked allocation. To start a Tree class, we need one field, a reference to the root of a tree. 

class Tree
{
    private Node root;
}

We present objects of type Tree by diagrams like the following:

A node of the tree will need three fields: a link to the node's left child (or null if there is no left child), a link to the node's right child (or null if there is no right child), and an information field. As with linked lists, this field will, in practice, be a reference to some object but, for demonstration purposes, we will simply store integers into our info fields. To start our Node class, we give it the required fields and a simple constructor: 

class Node
{
    int info;
    Node lChild, rChild;

    Node (int i, Node l, Node r)
    {
        info = i;
        lChild = l;
        rChild = r;
    }
}

Objects of the Node class will be represented by diagrams like the following:




Example 2

Using the Tree and Node classes, the implementation of the binary tree shown in the previous example would have the structure shown in the next diagram. The nodes are labelled with the same letters used in the previous example.

Operations on binary trees are most easily performed using recursion. As we saw in the previous section, it is useful, if we want to develop recursive algorithms for processing a data structure, to first look at that structure recursively. We can do this here by defining the structure of the ADT binary tree as: a set of nodes that is either empty or, if not empty, contains a node called the root together with two disjoint binary trees: the left subtree of the root and the right subtree of the root.

Recursive algorithms for operating on binary trees reflect this form by processing the root directly and processing the left and right subtrees recursively with an empty tree acting as a stopping condition on the recursion.

As a simple illustration of recursion with a binary tree, consider the problem of performing a traversal of a tree. In a traversal, we want to visit each node of the tree, performing some task such as printing the data in each node as we carry out our visitation. If we want to traverse a binary tree, there are many possible orders in which we can visit the nodes. (For a tree containing ten nodes, for example, there are 3,628,000 possible orderings.) Of these many orderings, only a few are commonly used. Three of the most common orderings are very similar. In each of them, the left subtree is traversed before the right subtree. The only difference among the three is the point at which the root is visited. The outlines and names of the orderings are shown in the table.

The names are derived from the point at which the root is visited relative to the traversal of the two subtrees: pre (before), in (between), or post (after) the subtrees.

A recursive algorithm for an inorder traversal of a binary tree could take the following form.

To TRAVERSE THE TREE
    if the tree is not empty
        TRAVERSE THE LEFT SUBTREE
        visit the root
        TRAVERSE THE RIGHT SUBTREE

As we did for recursive operations on linked lists, we can break up the task here into two parts: a non-recursive method in the Tree class to process the case of an empty tree and a recursive version in the Node class to process non-empty binary trees.

Example 3

Suppose that a binary tree is implemented using the data structure in the previous example. To print info fields of such a tree using an inorder traversal, we could use the following methods.
First, in the Tree class,

public void inPrint()
{
    if (root != null)
        root.inPrint();
}

Then, in the inner Node class,

void inPrint()
{
    if (lChild != null)
        // print non-empty left subtree
	lChild.inPrint();

    System.out.println(info);

    if (rChild != null)
	// print non-empty right subtree
	rChild.inPrint();
}



Exercise 12.5

  1. For the binary tree shown in the diagram, identify each of the following.
    1. the root of the tree
    2. the leaves of the tree
    3. the nodes of the left subtree
    4. the children of the root of the right subtree
    5. a pair of siblings
    6. the nodes of the left subtree of the right subtree of the root
    7. a node with no parent
    8. the left child of the root of the left subtree
  2. In what order would the nodes of the following tree be visited using
    1. an inorder traversal?
    2. a postorder traversal?
    3. a preorder traversal?
  3. The diagram shows an expression tree with operands at the leaves and operators at the other nodes.
    1. The value of a non-empty expression tree is obtained by applying the operator at the root to the value of the left subtree and the value of the right subtree. Find the value of the given expression tree.
    2. In what order would the nodes of the tree be visited using
      1. a preorder traversal?
      2. an inorder traversal?
      3. a postorder traversal?
    3. An expression tree, visited in postorder, gives the following expression
        2 3 + 5 4 2 - + x
      Draw the expression tree and find its value.
  4. The following method for the Tree class starts the process of finding the sum of the info fields of a binary tree of the type discussed in this section. 
    public int sum()
{
    if (root == null)
        return 0;
    else
        return root.sum();
}
    1. Write the definition of a recursive method sum for the Node class that will complete the process.
    2. What happens if the tree is empty?
    3. Explain why two versions of sum are used.