Monday, March 9, 2009

*-ary tree structure

I'm in the process of creating a *-ary or N-ary tree structure, where N can be any number. It's a tree with any number of children allowed, simply because I do not like to program limitations into my code.

I'm going to use this tree structure to represent a Top Down File menu. I'm not 100% sure, but I believe this tree may prove useful for a scene graph structure as well.

This tree structure is going to be the heart of my Top Down File menu widget for my GUI. I stuck the development version directly in the trunk.

Is anyone aware of a 'standard' N-ary tree? I've found out about the K-ary tree where K is a konstant, but haven't had any luck in finding a standard way of making a *-ary tree. Also, there is no Tango equivalent that I am aware of.

4 comments:

h3r3tic said...

The quad-linked tree structure is what I like the most. It allows O(1) child insertion, removal, O(n) iteration and avoids dynamic memory allocation. Search this gamedev thread for the keyword "quad-linked". This is where I've originally learned about it.

Clay Smith said...

Thanks, I may give that a try.

Mason said...

In addition to the QuadTree, you might want to consider a Bounding Volume Hierarchy (BVH).

h3r3tic said...

It's not a QuadTree, Mason :P It's an n-ary tree. Check the link I've posted.