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.