Data structures example: the tree class
May 15, 2007 on 11:30 pm | In Actionscript, data structures |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
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!
Comment by carlos — May, 16 2007 #
[...] Polygonal Labs has a tree sample up that has many possible usages from visualization of game states to building node based editors to anything really in game development.  I could easily see a mix of this and scene creation in papervision via a flash application/IDE. [...]
Pingback by [ draw.logic ] AS3 Data Structures for Game Development by Polygonal Labs « — May, 16 2007 #
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.
Comment by mike — May, 16 2007 #
[...] pattern point of view. Everything has ASDoc supported comments. He even has a nice tutorial on using the Tree Class and it seems he might be adding more tutorials later. Nice work [...]
Pingback by NateJC.com - Flash & ActionScript 3 info, source, & experiments » Blog Archive » ActionScript 3 Data Structures — May, 19 2007 #
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.
Comment by adampasz — May, 27 2007 #
[...] polygonal labs » Data structures example: the tree class ã“れ使ãˆãÂÂã†。 (tags: tree as3 library flash) [...]
Pingback by links for 2007-05-29 « test — May, 29 2007 #
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
Comment by superabe — July, 20 2007 #
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]) }Comment by Michael — July, 21 2007 #
I used to use xml for situations when I need tree like effect, what does tree have to offer over xml?
Comment by Mahmoud — January, 1 2008 #
[...] i googled and found an excelent peace of work. A Tree class created by Michael Baczynski from Polygonal Labs. I decided to have a good look at it even-though the data-structure package is written in [...]
Pingback by bushbaby blog » Blog Archive » datastructure tree — January, 22 2008 #
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();
}
Comment by Vish — April, 10 2008 #
Hi Vish,
I have an assumption, you have to copy the TreeIterator. In your version you committed a TreeIterator Reference. This TreeIterator Reference contains the false node reference for the new walk function cycle.
Here is a good Link for Deep Object Copies with ByteArray:
http://www.kirupa.com/forum/showthread.php?p=1897368
Comment by Flo — May, 6 2008 #
Thanks for that - I shall have a go :)
Comment by Vish — May, 6 2008 #
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 !
Comment by MJ — June, 20 2008 #
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.
Comment by Michael — June, 20 2008 #
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…
++
Comment by zeflasher — July, 30 2008 #
just to be notified when new comments are created
Comment by zeflasher — July, 30 2008 #
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
Comment by zeflasher — July, 30 2008 #
you are right, this was a bug - fixed in SVN :-)
Comment by Michael — August, 1 2008 #
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…
++
Comment by zeflasher — August, 1 2008 #
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…
++
Comment by zeflasher — August, 1 2008 #
Is there a member function whether in TreeNode or TreeIterator used to ‘reparent’ one tree_node to another in the same tree?
Comment by Purga — September, 24 2008 #
// 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);
}
Comment by Purga — September, 27 2008 #
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 :)
Comment by dezza — October, 4 2008 #
[...] opensource package from Michael Baczynksy at polygonal.de for the use of lists, queues, stacks and trees . While it works great, it has some explicit design decisions that we do not want to follow, mainly [...]
Pingback by The collections package at dpdk Open Source — October, 10 2008 #
good question - I forgot the reason.. but I think the method wasn’t really needed for garbage collection.
Comment by Michael — October, 10 2008 #
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
Comment by Syed Mazhar Hasan — December, 16 2008 #
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.
Comment by Michael — December, 24 2008 #
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
Comment by Syed Mazhar Hasan — December, 24 2008 #
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.
Comment by Michael — December, 25 2008 #
ok thanx anyways, actually i was trying to make something like the family tree graph as in http://www.geni.com
Comment by Syed Mazhar Hasan — December, 25 2008 #
Hi Michael!
Is there a simple way to make the DS classes persistent, for example serializing/deserializing to XML?
Regards / Jonas
Comment by Jonas Nyström — June, 25 2009 #
this not supported, you have to write something on your own..
Comment by Michael — July, 10 2009 #
Thanks sir!!!!
Comment by Mitchell Morris — August, 28 2009 #
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!
Comment by Rick — October, 31 2009 #
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 ;-)
Comment by Michael — November, 3 2009 #
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
Comment by Alex — November, 6 2009 #
this is a difficult question, since it depends on so much things…I would go with the dictionary approach you mentioned.
Comment by Michael — November, 13 2009 #
[...] He’s also writing examples on how some of the classes are used, for example Queue and Tree. The hexagon framework will contain similar data structure classes but they will adhere more to [...]
Pingback by AS 3.0 Data Structures For Game Developers - H1DD3N.R350URC3 — November, 19 2009 #