$ cat /home/buntine/mind_melting_brilliance

This is the first part of a two (maybe three) part series on tree data structures in Scheme.

In many programming problems, an efficient way of organising data is in a tree-like structure. In essence, a tree in this sense consists of a root node, followed by zero or more sub-nodes, each of which can be followed by a set of further nodes. Common terminology for this node/subnodes relationship is mother and children, respectively. Other common terms are root/branch/leaf.

A picture is a great way to provide an example of such a structure:

The tree above is quite simple. It consists of a root node, followed by two children. The first child contains no further children (a leaf), and the second child is the parent to one child. An important thing to realise at this point is that every child is infact a perfectly valid tree in and of itself. We can see this in more detail a bit further on.

Representing such a structure in Scheme (or any implementation of LISP) is really quite easy. We use the obvious building block: lists. The tree in the image above would be encoded as:

'(a (b) (c (d)))

As I mentioned before, if we snap off the branches from the root node, we are left with a set of new trees; a forest. In LISP terms, the cdr of a tree is a list of lists:

'((b) (c (d)))

The first item in this list is a tree with only a root node. Not a very useful tree, but a tree none-the-less. The second; a tree with a root node and a single child element. The reason I've brought this up is because it shows us that there is most certainly a convenient recursive way to deal with such a structure (this I will talk about in the next article).

To help us with creating trees and get our terminology contextually proper, we can define the following helper procedures:

(define (tree root . children)
  (cons root children))

(define (leaf-node node)
  (tree node))

So, with these new procedures in place, lets create a basic tree structure:

> (define family-tree
          (tree 'family
                (tree 'karl
                      (leaf-node 'oak))
                (tree 'colin
                      (leaf-node 'celine)
                      (leaf-node 'ashin))))

> family-tree
  (family (karl (oak)) (colin (celine) (ashin)))

In the next article I'll talk about a cool way of recursively parsing such a structure.