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

58 thoughts on “Data structures example: the tree class”

  1. Hello

    First of all: thanks, I admire your work a lot, great stuff here.

    This may sound stupid but would help a lot of people: is there an example that shows a game development situation where the tree iterator class you wrote would fit perfectly?

    Keep up the good work!

  2. It could be used to store the plot line of a game. Let’s say you have a dungeon that has two exit doors – you could store the level structure into a tree, so when the player takes the left door instead of the right, he gets to another branch of dungeon levels.

    Another application for trees are BVHs (Bounding Volume Hierarchies) where a large object is split into smaller ones.

  3. This library looks great! I have been working on something similar for some game projects, but I may set it aside in favor of what you’ve done.

  4. Great work on the library.
    One question, is there a method in the Tree API to move children around, say for e.g while sorting ?

    Eg node A has three children 1, 2, 3
    I want to move the children such that they are in the order 2,3,1

    thanks

  5. All children are stored in a doubly linked list, so this is not possible because the linked list doesn’t support sorting yet. I’m trying to implement such a thing in the next release. The only thing you could right now is copying all children into an array to change their position, something like that:

    children_arr = myTree.children.toArray();
    myTree.children.clear();
    children_arr.sort(...)
    
    itr = myTree.getTreeIterator();
    for (i = 0; i < children_arr.length; i++) {
    	itr.appendChild(children_arr[i])
    }
    
  6. I used to use xml for situations when I need tree like effect, what does tree have to offer over xml?

  7. Nice work – am currently trying into implement a recursive tree builder so I can use it for a menu, but then later use the menu system to link to a 3D world.

    I’m currently trying things like this, but they’re not working. Anyone have some suggestions?


    private function walk(itr:TreeIterator, node:XML):void {
    // add this node to the itr as a sibling
    itr.appendChild(node.@label);
    //
    for each( var element:XML in node.elements()) {
    // add these nodes to itr as childen
    //itr.down();
    itr.appendChild(element.@label);
    trace(node.@label + "//" + element.@label);
    walk(itr, element);
    }
    itr.nextChild();
    //itr.up();
    }

  8. When I downloaded the examples I copied de folder inside it to use the class

    I opend TreeTraversal.fla and press CTRL + ENTER

    I get thes error
    1061: Call to a possibly undefined method destroy through a reference with static type de.polygonal.ds:TreeNode.

    that point to

    tree.destroy();

    SimpleTree is working fine

    but TreeIteration & TreeTraversal is not

    it give some errors

    like in TreeIteration

    error :
    1119: Access of possibly undefined property numChildrens through a reference with static type de.polygonal.ds:TreeNode.
    Source :
    trace(itr.node.numChildrens, itr.node.numSiblings);

    and two more errors,

    I havent change anything it should work !

  9. The TreeNode class was updated meanwhile, so the source in the example refers to a method which doesn’t exist anymore. just replace ‘destroy()’ with ‘clear()’ and it should work.

  10. Hi there..
    great piece of work…
    I wuestion though. I have downlaoded the source from the svn, and have create the example above.
    When I trace the dump() I have “almost” the same data.

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

    It seems that the down method is not going on the first node of the list, but indeed keep the reference of the last node inserted… :/
    So here the node 5 and 6 are children of node 3 instead of node 4…
    ++

  11. In the prependChild method, you should always call the childStart().
    So removing the if condition ( line 277 ) in the TreeIterator, seems to fix this…
    Anyway thx again for this great package

  12. Nice…
    Another thing. I wanted to be able to retreive the next / previous sibling of the current node. Can’t seem to be able to do it with the provided functions so I’ve created this one ( here nextSibling )

    public function nextSibling() : TreeNode
    {
    if ( node.hasSiblings() )
    {
    var siblings : DListIterator = node.parent.children.getListIterator();
    var itr : DListIterator = siblings.list.nodeOf( node );
    itr.forth();
    node = itr.data;
    return itr.data as VisualTreeNode;
    }
    return null;
    }

    Hope that make sence…
    ++

  13. Ooops..
    As you can see there is a VisualTreeNode reference left, change it to TreeNode
    And this function is sitting in the TreeNode class.

    Why a VisualTreeNode reference? I’m currently working on a component that will display the TreeNode :)

    Btw Michael, if we have the need to extends your classes and as we can’t override variables, you should use getter and setter for public access and use the protected namespace for the “internal” variables…

    ++

  14. Is there a member function whether in TreeNode or TreeIterator used to ‘reparent’ one tree_node to another in the same tree?

  15. // The solution… might not be perfect but works.

    public function appendChildNode(childnode:TreeNode):void
    {
    var itr_rpc:TreeIterator = childnode.getTreeIterator();
    itr_rpc.up();
    for (itr_rpc.childStart(); itr_rpc.childValid(); itr_rpc.nextChild())
    {
    if (itr_rpc.childNode == childnode)
    {
    itr_rpc.removeChild();
    break;
    }
    }

    childnode.parent = node;
    node.children.append(childnode);
    }

  16. Hi, great tutorials btw. I am trying out a couple of the examples and I notice that there are some calls to a destroy() method in TreeNode which no longer exists? I’m interested to know if it was taken out for a reason :)

  17. Hello Guys!
    Lovely piece of work, i am a bit weak in data structures :) so i want to know a couple of things:
    1) how can i find how many nodes are there on each level of my tree?

    2) How to do a breadth first traversal on the tree

  18. hi,

    1) just use the size property of a tree node
    2) breadth first traversal doesn’t make much sense for a tree, use TreeIterator.preorder and TreeIterator.postorder instead.

  19. Thanx Michael for your reply!
    but actually in my case, i need to know how many nodes are on a particluar depth of tree and i also need to use breadth first approach as i need to visually place the nodes to show a family tree hierarchy, i dont know how can preorder/postorder traversal can help me instead. the size property gives the total number of nodes of a tree i think and i need to know number of nodes at particular depth of tree, numSiblings will just give me the child node count of same parent but i need to get the entire noe level count.

    Thanx again for your time and my silly question, if you have a better solution then please do suggest me.
    Thanx

  20. i don’t understand the family tree thing, but size counts the total number of tree nodes starting at the node on which the method is called, so to get the number of nodes at a particular depth it should be fine to use size on the particular TreeNode to count all nodes below it.

  21. Hi Michael!

    Is there a simple way to make the DS classes persistent, for example serializing/deserializing to XML?

    Regards / Jonas

  22. Hi.

    Fantastic work. I appreciate it!
    In your examples, you seem to avoid extending the treenode class with draw functions as you would expect with the composite pattern.

    Is there a reason or am I missing something? It just seems to be what the treenode is all about.

    Thanks again!

    1. I don’t remember. But the code for the visuals were hacked together in a couple of hours so don’t expect beautiful code here ;-)

  23. Hi Mike
    Very that you go to haxe. Some people simple are constrained with adobe. :((. I want to ask you about opinion from your game experience. Is it smart to store floor maps as trees or graphs instead of standard array[i][j][k] for every cell. So you can apply A* later. We should count that some paths(nodes) could be change(with flag)/removed in real time like some blocking element or char. Other thing is beside that trees are fast for seraching we need direct access some time. So is it ok to maintain hashtable or Dictionary for direct access containing pointer to tree structure. Later for collision should keep for every element on stage should I maintain quadtree. Thx in front.
    I don’t like just things to work but work right.
    Regards
    Alex

  24. Hi, thanks for the work Michael.

    Here’s a little snippet for genereta Tree from XML data (without cloning TreeIterator ;-) ), if it can be usefull :

    private function createTreeFromXML( pXML:XML ):void
    {

    tree = new TreeNode({label:pXML.item.@name});
    itr = tree.getTreeIterator();

    walk(itr, XML( pXML.elements().toString() ) );

    //itr.root();
    refresh();

    stage.addEventListener(KeyboardEvent.KEY_DOWN, onKeyDown);
    }

    private function walk(pItr:TreeIterator, node:XML):void
    {
    // add this node to the itr as a sibling
    pItr.down();

    for each( var element:XML in node.elements())
    {
    // add these nodes to itr as childen

    pItr.appendChild({label:element.@name});
    trace(“//” + element.@name);

    walk( new TreeIterator(pItr.node), element);
    }
    }

  25. arf, this snippet doesn’t work perfectly, any help will be usefull here ;-)

  26. ok, so it work perfectly if i use prependChild instead of appendChild.
    But the bad news is that the xml data are reversed from left to right ;-(

    Any idea ?

  27. Hello every one!!!
    I have been using the TreeNode Class, and i think is very useful, but i need a function to paint the struct of the tree; like the example in this post.
    Help please……thanks

  28. I am having a heck of a time trying to make treeNode work. It appears the library has changed considerably since the above code was first post.
    In Flex, I am creating a TreeNode:
    var tree:TreeNode=new TreeNode(customFilters.getCustomFilters()[0].label);
    // above gets us a root
    var tempNode:TreeNode=new TreeNode(customFilters.getCustomFilters()[k].label) tree.appendNode(tempNode);
    // above gets us in this case 2 children..

    how the heck do I “get” to those children to append more children? i.e. each leaf can sprout 1-n children, etc.. going down..

    here is the trace of my tree:
    {TreeNode (root), children: 2, depth:0, value: root}
    +—{TreeNode (leaf|child), depth:1, value: child1}
    +—{TreeNode (leaf|child), depth:1, value: child2}

    1. The library has changed a lot since the I wrote this post. as3ds is no longer maintained so I can only give a haXe example using the ds library:

      var root = new TreeNode(0); //create the root of the tree

      var builder = new TreeBuilder(root);
      builder.appendChild(1);
      builder.down();
      builder.appendChild(2);
      builder.up();
      builder.appendChild(3);

      trace(root); //prints out:

      {TreeNode (root), children: 2, depth:0, value: 0}
      +—{TreeNode (child), children: 1, depth:1, value: 1}
      | +—{TreeNode (leaf+child), depth:2, value: 2}
      +—{TreeNode (leaf+child), depth:1, value: 3}

  29. by the way, the dump method no loner exists, right?

    i can´t print the whole tree using “trace” or “toString”

    1. if you compile against the ds_debug_xxx.swc file tracing a node dumps the subtree rooted at this node. if using haXe compile with -debug

    1. you could run a levelorder traversal and for each node, if node.depth() equals your target depth, store in the output array. abort the traversal when node.depth() > target depth.

  30. Hello! I’m a newbie here, and I’m making a checkers game in flash. What I don’t understand is how to store a move in a node. Would you help me please? Thank you! I understand the concept of trees and tree traversal but I don’t exactly know how to apply it in a real game. :)

  31. Hi. I’ve crashed my brain already.
    How to select node with the particular data value? Or there are the only way to search it with traversal?

  32. Example uses new ds library (http://code.google.com/p/polygonal/)

    //construct simple tree
    var root:TreeNode = new TreeNode(0);
    var builder:TreeBuilder = new TreeBuilder(root);
    builder.appendChild(1);
    builder.down();
    builder.appendChild(2);
    builder.up();
    builder.appendChild(3);
    
    //the easy way
    var node:TreeNode = root.find(2);
    
    //the hard way
    var myValue:int = 2;
    var myNode:TreeNode = null;
    root.preorder(function(node:TreeNode, preflight:Boolean, userData:*):Boolean
    {
        if (node.val == myValue)
        {
            myNode = node;
            return false;
        }
        return true;
    });
    trace(myNode);

    hope that helps.

  33. ok)) i’m learning haxe to use it ^_^’
    or i need translate/rewrite old files to use it with flashpro.
    So then — great thanks. Now i know where to move)))

Comments are closed.