Looking for C++ Simple N-ary Tree Examples - Very Stuck!

Posted on 2008-10-11
Medium Priority
Last Modified: 2013-12-14
Hi Experts,

I'm trying to find an example of an n-ary tree for void data types.  I understand the basics but I am struggling with implementation, so an example of a simple n-ary tree would be invaluable (with view to writing an XML data retrieval class).
I understand that a node in the tree will need a pointer to a parent, an array of pointers to child nodes, and a void pointer to data on the node.
I don't quite understand how I add a node, because how do I know where I am in the tree?  I've written a similar queue/stack/list class that adds nodes to a given position (front, end, midpoint) of the doubly linked list, but I'm conceptually stuck with how I refer to a particular node on the tree.
If anyone could point me to some example code it would really help.  As I will have to maintain and expand this code, I have to understand it fully, which is why I am not using an off-the-shelf class.  (Please note that I am not a student trying to skip homework, this is work for me...).
I've scoured the internet but each example seems to say "...and you can take it from here" and it's the implementation that I am having difficulty with.
Help would be very greatly appreciated.  [The List/Queue/Stack class is available to anyone who wants it, it's fast and has been used in real apps, and does no copying so it's quite fast]
For reference, this is C++ in Visual C++ 6, on Windows Vista.
Thanks in advance.
Question by:stevehibbert
  • 3
  • 2
LVL 39

Accepted Solution

itsmeandnobodyelse earned 2000 total points
ID: 22695658
>>>> I understand that a node in the tree will need a pointer to a parent,
>>>> an array of pointers to child nodes,
No, a node would point to first (and perhaps last) child-node. Then, each node would have a pointer to next (and perhaps previous) node of same level (sibling), e. g. like I did in the code snippet above
>>>>because how do I know where I am in the tree?  
You have two insert functions. One for private use only. It passes the parent node pointer as first argument or is a member function of Node class. In either way it knows where to add a new child node. The public insert function which is a member of the tree class, has no node-pointers as arguments, but some kind of key. Then, the insert function first traverses its internal tree (from root node) to *find* the node where to add the new entry and then calls the internal insert function using that node.
>>>> Please note that I am not a student trying to skip homework, this is work for me...
Yes, I looked at your profile and it doesn't look like that of a student. But you deleted all previous C++ questions, so it seems you have less to no experience writing C++ containers. Then, a full working tree class isn't that you need. You should start with some basic code yourself , post it here, and let us help to improve it.

// macros for easier template type declaration
#define TreeItemPtr        TreeItem*
#define TreeNodePtr        TreeNode<TNodeData, TLeafData>*
#define TreeLeafPtr        TreeLeaf<TNodeData, TLeafData>*
#define TreePtr            Tree<TNodeData, TLeafData>*
#define TreeRef            Tree<TNodeData, TLeafData>&
#define TreeIteratorPtr    TreeIterator<TNodeData, TLeafData>*
#define TreeIteratorRef    TreeIterator<TNodeData, TLeafData>&
// @doc   Tree
// @class Base class for elements of a tree. A TreeItem holds pointers to the parent, previous and next tree element 
class TreeItem
// @dataprivate
    // Attributes
    string               m_key;         // @cmember item key (should be unique for all siblings)
    TreeItemPtr          m_pParent;     // @cmember pointer to parent node item or NULL if root
    TreeItemPtr          m_pPrev;       // @cmember pointer to previous item of the same level or NULL if first
    TreeItemPtr          m_pNext;       // @cmember pointer to next item of the same level or NULL if last
// @doc   TreeNode
// @class  Derived class of class TreeItem to hold nodes. A node is a tree item  
//   <nl>  that may be parent of a list of leafs and/or parent of a list of
//         child nodes, Nodes and leafs may associate different data types
template <class TNodeData, class TLeafData>
class TreeNode  : public TreeItem
// @dataprivate
    // Attributes
    TNodeData*           m_pData;        // @cmember pointer to data
    TreeNodePtr          m_pFirstKid;    // @cmember pointer to first child node or NULL if last level
    TreeNodePtr          m_pLastKid;     // @cmember pointer to last child node or NULL if last level
    TreeLeafPtr          m_pFirstLeaf;   // @cmember pointer to first leaf or NULL if no leafs
    TreeLeafPtr          m_pLastLeaf;    // @cmember pointer to last leaf or NULL if no leafs
// @doc   TreeLeaf
// @class  Derived class of class TreeItem to hold leafs. A leaf is a child   
//   <nl>  tree item that has no child items
template <class TNodeData, class TLeafData>
class TreeLeaf  : public TreeItem
// @dataprivate
    // Attributes
    TLeafData*                  m_pData;       // @cmember pointer to data

Open in new window


Author Comment

ID: 22697302
Yep, I have no experience of writing C++ containers, that is correct.  I am teaching myself from books and internet code, using Petzold and Richter for Windows stuff, and Horton's C++ book as the start for C++.  Essentially, I am doing C, with C++ bits and bobs, avoiding MFC entirely, out of choice.
This morning I figured out that I would need a pointer that is used to navigate the tree.  I am going to have to update that pointer as I move around the tree.  
I was going to use a dynamic array of child pointers because this gets me closer to another project I want to start, a neural net model.  Similar to a n-ary tree, each neural node points to an upstream neuron (parent) that it is sending it a signal, and an uknown number of downstream neurons (children) that it sends signals to.
The current  tree class will be used to take a flat XML file and impose meaning on it via the structure of the tree, so that I can extract strings of data from certain categories.
I'm specifically not using template containers, I'm intentially using a void pointer instead.  It means I can store different data types in the tree if I need to.  I've got used to this method in writing the stack/queue/list class, and it works well and does not copy the data into and out of the class, it only points to the data in the place it was originally 'new'ed.  I can also interleave data types or structures if needed - dangerous maybe, I grant you, I have not tried this yet.

Thanks very much for taking the time to reply, I appreciate the effort you have made.  As I am admittedly a beginner it may take me a few days to digest and understand this, so I will get back to you shortly.

[The previous questions were deleted because I figured out the solutions before an answer was posted - sometimes if you chew on a problem long enough you can crack it yourself.]

Much obliged.

Author Comment

ID: 22719065
Damn, I meant to accept "itsmeandnobodyelse"s solution, not my own.  There seems to be no cancel option other than raising an objection.

Author Closing Comment

ID: 31505287
After struggling to find my own way to do this, I ended up doing it this way.  But at least I now understand what I am doing and can maintain the code, so very grateful for the assistance.
LVL 39

Expert Comment

ID: 22719266
>>>> I meant to accept "itsmeandnobodyelse"s solution
No problem, it worked. Thanks for the points.

If you need some code of the above example, don't hesitate to ask.

I used the above tree class to map a file system where the TreeNodes are directories and the TreeLeafs were files. For a 'normal' tree class you could make one class out of TreeItem and TreeNode.


Featured Post

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

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.

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.

Join & Write a Comment

In our object-oriented world the class is a minimal unit, a brick for constructing our applications. It is an abstraction and we know well how to use it. In well-designed software we are not usually interested in knowing how objects look in memory. …
Jaspersoft Studio is a plugin for Eclipse that lets you create reports from a datasource.  In this article, we'll go over creating a report from a default template and setting up a datasource that connects to your database.
THe viewer will learn how to use NetBeans IDE 8.0 for Windows to perform CRUD operations on a MySql database.
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

621 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