multiway/n-ary tree


I've been looking for any kind of API/class for a multiway/n-ary tree.  So far in the books and websites, I've seen, the representation of a node consists of a pointer to the first child and a pointer to the next sibling, i.e.:

struct TreeNode {
     TreeNode* firstChild;
     TreeNode* nextSibling;
     TreeNode* parent;  // optional
};

My question is, where can I find some example implementations of the actual multiway/n-ary tree class?  In fact, all I need is some sample interfaces that have functions that will help traverse/insert/remove the tree.  I know how to insert items into a binary search tree, but in a multiway tree, there's no such thing as the binary search property (smaller items go left, larger items go right), so I can't find a way to easily navigate the tree.

Any suggestions in the form of links, book reccommendations, papers, sample libraries for whatever language will be useful to me.  I've searched on the Internet for a while now and have come up with few things at all.
LVL 2
VEngineerAsked:
Who is Participating?
 
gandalf94305Commented:
N-ary trees are used to implement directory/file structures. Depending on the complexity of parent/child relationships, you will find one of three approaches to organize the children:

- array (simple to traverse, insert/delete operations are more costly, rather compact and space-efficient)
- linked list/doubly-linked list (traversal is more expensive, easy insert/delete operations, space allocation can be dynamic from a heap)
- hash table (simple to traverse, easy insert/delete, requires more storage space though).

Sibling information (if stored at all in a node and not just made available via the parent) is normally stored as a doubly-linked list, i.e., *previousSibling, *nextSibling, to ease traversal.

This way, you get one threading for the parent/child relationship, and optionally a second for the sibling chain.

As for implementations of this, I could provide some Java code but this does seem to be not overly complex to implement as it basically boils down to maintain the respective underlying data structures (arrays, linked lists, doubly-linked lists, hashtables).

Cheers,
--gandalf.
0
 
sgoldgaberCommented:
VEngineer,

I had the same question as you, so I scoured the net far and wide for useful implementations of n-ary trees.

Here is what I found:

The GTK project (http://www.gtk.org/) has the most general and useful implementation:
http://developer.gnome.org/doc/API/2.0/glib/glib-N-ary-Trees.html

The Flux library has an implementation that they call "token trees":
http://www.fluxlib.org/

Yet another implementation is in the HiM, "Hierarchical Marshalling Library", at:
http://www.sama.ru/~despair/him/
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.