Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.


16.3 Binary Trees

This is an example of a recursive type and the effect it has on functions which manipulate this type of data. A binary tree is like a linked list, but instead of each element containing only one link to another element there are two links in each element of a binary tree (which point to smaller trees called branches). The first link points to the left branch and the second points to the right branch. Each element of the tree is called a node and there are two kinds of special node: the start point, called the root of the tree (like the head of a list), and the nodes which do not have left or right branches (i.e., NIL pointers for both links), called leaves. Every node of the tree contains some kind of data (just as the linked lists contained an E-string or E-list in each element). The following diagram illustrates a small tree.

            +------+
            | Root |
            +--*---+
              / \
        Left /   \ Right
            /     \
    +------*       *------+
    | Node |       | Node |
    +--*---+       +--*---+
      /              / \
Left /         Left /   \ Right
    /              /     \
+--*---+     +----*-+   +-*----+
| Leaf |     | Leaf |   | Leaf |
+------+     +------+   +------+

Notice that a node might have only one branch (it doesn't have to have both the left and the right). Also, the leaves on the example were all at the same level, but this doesn't have to be the case. Any of the leaves could easily have been a node which had a lot of nodes branching off it.

So, how can a tree structure like this be written as an E object? Well, the general outline is this:

OBJECT tree
  data
  left:PTR TO tree, right:PTR TO tree
ENDOBJECT

The left and right elements are pointers to the left and right branches (which will be tree objects, too). The data element is some data for each node. This could equally well be a pointer, an ARRAY or a number of different data elements.

So, what use can be made of such a tree? Well, a common use is for holding a sorted collection of data that needs to be able to have elements added quickly. As an example, the data at each node could be an integer, so a tree of this kind could hold a sorted set of integers. To make the tree sorted, constraints must be placed on the left and right branches of a node. The left branch should contain only nodes with data that is less than the parent node's data, and, similarly, the right branch should contain only nodes with data that is greater. Nodes with the same data could be included in one of the branches, but for our example we'll disallow them. We are now ready to write some functions to manipulate our tree.

The first function is one which starts off a new set of integers (i.e., begins a new tree). This should take an integer as a parameter and return a pointer to the root node of new tree (with the integer as that node's data).

PROC new_set(int)
  DEF root:PTR TO tree
  NEW root
  root.data:=int
ENDPROC root

The memory for the new tree element must be allocated dynamically, so this is a good example of a use of NEW. Since NEW clears the memory it allocates all elements of the new object will be zero. In particular, the left and right pointers will be NIL, so the root node will also be a leaf. If the NEW fails a "MEM" exception is raised; otherwise the data is set to the supplied value and a pointer to the root node is returned.

To add a new integer to such a set we need to find the appropriate position to insert it and set the left and right branches correctly. This is because if the integer is new to the set it will be added as a new leaf, and so one of the existing nodes will change its left or right branch.

PROC add(i, set:PTR TO tree)
  IF set=NIL
    RETURN new_set(i)
  ELSE
    IF i<set.data
      set.left:=add(i, set.left)
    ELSEIF i>set.data
      set.right:=add(i, set.right)
    ENDIF
    RETURN set
  ENDIF
ENDPROC

This function returns a pointer to the set to which it added the integer. If this set was initially empty a new set is created; otherwise the original pointer is returned. The appropriate branches are corrected as the search progresses. Only the last assignment to the left or right branch is significant (all others do not change the value of the pointer), since it is this assignment that adds the new leaf. Here's an iterative version of this function:

PROC add_iter(i, set:PTR TO tree)
  DEF node:PTR TO tree
  IF set=NIL
    RETURN new_set(i)
  ELSE
    node:=set
    LOOP
      IF i<node.data
        IF node.left=NIL
          node.left:=new_set(i)
          RETURN set
        ELSE
          node:=node.left
        ENDIF
      ELSEIF i>node.data
        IF node.right=NIL
          node.right:=new_set(i)
          RETURN set
        ELSE
          node:=node.right
        ENDIF
      ELSE
        RETURN set
      ENDIF
    ENDLOOP
  ENDIF
ENDPROC

As you can see, it's quite a bit messier. Recursive functions work well with manipulation of recursive types.

Another really neat example is printing the contents of the set. It's deceptively simple:

PROC show(set:PTR TO tree)
  IF set<>NIL
    show(set.left)
    WriteF('\d ', set.data)
    show(set.right)
  ENDIF
ENDPROC

The integers in the nodes will get printed in order (providing they were added using the add function). The left-hand nodes contain the smallest elements so the data they contain is printed first, followed by the data at the current node, and then that in the right-hand nodes. Try writing an iterative version of this function if you fancy a really tough problem.

Putting everything together, here's a main procedure which can be used to test the above functions:

PROC main() HANDLE
  DEF s, i, j
  Rnd(-999999)    /* Initialise seed */
  s:=new_set(10)  /* Initialise set s to contain the number 10 */
  WriteF('Input:\n')
  FOR i:=1 TO 50  /* Generate 50 random numbers and add them to set s */
    j:=Rnd(100)
    add(j, s)
    WriteF('\d ',j)
  ENDFOR
  WriteF('\nOutput:\n')
  show(s)         /* Show the contents of the (sorted) set s */
  WriteF('\n')
EXCEPT
  IF exception="NEW" THEN WriteF('Ran out of memory\n')
ENDPROC


Go to the Next or Previous section, the Detailed Contents, or the Amiga E Encyclopedia.