Solved

C++ General Tree

Posted on 2009-07-03
25
458 Views
Last Modified: 2013-12-14
Hey C++ guru's...

I'm pretty new to the C++ world and would really appreciate some help... ...

I'm trying to build a general tree (a tree with one root and N children), I've written the code and compiled it quote/un-quote successfully... ...I say that because I am faced with a runtime error that basically stops my efforts dead in its tracks...
/////// ********* GeneralTree.h *********///////

///////-------------------------------------///////

#ifndef GENERALTREE_h

#define GENERALTREE_h
 

#include <iostream>
 

using namespace std;
 

class GeneralTree{

	public:

		struct GenTreeNode{

			int int_transactionID, int_totalNumChildren;

			GenTreeNode *ptr_nextChild;

		};

		

		//initialize root

		GenTreeNode *root;
 

		GeneralTree(){

			int int_totalNumChildren = 0;

		}
 

		~GeneralTree(){

			clear();

		}
 

		void clear(){

			//point to the node to be deleted

			GenTreeNode *tmp;

			//used to visit each node in the tree. 

                        //We start with the first actual node off of "root"

			GenTreeNode *traverse = root->ptr_nextChild;

			

			//while the tree is not empty

			while(traverse != NULL){

				//store the current node

				tmp = traverse;

				//visit the next node

				traverse = traverse->ptr_nextChild;

				//free the memory taken up by the current node

				delete tmp;

			}

		}
 

		void addChildren(int *tranID, int cNo){

			int int_totalNumChildren = cNo;

			GenTreeNode *genTree = new GenTreeNode[int_totalNumChildren];
 

			for(int i=0; i<int_totalNumChildren; i++){

				genTree->int_transactionID = tranID[i];

			}

		}
 

		void PrintTree(GenTreeNode *tree) {

			/* .: Print all the items in the tree to which root points...the item in the root is printed first, followed by its children :: as long as the root is not empty :. */

			if (tree != NULL){

				cout << tree->int_transactionID << " ::- " << tree->int_totalNumChildren << endl;

				// Print children

				PrintTree(tree->ptr_nextChild);

			}

		}
 

		void deleteChild(GenTreeNode *ChildPtr){

		}

};
 

#endif
 

/////// ********* Main.cpp *********///////

///////-------------------------------///////

#include <iostream>

#include <fstream>

#include "GeneralTree.h"
 

using namespace std;
 

int main(){

	GeneralTree *gTree = new GeneralTree;

	int tID = 100; 

	int numOfChildren = 10;
 

	cfisTree->addChildren(&tID, numOfChildren);

	cfisTree->PrintTree(gTree->root);
 

	return 0;

}

Open in new window

0
Comment
Question by:didijc
  • 8
  • 8
  • 7
  • +1
25 Comments
 
LVL 44

Expert Comment

by:AndyAinscow
ID: 24772983
>>I say that because I am faced with a runtime error

Telling us what the error is will help
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24773037
You never allocate memory for the root ... ie. the root pointer points nowhere. You should probably do that when creating the GeneralTree object.
0
 

Author Comment

by:didijc
ID: 24773836
Andy -- my apologies...I attached a screen shot of the runtime error...

Also, lines 83 & 84 should read:
gTree->addChildren(&tID, numOfChildren);
gTree->PrintTree(gTree->root);

Infinity08, I'm not sure I follow what you're saying...I was under the impression that you had to allocate space for the root...that's how the tree is initialized...no?
error.jpg
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 100 total points
ID: 24773856
>> I was under the impression that you had to allocate space for the root...that's how the tree is initialized...no?

yes, but you never do that. The only places where 'root' is used are :

>>                 GenTreeNode *root;

Declaration of the pointer.

>>                         GenTreeNode *traverse = root->ptr_nextChild;

Dereferences the pointer.

>>         cfisTree->PrintTree(gTree->root);

Might also dereference the pointer (inside the PrintTree method);


So, there's never any memory allocation, like in :

        root = new GenTreeNode();

