Data structures example: the tree class

First, I have updated the data structures source to version 0.7.3, so make sure you have the latest version. The source code for the SWFs in this post can be obtained here (Flash CS3 required).

Using the tree iterator

Before we build a tree its important to understand how the tree iterator works. Normally the iterator is used to iterate over the structure’s data – in this case the iterator additionally acts as a ‘marker’ and points to the node at which we may modify the tree.
Also, the tree iterator is somewhat special, because it allows you to iterate through the tree in two directions: horizontally and vertically. Therefore it has to manage two node references simultaneously, making it more complex than other iterators.

In the figure below, the purple colored node is the vertical iterator and is used to move up and down the tree using the treeNodeInstance.parent property, while the blue node is obviously the horizontal iterator and can only step left and right through the node’s children.

I think a simple demonstration is worth more than thousand words, so you can try it yourself by playing around with the tree using the keys below (first click the flash to get focus):

up/down, left/right: moves the vertical (V) and horizontal (H) iterator
home: deletes the whole tree
a: appends a child node to the (V) node
i: inserts a node after the (H) node
d: recursively removes all child nodes from the (V) node
r: removes the (H) node

Building a simple tree

Now let’s look how to build a tree in ActionScript. First we create the root of the tree and get an iterator pointing to this node:

var tree:TreeNode = new TreeNode("root");
var itr:TreeIterator = tree.getTreeIterator();

The root has three children, so lets add them:

for (var i:int = 0; i < 3; i++)
{
    itr.appendChild("node" + i);
}

Now the root’s second child (‘node1’) has children by itself. To insert them, we first have to adjust the vertical iterator so it points to ‘node1’. First one step to the right, then one step down the tree:

itr.nextChild();
itr.down();

Now we can add ‘node3’ and ‘node4’, this time in a reverse order:

itr.prependChild("node" + 3);
itr.prependChild("node" + 4);

The first time we add a child node to an empty node, the horizontal iterator is automatically initialized to point to the first child, which in this case is ‘node4’. So to create ‘node5’ and ‘node6’ we only need to go another step down.

itr.down();
itr.appendChild("node" + 5);
itr.appendChild("node" + 6);

Finally we want to add ‘node7’. Therefore we ‘bubble up’ the tree until we arrive at the root node, go to the rightmost child, one step down and add it:

itr.root();
itr.childEnd();
itr.down();
itr.appendChild("node" + 7);

The dump() method invoked on the root node prints out the complete tree, as you can see it matches the tree above.

[TreeNode > (root) has 3 child nodes, data=root]
+---[TreeNode > (leaf), data=node0]
+---[TreeNode >  has 2 child nodes, data=node1]
|    +---[TreeNode >  has 2 child nodes, data=node4]
|    |    +---[TreeNode > (leaf), data=node5]
|    |    +---[TreeNode > (leaf), data=node6]
|    +---[TreeNode > (leaf), data=node3]
+---[TreeNode >  has 1 child nodes, data=node2]
|    +---[TreeNode > (leaf), data=node7]

Preorder and postorder traversal

Now that you have created a tree structure, you need a way of traversing the nodes so you access the node’s data. There are two common recursive algorithms for doing this. The preorder function first visits the node that is passed to the function and then loops through each child calling the preorder function on each child. The postorder on the other hand does the opposite: It visits the current node after its child nodes.
To see this in action just click a node in the demo below. The numbers indicate the order in which the nodes are visited.

The TreeNode class also supports a regular iterator using hasNext() and next(). This matches the preorder iterator, but is implemented in a non-recursive way.

See also:
Linked lists
The queue class
The graph class