Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

multiway/n-ary tree

Posted on 2002-07-19
2
Medium Priority
?
1,504 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
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

Build and deliver software with DevOps

A digital transformation requires faster time to market, shorter software development lifecycles, and the ability to adapt rapidly to changing customer demands. DevOps provides the solution.

Question has a verified solution.

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

The SignAloud Glove is capable of translating American Sign Language signs into text and audio.
We live in a world of interfaces like the one in the title picture. VBA also allows to use interfaces which offers a lot of possibilities. This article describes how to use interfaces in VBA and how to work around their bugs.
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…
With the power of JIRA, there's an unlimited number of ways you can customize it, use it and benefit from it. With that in mind, there's bound to be things that I wasn't able to cover in this course. With this summary we'll look at some places to go…

721 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