Solved

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

Posted on 2008-10-11
5
2,742 Views
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.
0
Comment
Question by:stevehibbert
  • 3
  • 2
5 Comments
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 500 total points
ID: 22695658
>>>> 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
 

Author Comment

by:stevehibbert
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.
0
 

Author Comment

by:stevehibbert
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.
0
 

Author Closing Comment

by:stevehibbert
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.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
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.

0

Featured Post

Enabling OSINT in Activity Based Intelligence

Activity based intelligence (ABI) requires access to all available sources of data. Recorded Future allows analysts to observe structured data on the open, deep, and dark web.

Join & Write a Comment

Programmer's Notepad is, one of the best free text editing tools available, simply because the developers appear to have second-guessed every weird problem or issue a programmer is likely to run into. One of these problems is selecting and deleti…
How to install Selenium IDE and loops for quick automated testing. Get Selenium IDE from http://seleniumhq.org (http://seleniumhq.org) Go to that link and select download selenium in the right hand columnThat will then direct you to their downlo…
This tutorial covers a step-by-step guide to install VisualVM launcher in eclipse.
The viewer will learn how to synchronize PHP projects with a remote server in NetBeans IDE 8.0 for Windows.

746 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

12 Experts available now in Live!

Get 1:1 Help Now