(don't forget to initialize the struct members after allocating memory for them)
0
 

Author Comment

by:didijc
ID: 24773926
Infinity

I did what you suggested -- I removed the "new GenTreeNode();" --- but now I get ::- Run-Time Check Failure #3 - The variable 'gTree' is being used without being initialized.

check out the screen shot...
error2.jpg
0
 
LVL 53

Assisted Solution

by:Infinity08
Infinity08 earned 100 total points
ID: 24773955
>> I removed the "new GenTreeNode();"

I never said to remove it ...  You need to ADD it. You need to allocate memory for 'root' before you use it.

I suggest you read up on dynamic memory in C++, in this tutorial for example :

        http://cplusplus.com/doc/tutorial/dynamic/
0
 

Author Comment

by:didijc
ID: 24774046
Ok wait...

So basically what you're saying is that I should have something like this

class GeneralTree{
        public:
                struct GenTreeNode{
                        int int_transactionID, int_totalNumChildren;
                        GenTreeNode *ptr_nextChild;
                };
               
                //initialize root
                GenTreeNode *root = new GenTreeNode();

??
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24775299
>> So basically what you're saying is that I should have something like this

That won't compile ... But you have the class constructor to perform initializations when the object is created.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24780170
>>>>> That won't compile ... But you have the class constructor to perform initializations when the object is created.

Infinity means you should move that statement into the constructor like

    GeneralTree()
    {
         int_totalNumChildren = 0;
         root = new GenTreeNode();
    }

Generally omit to create a new type when refering to members in member functions. You would create a local variable with same name as the member and the member was *NOT* initialized.

   
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24780198
>>>> int_totalNumChildren = 0;
I saw that it is a member of the GeneralTreeNode, hence you should provide a constructor of that struct like

class GeneralTree{
        public:
                struct GenTreeNode
                {
                        int int_transactionID;
                        int int_totalNumChildren;
                        GenTreeNode *ptr_nextChild;
                        GenTreeNode()
                            : int_transactionID(0)
                            , int_totalNumChildren(0)
                            , ptr_nextChild(NULL)
                         {}
                };
                ...


The above is calloed an initializer list, ad it is the recommended way how to initialize *all* data members which have no own constructor.

applying the same to the constructor of GeneralTree we have

The recommended way to init data members of a class/struct in C++ is to using the initializer list:

   GeneralTree()
     :  root(new GenTreeNode())
    { }

And if using new don't forget the destructor


   virtual ~GeneralTree() { delete root; }

if root is always initialized it doesn't matter if it is NULL when deleting it.

Making it virtual allows to derive from GeneralTree and delete by baseclass pointer.

0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 400 total points
ID: 24780258
>>>> ~GeneralTree(){  clear(); }
You already had a destructor. It was not bad but it could be improved by moving the deletion of children into the destructor of the node. Then you simply delete the root and it would recursively delete all children.

The GenNodeTree has only one child-pointer. With that your *tree* actually is a simply linked list.

A treenode at least needs two pointers one to the right for the next sibling and one pointer down to the first child.

                struct GenTreeNode
                {
                        int int_transactionID;
                        int int_totalNumChildren;
                        GenTreeNode *ptr_nextSibling;
                        GenTreeNode *ptr_nextChild;
                        GenTreeNode()
                            : int_transactionID(0)
                            , int_totalNumChildren(0)
                            , ptr_nextSibling(NULL)
                            , ptr_nextChild(NULL)
                         {}
                         ~GenTreeNode()
                         {
                              delete ptr_nextSibling;   // first delete brothers and sisters
                              delete ptr_nextChild;     // then delete down
                        }
                };
 
0
 
LVL 39

Assisted Solution

by:itsmeandnobodyelse
itsmeandnobodyelse earned 400 total points
ID: 24780267
>>>> int int_totalNumChildren;
Don't think you need that. You easily could make a mamber function instead like that:

                struct GenTreeNode
                {
                     int getNumChildren()
                     {
                          GenTreeNode * ptr = ptr_nextChild;
                          int num = 0;
                          while (ptr != NULL)
                          {
                                num++;
                                ptr = ptr->ptr_nextSibling;
                          }
                          return num;
                     }
                };
   

0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 44

Expert Comment

by:AndyAinscow
ID: 24780419
>>A treenode at least needs two pointers one to the right for the next sibling and one pointer down to the first child.

Aren't the siblings the children of the parent node - IMHO no requirement for information about a sibling in a node, that is just duplicating information.
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24780539
Siblings in the context of a tree, are nodes that have the same parent. Sometimes it is more widely understood to be nodes at the same level in the tree.
0
 

Author Comment

by:didijc
ID: 24782214
Also, why doesn't my PrintTree function not out my tree correctly... ...in other words, in my main.cpp I enter this...

[code]
/////// ********* Main.cpp *********///////
///////-------------------------------///////
#include <iostream>
#include <fstream>
#include "GeneralTree.h"
 
using namespace std;
 
int main(){
        GeneralTree *gTree = new GeneralTree;
        int tID = 100;
        int numOfChildren = 10;
 
        cfisTree->addChildren(&tID, numOfChildren);
        cfisTree->PrintTree(gTree->root);
 
        return 0;
}
[/code]

In return...I get...

0 ::- -842150451

0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24783004
>> Also, why doesn't my PrintTree function not out my tree correctly...

Can you show the complete code you're using now ? After the modifications you made for fixing the firts problem.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24783303
>>>> IMHO no requirement for information about a sibling in a node, that is just duplicating information.

If there is only one pointer for many children the pointer needs to point to an array of children rather than to the first child as it was usual. I saw that in the addChildren indeed an array of children nodes was created . But such a design has some disadvantages. First, you always need to know the count of children before you can open a new child level. Second, it is impossible (with the current design) to add a new child node after children were once created. Third, you need to pass all data for the children with the addChildren to fully create them. But after that, you would need to have a loop traversing all children to add further children to these nodes. Building up a tree that way is very difficult as you hardly can do it from a sequential list (file) without more information regarding the parent - child relation.  

Look at the (current) implementation of addChildren. Here the dilemma is quite obvious (despite of some other logical flaws).

>>>>            void addChildren(int *tranID, int cNo){
>>>>                  int int_totalNumChildren = cNo;
>>>>                  GenTreeNode *genTree = new GenTreeNode[int_totalNumChildren];
>>>>
>>>>                  for(int i=0; i<int_totalNumChildren; i++){
>>>>                          genTree->int_transactionID = tranID[i];
>>>>                  }
>>>>            }


(1) it is a tree member function though it would needed to be a node function.
(2) it passes an array of ids for each child.
(3) the int_totalNumChildren will be locally defined here though the member
     'int_totalNumChildren' of the current node should be set.
(4) the genTree is a local pointer as well though it should be assigned to the
     ptr_nextChild of the current node.
(5) only the int_transactionID of the first node will get an assignment but not
     the later child nodes.

Below is an implementation of addChildren which is correct within the current design. But I would recommend to change that to a design where a tree node points down and right which is much more flexible.

Note, if you want to let the addChildren a member function of GeneralTree, you would need to specify the parent node where the children were to be added somehow. If the transactionID is a unique key you could take that. If not, you would need to have a member

        GenTreeNode * current;

in the GeneralTree, where the current node (e. g. found by iteration or by searching for transaction ID or the last node accessed by a previous operation) was stored.


 

// Must be a member of GenTreeNode

void GenTreeNode::addChildren(int tranIDArr[], int cNo)

{

   // set member of parent node

   int_totalNumChildren = cNo;

   // create an array of nodes (note, it is nodes and not node pointers)

   ptr_nextChild = new GenTreeNode[int_totalNumChildren];

   for(int i=0; i<int_totalNumChildren; i++){

        ptr_nextChild[i].int_transactionID = tranID[i];

   }

}

Open in new window

0
 

Author Comment

by:didijc
ID: 24786829
Thanks everyone for all of your help... ...I've made several corrections based on all of your input...however, my output is not returning the results I expect...

What I mean by that is this... ...in my MAIN.CPP I assign values to tID[] and numOfChildren...however, when I print my tree I only get the value of 0 (zero) back for both...take a look at the attached jpeg...

>>>>"But I would recommend to change that to a design where a tree node points down and right which is much more flexible."

itsmeandnobodyelse, that was my initial intention however, I'm still a bit new with C++ and I got lost, if you have suggestions I will definitely like to hear them, like I said that is the direction that I would like to implement...
/////// ********* GeneralTree.h *********///////

///////----------------------------------///////

#ifndef GENERALTREE_h

#define GENERALTREE_h

 

#include <iostream>

 

using namespace std;

 

class GeneralTree{

	public:

		struct GenTreeNode{

			int int_transactionID, int_totalNumChildren;

			GenTreeNode *ptr_nextChild;

			GenTreeNode *ptr_nextSibling;

			

			GenTreeNode()

				: int_transactionID(0), 

					int_totalNumChildren(0), 

					ptr_nextChild(NULL),

					ptr_nextSibling(NULL){}

		};

		

		//initialize root

		GenTreeNode *root;
 

		GeneralTree()

			: root(new GenTreeNode()){}
 

		virtual ~GeneralTree(){

			delete root;

		}
 

		void addChildren(int tranIDArr[], int childrenNum){

			GenTreeNode *genTree = new GenTreeNode[childrenNum];

			

			for(int i=0; i<childrenNum; i++){

				genTree->ptr_nextChild[i].int_transactionID = tranIDArr[i];

			}

		}
 

		void PrintTree(GenTreeNode *tree) {

			/* .: Print all the items in the tree to which root points...the item in the root is printed first, followed by its children 

				:: as long as the root is not empty :. */

			if (tree != NULL){

				cout << tree->int_transactionID << " :: " << tree->int_totalNumChildren << endl;

				// Print children

				PrintTree(tree->ptr_nextChild);

			}

		}
 

		void deleteChild(GenTreeNode *ChildPtr){
 

		}

};
 

#endif
 

/////// ********* Main.cpp *********///////

///////-----------------------------///////

// .: canned includes :.

#include <iostream>

#include <fstream>
 

// .: custom includes :.

#include "GeneralTree.h"
 

using namespace std;
 

int main(){

	GeneralTree *cfisTree = new GeneralTree();

	int tID[] = {100}; 

	int numOfChildren = 0;
 

	cfisTree->addChildren(tID, numOfChildren);

	cfisTree->PrintTree(cfisTree->root);

	

	return 0;

}

Open in new window

output.jpg
0
 
LVL 53

Expert Comment

by:Infinity08
ID: 24786948
>>         int numOfChildren = 0;
>>  
>>         cfisTree->addChildren(tID, numOfChildren);

You add 0 children to the tree ... (since numOfChildren == 0)


>> however, when I print my tree I only get the value of 0 (zero) back for both

That's because you initialized the root node to have the value 0 for int_transactionID and int_totalNumChildren, so the code just prints the values you assigned.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 400 total points
ID: 24789629
>>>> if you have suggestions I will definitely like to hear them

Ok, I'll give you the code though I need to let some implementations open in case it was homework. Note, you can ask me or other experts for any of the ... statements.  It is only that EE rules forbid to give full code to possible assignments.


/////// ********* GeneralTree.h *********///////

///////-------------------------------------///////

#ifndef GENERALTREE_H

#define GENERALTREE_H
 

#include <iostream>

#include <iomanip>   // setw, right
 

class GeneralTree{

public:

    struct GenTreeNode

    {

        int data;

        GenTreeNode * firstChild;

        GenTreeNode * nextSibling;

        GenTreeNode() : data(0), firstChild(NULL), nextSibling(NULL) {}

        ~GenTreeNode() { delete firstChild; delete nextSibling; }

        GenTreeNode * find(int tranId) 

        {

            // check if data equals to the tranId searched for

            // if yes return this node

            ...

            GenTreeNode * node = NULL;

            if (nextSibling != NULL) 

            {

               // get node from recursive calling find 

               node = ... ; 

               // if the nde was found we are thru

               if (node != NULL) return node;

            }

            if (firstChild != NULL) 

               // get node by calling find for the first child

               node = ... ;

            return node;

        }

        // print node and all susbsequent nodes

        // depth is the level 

        void print(int depth)

        {

            // make 2 spaces indent depending on depth

            for (int i = 0; i < depth; ++i)

                std::cout << "  ";

            // print value of current node 

            std::cout << std::right << std::setw(10) << data << std::endl;

            if (firstChild != NULL) 

            {

               // call print for first child with depth + 1

               ...;

            }

            if (nextSibling != NULL) 

            {

               // call print for next sibling with same depth

               ... ;

            }

        }

    };

    

    // tree root

    GenTreeNode * root;

    

    GeneralTree()

        : root(NULL)

    {}

    

    ~GeneralTree(){ delete root; }  // recursive deletion

    

    // add a new node by passing tranId for parent and child 

    // tranId is supposed to be unique for all nodes

    bool add(int tranParentID, int tranChildID) 

    {

       // locate the parent

        GenTreeNode * parent = findNode(tranParentID);

        if (parent == NULL) 

        {

            if (root == NULL)

            {

                // if we have an empty tree we create a root node 

                root = ...;

                // and set the data element of the root node to the tranChildId

                ...;

                return true;

            }

            return false;  // root is not NULL bit tranParentId was not found

        }

        // initialize the node with first child of parent

        GenTreeNode * lastChild = parent->firstChild;

        // if NULL the parent node has no children til now

        if (lastChild == NULL)

        {

           // generate a new child node and set it as first child of parent

           ...;

           // set data of the new child node

           ...;

           return true;

        }

        // in case the first child is not NULL we need to iterate 

        // thru all siblings until we reach the last sibling

        while (lastChild->nextSibling != NULL)

            lastChild = lastChild->nextSibling;

        // then we generate a new node and set it 

        // as next sibling of the last child node 

        ...;

        // set tranChildId as data of the new sibling node

        ...;

        return true;

    }

    // print tree recursively

    void printTree() 

    {

        if (root == NULL) return;

        root->print(0);
 

    }
 

protected:
 

    // findNode is an internal function only (protected)

    // we call the above find function starting with root

    GenTreeNode * findNode(int tranId)

    {

        if (root == NULL) return NULL;

        GenTreeNode * node = root->find(tranId);

        return node;

    }

    

};

 

#endif

Open in new window

0
 

Author Comment

by:didijc
ID: 24794694
Wow - okay... ...so I was going in a totally wrong direction...

okay, well I will incorporate your code and add a little bit of me into it :) -- and re-post it...

Thanks itsmeandnobodyelse and everyone else...all of you are my heroes!!! :D
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24795168
>>>> so I was going in a totally wrong direction...
No, it is only a different approach which has some advantages. E. g. that you can add and remove child nodes. Or that you can easily decide how to expand a  tree at the current node: to the right by adding a new child to the parent or down by adding an own child.

But your first approach was valid as well, beside of the bugs ;-)

By adding an array of children to each node, you can construct the same tree as in my design though it is less flexible and perhaps much more difficult to implement.
0
 

Author Comment

by:didijc
ID: 24817252
Why is it that the "root" of my tree is declared OUTSIDE of "struct GenTreeNode" -- I'm trying to fully dissect and understand every single line of the code -- but that's one question I simply cannot get a clear understanding on...

Also, itsmeandnobodyelse...lines 20-22 of your code

[code]
// check if data equals to the tranId searched for
// if yes return this node
...
[/code]

Is this what you mean:
if(date == tranId)
      return node;

But how does that work, when you no node was established...where does the node that is being returned come from?
0
 

Author Comment

by:didijc
ID: 24817794
This is how I implemented the find function...
GenTreeNode *find(int tranId){

	GenTreeNode *node = NULL;

			

	if (nextSibling != NULL){

		// get node by calling find for the sibling

		node = findGenTreeNode(node->nextSibling->data); 

		// if the node was found we are thru

		if (node != NULL){ 

			return node;

		}

	}
 

	if (firstChild != NULL){

		// get node by calling find for the child

		node = findGenTreeNode(node->firstChild->data); 

		// if the node was found we are thru

		if (node != NULL){ 

			return node;

		}

	}

}

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24821055
>>>> Why is it that the "root" of my tree is declared OUTSIDE of "struct GenTreeNode" --

The root is a member of the tree and not of the node. It tells where the tree begins. The struct GenTreeNode could have been defined above the class GeneralTree as well. It is only a helper. By putting the class (struct) definition into the General Tree you make it a (private) subclass of GeneralTree which only may be used by member functions of GeneralTree but not by functions *using* the GeneralTree.  

>>>> // check if data equals to the tranId searched for
>>>> // if yes return this node

I thought on code like

      if (tranId == data)
           return this;

When calling functions recursively the recursion somehow must have an end. Here we are in a find function which should find the node (within the whole tree) which data value matches to the tranId passed as search value. The above statement simply is the case where we found the tranId in the current node (this).

>>>> This is how I implemented the find function...
It is ok beside of the check whether the current node (this) is the one we searched for.

If you don't add that check none of the recursive calls ever could return a node different to NULL.



0

Featured Post

Maximize Your Threat Intelligence Reporting

Reporting is one of the most important and least talked about aspects of a world-class threat intelligence program. Here’s how to do it right.

Join & Write a Comment

Introduction This article is the first in a series of articles about the C/C++ Visual Studio Express debugger.  It provides a quick start guide in using the debugger. Part 2 focuses on additional topics in breakpoints.  Lastly, Part 3 focuses on th…
Introduction This article is a continuation of the C/C++ Visual Studio Express debugger series. Part 1 provided a quick start guide in using the debugger. Part 2 focused on additional topics in breakpoints. As your assignments become a little more …
The viewer will learn how to use and create keystrokes in Netbeans IDE 8.0 for Windows.
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…

760 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

20 Experts available now in Live!

Get 1:1 Help Now