Go Premium for a chance to win a PS4. Enter to Win

x
?
Solved

multiway/n-ary tree

Posted on 2002-07-19
2
Medium Priority
?
1,514 Views
Last Modified: 2012-06-21

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.
0
Comment
Question by:VEngineer
2 Comments
 
LVL 3

Accepted Solution

by:
gandalf94305 earned 400 total points
ID: 7165984
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
 

Expert Comment

by:sgoldgaber
ID: 7861241
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

Featured Post

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

If you’re thinking to yourself “That description sounds a lot like two people doing the work that one could accomplish,” you’re not alone.
If you are a mobile app developer and especially develop hybrid mobile apps then these 4 mistakes you must avoid for hybrid app development to be the more genuine app developer.
An introduction to basic programming syntax in Java by creating a simple program. Viewers can follow the tutorial as they create their first class in Java. Definitions and explanations about each element are given to help prepare viewers for future …
Introduction to Processes

772 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question