• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 3028
  • Last Modified:

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

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.
0
stevehibbert
Asked:
stevehibbert
  • 3
  • 2
1 Solution
 
itsmeandnobodyelseCommented:
>>>> I understand that a node in the tree will need a pointer to a parent,
ok
>>>> 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
private:
    // 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
private:
    // 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
private:
    // Attributes
    TLeafData*                  m_pData;       // @cmember pointer to data
...
};

Open in new window

0
 
stevehibbertAuthor Commented:
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.
0
 
stevehibbertAuthor Commented:
Damn, I meant to accept "itsmeandnobodyelse"s solution, not my own.  There seems to be no cancel option other than raising an objection.
0
 
stevehibbertAuthor Commented:
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.
0
 
itsmeandnobodyelseCommented:
>>>> 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.

0

Featured Post

Concerto Cloud for Software Providers & ISVs

Can Concerto Cloud Services help you focus on evolving your application offerings, while delivering the best cloud experience to your customers? From DevOps to revenue models and customer support, the answer is yes!

Learn how Concerto can help you.

  • 3
  • 2
Tackle projects and never again get stuck behind a technical roadblock.
Join Now