Solved

multiway/n-ary tree

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

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

Suggested Solutions

Title # Comments Views Activity
linearIn  challenge 23 65
squareUp  challenge 22 105
VBA color chart bars 12 65
Adoquery sql  left join does not work 25 45
Here we come across an interesting topic of coding guidelines while designing automation test scripts. The scope of this article will not be limited to QTP but to an overall extent of using VB Scripting for automation projects. Introduction Now…
This is about my first experience with programming Arduino.
In this fourth video of the Xpdf series, we discuss and demonstrate the PDFinfo utility, which retrieves the contents of a PDF's Info Dictionary, as well as some other information, including the page count. We show how to isolate the page count in a…
In this seventh video of the Xpdf series, we discuss and demonstrate the PDFfonts utility, which lists all the fonts used in a PDF file. It does this via a command line interface, making it suitable for use in programs, scripts, batch files — any pl…

707 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now