Computer Science
Trees

What Is A Tree?

A tree is a dynamic data structure in which data is stored in a hierarchical manner.

tree image

In the above diagram, each part of the tree that contains information (the boxes) is called a node. The first node (in this diagram - 'Computing') is called the root node. The lines which connect each of the boxes are called branches. Some nodes have child nodes - they connect to nodes on the level below. Nodes that don't have children are called leaf nodes.

A tree is very similar to a graph. In fact, we could say that the tree shown above is a connected, undirected graph. This particular tree is a rooted tree. All of the edges are directed away from the root node.

Binary Trees

A binary tree is a special type of tree where each node is allowed a maximum of 2 children. You construct a binary tree by placing the first data item as the root node. For each subsequent item, branch to the left if it is less than the root node, branch to the right if it is greater. Apply this branching rule at each node that is met unitl the item can be placed.

Do this with the following names,

Partridge, Duckworth, Smith, Arkwright, Wren, Thumbface, McJack.

You should end up with a tree diagram that looks like this,

tree image

Starting from the root node, if you were searching for Thumbface, which items would you need to access?

Make another tree with the following captial cities,

London, Paris, Washington, Canberra, Lima, Madrid, Lisbon.

Which data items would be accessed if you were searching for Madrid?

Traversing The Tree

There are a variety of methods used for traversing the tree to produce sorted output. The following traversal methods produce output in different orders.

  • Pre-Order Traversal
  • In-Order Traversal
  • Post-Order Traversal

A diagrammatic representation of how to construct a binary search tree, as well as the different traversal methods, can be found by clicking or downloading the following PowerPoint slideshow. DOWNLOAD BINARY TREE SIMULATION

Javascript Binary Tree Simulation

Remember that the diagrams shown in the slideshow are simply a way of representing the structure of the tree. In order to program with the tree, there is no need to replicate the visuals. In the example below an array of records is used. Each record has 3 properties, a name, a left pointer and a right pointer. The pointers indicate the address of the left or right child of a node. Add some names and watch how the pointers change as each item is added. Then press the buttons and see how they are sorted.

 







Binary Tree Algorithms

The simulation on this page uses an array of records to manage the items in the binary tree. The structure definition is shown in C#, the remaining algorithms are pseudocode.

Record Definition & Global Variables

public struct TreeItem {
   public int left;
   public int right;
   public string name;
}
int maxsize = 15;
TreeItem[] treeitems = new TreeItem[maxsize];

Inserting Items In The Tree

Two procedures are used. The first checks that the tree is full and, if not then looks to see if this is the first item (root node) of the tree. If this is the root node it creates it, no fuss involved since the root node initially points to 0. If the node is not the root, the second procedure is called. This procedure is recursive, walking through the tree following the left/right rules changing the appropriate pointer of the parent node.

Procedure InsertItem(itm)
   IF treeitems.length = maxsize THEN Exit Procedure
   IF treeitems.length = 0 THEN
   treeitems[0] = new TreeItem(itm)
   ELSE
      treeitems[treeitems.length] = new TreeItem(itm)
      ChangePointers(treeitems.length - 1, 0)
   END IF
End Procedure Procedure ChangePointers(a,b)
   IF treeitems[a].name < treeitems[b].name THEN
      IF treeitems[b].left = 0 THEN
         treeitems[b].left = a
      ELSE
         ChangePointers(a, treeitems[b].left)
      END IF
   ELSE
      IF treeitems[b].right = 0 THEN
         treeitems[b].right = a
      ELSE
         ChangePointers(a, treeitems[b].right)
      END IF
   END IF
End Procedure

In-Order Traversal

The procedure for in-order traversal is recursive. The first call to this procedure would be InOrderPrint(0).

Procedure InOrderPrint(a)
   IF treeitems[a].left <> 0 THEN
      InOrderPrint(treeitems[a].left)
   END IF
   Print treeitems[a].name
   IF treeitems[a].right <> 0 THEN
      InOrderPrint(treeitems[a].right)
   END IF
End Procedure

Pre-Order Traversal

Procedure PreOrderPrint(a)
   Print treeitems[a].name
   IF treeitems[a].left <> 0 THEN

      PreOrderPrint(treeitems[a].left)

   END IF

   IF treeitems[a].right <> 0 THEN

      PreOrderPrint(treeitems[a].right)

   END IF

End Procedure

Post-Order Traversal

Procedure PostOrderPrint(a)
   IF treeitems[a].left <> 0 THEN

      PostOrderPrint(treeitems[a].left)

   END IF

   IF treeitems[a].right <> 0 THEN

      PostOrderPrint(treeitems[a].right)

   END IF

   Print treeitems[a].name
End Procedure