Binary Trees,
Recursion Elimination,
and Enumerations
- Here is a program technically in C++, but really
entirely in the traditional C style. It defines a simple binary tree and
functions for inserting, searching, and printing all the contents in order.
Notice that the insert function takes and old tree as a parameter and returns
the new tree as its result; this is to avoid reference parameters which are
specific to C++, and too many pointers.
This is what happens when it is run.
- Here is an alternative version of the print function;
it makes the structure of the tree visible with parentheses (note how the
original version shows the order of the items, but gives no hint of the
shape of the tree).
This is what happens when it runs. The output is not
nice to look at, but at least all the information is there.
- Here is a cleverer version of the print function,
it actually draws the tree (sideways). Before each string, an extra character
appears, = to indicate the root, and / or \ to show where to draw the lines
that connect a node to its parent.
Here is the output. It is easier to understand if you
see the output with the complete lines drawn in, as in this
graphic.
- This version prints the tree the right way up. Although
the output produced looks more tree-like, it is not at all
easy to put in the special little characters / and \ to indictae which way
the lines should be drawn. This print function uses a kind of breadth-first
scan to run through the tree layer by layer.
Here is a
slightly more sophisticalted version that doesn't need to be told the maximum
number of levels to print.
- Here is a version of the insert function that uses
reference parameters. This makes it able to modify the node-pointer passed in,
and thus removes the need to return a result. Unfortunately reference parameters
are not available in plain C.
- This is what happens if that version of the function is
written in plain C. Reference parameters have to be converted to pointers, so
references to pointers become double pointers. Every time a function is called,
the address of the parameter must be provided (see how that messes up the
recursive calls). Every time the parameter is used, an extra pointer must be
followed.
- This shows how to remove a string from the tree. At
first sight, removing seems simple: just reverse what was done to add in the
first place. But remember that things are only added at the bottom level of the
tree. Removing something from the bottom level of a tree is as easy as you'd
expect, but removing something from the middle of the tree is more tricky.
This is how it works: To remove something that has no children, just remove
it. To remove something that has only one child (even if that child is itself
a whole big subtree) let the child replace the removed node. To remove something
that has two children, we can't leave a gap in the tree, so find something
from the bottom level of the tree (easy to remove) that could replace the removed
thing, and use it as a replacement. The smallest thing that is larger than the item to
be removed is guaranteed not to have two children, so is a suitable replacement.
- This shows the basic idea behind recursion elimination.
We simply simulate what the computer does with a normal recursive function. Make our
own version of the stack, the "LittleNote" objects exactly reflect the computer's
stack frames, containing values of local variables and a note of where to continue
execution when a function call is complete.
- This version is exactly the same as the above, except it
is based on a nicer, simpler version of the recursive print function.
- This takes the above version a little further. Instead of
having a non-recursive print function, we now have a non-recursive general
tree-exploring function, which a now-trivial print function makes use of.
- That idea, of a non-recursive function that can be used whenever needed
to get the next data item from a tree (or any other data structure) is a very
useful little thing, known as an Enumeration, shown here.
To run through the data stored in a tree, just create an enumeration for that tree,
then whenever more data is needed just ask the enumeration if it still has data
to give, and if it has, get that data from it.
- Finally, this shows non-recursive enumerations doing something
that the original recursive functions could never do: we have two totally independent
trees, and take data items from them one at a time, so that the first item from one tree is paired
with the first item from the other tree, etc., etc. Trivial with an enumeration,
almost impossible with recursion.
- Object orienting a binary tree definition takes a little thought. Here
is the beginning of a naive attempt. Everything seems OK until we find that dealing
with the empty tree (i.e. NULL) gets very unpleasant. This version of insert wasn't
going to be completely successful.
- Here we see a much happier object oriented binary tree. A simple
little object StringTreeNode represents all the structure of the tree and holds all the
data, and in fact works exactly as the non-object-oriented versions did. Then a special
wrapper object StringTree just contains one pointer to a StringTreeNode and has all the
expected methods. Thus when the tree is empty, and we have no StringTreeNodes, we will
still have a StringTree object to hold all the methods and gracefully continue to work.
