Solved

multiway/n-ary tree

Posted on 2002-07-19
2
1,476 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 100 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

Free Tool: Postgres Monitoring System

A PHP and Perl based system to collect and display usage statistics from PostgreSQL databases.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

Question has a verified solution.

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

Suggested Solutions

Since upgrading to Office 2013 or higher installing the Smart Indenter addin will fail. This article will explain how to install it so it will work regardless of the Office version installed.
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.

830 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