Solved

Implementing General Tree

Posted on 2009-07-15
17
4,098 Views
Last Modified: 2012-05-07
hello experts,
please, i am tryting to implement General Tree ( a tree in which each node may have any number of child nodes).
// node structure follwos. each node has 3 parts : Value or info, No. of children, an array of pointers (dynamic) to point to n child nodes

its not working fine.
it does give output as expected.
please check where i am wrong.
#include<iostream.h>

#include<conio.h>

#include<alloc.h>
 

// node structure follwos. each node has 3 parts : Value or info, No. of children, an array of pointers (dynamic) to point to n child nodes

struct GTreeNode

{

     int val;

     int NChild;

     GTreeNode **Child;

}**Root=NULL;
 

void CreateGeneralTree(GTreeNode**,int);

void ShowGeneralTree(GTreeNode*);         //will show  details of all nodes, one by one, not working fine. 

void ShowGTNode(GTreeNode *R);            //will dhow details of one node. ok.
 

void main()

{

	int i, val, n;

	GTreeNode *NewNode ;

	clrscr();

	//Create Root Node.

	cout<<"\nEnter Root Val " ;

	cin>>val ;

	cout<<"Enter No. of Children "  ;

	cin>>n;
 

	NewNode=(GTreeNode *)malloc(sizeof(GTreeNode)*n);

	NewNode->val=val;

	NewNode->NChild=n;   //new node has n children

	for(i=0;i<n;i++)

		NewNode->Child[i]=(GTreeNode*)NULL;  //initiall ymake them all  Null

	Root=&NewNode; // root points to newnode. root is root of tree.

	CreateGeneralTree(Root,n); //now get details of n childern of root & their children

	//ShowGeneralTree(NewNode);

getch();

}
 

void CreateGeneralTree(GTreeNode **r, int n)

{

	int i,k, m;

	char ch ;
 

	//allocate memory for n children.

	(*r)->Child=(GTreeNode**)malloc(n*sizeof(GTreeNode));

	//Enter values of Child Nodes.

	cout<<"\nNode Created at : "<< r<<"\n";

	for(i=0;i<n;i++)

	{

		cout<<"\tEnter value for Child "<< i << " : ";

		cin>>(*r)->Child[i]->val;

		(*r)->Child[i]->NChild=0;

		(*r)->Child[i]->Child=NULL;

	}

	ShowGTNode(**r);  //chek is it ok.

	cout<<"\nDo You Wish to Enter Info of Child Nodes : ";

	ch=getche();

	if(ch=='y' || ch=='Y')

	{

		for(k=0;k<n;k++)

		{

			cout<<"\n "<<k<<" Enter No. of Children of " << (*r)->Child[k]->val<<"  : ";

			cin>>m;

			(*r)->Child[k]->NChild=m ;

			CreateGeneralTree(&((*r)->Child[k]),m);   //recurisive

		}

	}

}
 

void ShowGTNode(GTreeNode *R)

{

	int i, n=R->NChild;

	cout<<"\nNo. Of Children : "<<n ;

	for(i=0;i<n;i++)

		cout<<R->Child[i];

}
 
 
 

void ShowGeneralTree(GTreeNode *r)

{

     int i,n;

     n=r->NChild;

     cout<<"\nAddress : " <<r<<"\tValue : "<<r->val<<"\tChildren : "<<n<<"\t";

     for(i=0;i<n;i++)

	 cout<<"  "<<r->Child[i]->val;

     getch();

     for(i=0;i<n;i++)

	ShowGeneralTree(r->Child[i]);

}

Open in new window

0
Comment
Question by:soodsandeep
  • 8
  • 4
  • 4
  • +1
17 Comments
 
LVL 40

Expert Comment

by:evilrix
ID: 24866884
>>its not working fine.
Why?

>>it does give output as expected.
What do you expect and what do you get?
0
 
LVL 12

Expert Comment

by:Let_Me_Be
ID: 24866958
One thing I consider odd is that you are using pointer to pointer (GTreeNode **Child, **Root). Why? The problem might be here, because you seem to be intermixing one pointer operations with pointer to pointer operations.
0
 

Author Comment

by:soodsandeep
ID: 24867623
evilrix and Let_Me_Be, Thanks for your replies.
i have modifed code, a little bit. but its stll not wokring.
problem is tree is not created as expected. Pleae run it and check output.
Also, i have made two comments A and B. please check them, i doubt problem is due to A not matching with B.
in A  i am taking pointers to pointers and in B i am using it as array.
Plese check.
Thanks.
New code is :
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
struct GTreeNode
{
     int val;
     int NChild;
     GTreeNode **Child;
}**Root=NULL;

void CreateGeneralTree(GTreeNode**,int);
void ShowGTNode(GTreeNode *R);

void main()
{
      int i, val, n;
      GTreeNode *NewNode ;
      clrscr();
      //Create Root Node.
      cout<<"\nEnter Root Val " ;
      cin>>val ;
      cout<<"Enter No. of Children "  ;
      cin>>n;

      NewNode=(GTreeNode *)malloc(sizeof(GTreeNode)*n);
      NewNode->val=val;
      NewNode->NChild=n;
      for(i=0;i<n;i++)
            NewNode->Child[i]=(GTreeNode*)NULL;    //set each child to NULL.
      Root=&NewNode;
      CreateGeneralTree(Root,n); //now get deatails of other children.
      ShowGTNode(*Root);  //show details of tree node by node.
getch();
}

void CreateGeneralTree(GTreeNode **r, int n)  
{
      int i,k, m;
      char ch ;
      //allocate memory for n children.
      (*r)->Child=(GTreeNode**)malloc(n*sizeof(GTreeNode));     // IS THIS OK ?   ----  (A)
      //Enter values of Child Nodes.
      cout<<"\nNode Created at : "<< r<<"\n";
      for(i=0;i<n;i++)
      {
            cout<<"\tEnter value for Child "<< i << " : ";
            cin>>(*r)->Child[i]->val;
            (*r)->Child[i]->NChild=0;
            (*r)->Child[i]->Child=NULL;
      }
      cout<<"\nDo You Wish to Enter Info of Child Nodes : ";
      ch=getche();
      if(ch=='y' || ch=='Y')
      {
            for(k=0;k<n;k++)
            {
                  cout<<"\n "<<k<<" Enter No. of Children of " << (*r)->Child[k]->val<<"  : ";
                  cin>>m;
                  (*r)->Child[k]->NChild=m ;      //IS THIS OK and suits with A.  -- (B)
                  CreateGeneralTree(&((*r)->Child[k]),m);
            }
      }
}

void ShowGTNode(GTreeNode *R)
{
      int i,n=R->NChild;
      cout<<"\nInfo about "<<R->val;
      //cout<<"\nInfo about "<<(*R).val;
      cout<<" No. Of Children : "<<n ;
      for(i=0;i<n;i++)
            cout<<"\n"<<i<<"  "<<R->Child[i]<<"  "<<R->Child[i]->val ;
       for(i=0;i<n;i++)
            if(R->Child[i]->NChild !=0)
                  ShowGTNode(R->Child[i]) ;
}
0
 

Author Comment

by:soodsandeep
ID: 24867627
i also request infinity08, to please check this.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24867677
>>>> One thing I consider odd is that you are using pointer to pointer
Indeed, pointer to pointer was used for 2d arrays or if you want to have a output argument where a new pointer value needs to be returned to the caller. But even in the latter case you wouldn't create pointer to pointer but pass the address of a normal pointer.

One more thing odd is that you were using old (deprecated) iostream.h. Since C++ standard is from 1998 there is hardly a reason to not using iostream header from C++ standard.

#include <iostream>   // not .h
using namespace std;

Using iostream means in any case (both for old and new) that your prog isn't C but C++. Then, it is highly recommended to using new and delete rather than malloc and free. And it is highly recommended to not mixing C I/O (e. g. the getch) with C++ streaming.


0
 
LVL 12

Expert Comment

by:Let_Me_Be
ID: 24868345
A does not fit B.
(*r)->Child=(GTreeNode**)malloc(n*sizeof(GTreeNode*));

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

  (*r)->Child[i] = (GTreeNode*)malloc(sizeof(GTreeNode));

//....

(*r)->Child[k]->NChild=m ;

Open in new window

0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24868693
The first code you posted compiles after changing

   ShowGTNode(**r);

to

   ShowGTNode(*r);

but it crashes soonly because you never allocate space for the Child array elements as it is required if using pointer to pointer.

IMO, the pointer to pointer approach is wrong, bad design and much too complex for a beginner (as it seems you are).

I changed your code and make it run using simple pointers. It was a little work but it surely is the way to go.

As your code probably is an assignment I can't post you my full solution but only a starter based on your code.  But I can answer any special question for any single issue you may encounter later ...


 




#include<iostream>

#include<process.h>

using namespace std;

 

// node structure follwos. each node has 3 parts : Value or info, No. of children, an array of pointers (dynamic) to point to n child nodes

struct GTreeNode

{

     int val;

     int NChild;

     GTreeNode *Child;

}*Root=NULL;

 

void CreateGeneralTree(GTreeNode*, int);

void ShowGeneralTree(GTreeNode*);         //will show  details of all nodes, one by one, not working fine. 

void ShowGTNode(GTreeNode *R);            //will dhow details of one node. ok.

 

int main()

{

    int i, val, n;

    GTreeNode *NewNode ;

    system("cls");

    //Create Root Node.

    cout<<"\nEnter Root Val " ;

    cin>>val ;

    cout<<"Enter No. of Children "  ;

    cin>>n;

 

    NewNode = new GTreeNode;

    if (n > 0) 

       NewNode->Child = new GTreeNode[n];

    else 

       NewNode->Child = NULL;
 

   // continue here

Open in new window

0
 

Author Comment

by:soodsandeep
ID: 24871586
O GOD !! please, how  many times i have to tell my experts, that
THIS IS NOT ANY SORT OF HOME WORK OR ASSIGNEMENT.

Please......
0
IT, Stop Being Called Into Every Meeting

Highfive is so simple that setting up every meeting room takes just minutes and every employee will be able to start or join a call from any room with ease. Never be called into a meeting just to get it started again. This is how video conferencing should work!

 

Author Comment

by:soodsandeep
ID: 24885924
Hi    itsmeandnobodyelse
following line is not working :

NewNode->Child = new GTreeNode[n];

Also, i have changed code a lot as suggested by you and Let_Me_B.
my new code, which is still not working is give below.
Please check and give ur suggestions.
AND, PLEASE, THIS IS NOT ASSIGNMENT.

#include<iostream.h>

#include<conio.h>

#include<alloc.h>

struct GTreeNode

{

     int val;

     int NChild;

     GTreeNode **Child;

}**Root=NULL;
 

void CreateGeneralTree(GTreeNode**,int);

void ShowGTNode(GTreeNode *R);
 

void main()

{

	int i, val, n;

	GTreeNode *NewNode ;

	clrscr();

	//Create Root Node.

	cout<<"\nEnter Root Val " ;

	cin>>val ;

	cout<<"Enter No. of Children "  ;

	cin>>n;

	NewNode=new GTreeNode;

	NewNode->val=val;

	NewNode->NChild=n;

	NewNode->Child[i]=new GTreeNode[n] ;

	Root=&NewNode;

	CreateGeneralTree(Root,n);

	ShowGTNode(*Root);

getch();

}
 

void CreateGeneralTree(GTreeNode **r, int n)

{

	int i,k, m;

	char ch ;

	//allocate memory for n children.

	for(i=0;i<n;i++)

	{

		(*r)->Child[i]=new GTreeNode;

		cout<<"\tEnter value for Child "<< i << " : ";

		cin>>(*r)->Child[i]->val;

		(*r)->Child[i]->NChild=0;

		*((*r)->Child[i]->Child)=NULL;

	}

	cout<<"\nDo You Wish to Enter Info of Child Nodes : ";

	ch=getche();

	if(ch=='y' || ch=='Y')

	{

		for(k=0;k<n;k++)

		{

			cout<<"\n "<<k<<" Enter No. of Children of " << (*r)->Child[k]->val<<"  : ";

			cin>>m;

			(*r)->Child[k]->NChild=m ;

			CreateGeneralTree(&((*r)->Child[k]),m);

		}

	}

}

void ShowGTNode(GTreeNode *R)

{

	int i,n=R->NChild;

	cout<<"\nInfo about "<<R->val;

	cout<<"\n\tNo. Of Children : "<<n ;

	for(i=0;i<n;i++)

		cout<<"\n\t"<<i<<"  "<<R->Child[i]<<"  "<<R->Child[i]->val<<"  "<<R->Child[i]->NChild;

	 for(i=0;i<n;i++)

		if(R->Child[i]->NChild>0)

			ShowGTNode(R->Child[i]) ;

getch();

}

Open in new window

0
 

Author Comment

by:soodsandeep
ID: 24885932
particullary, i am not sure about line no. 27. what it should be, and shoud it be or not.
Please help.

0
 
LVL 12

Expert Comment

by:Let_Me_Be
ID: 24885973
I'm sorry, but your code is still using pointer to pointers but you don't work with them that way, you still use them as if they were single pointers.

If you have a pointer to pointer, you must first allocate the outer one (in this case an array of pointers to children) and then the inner one. You only allocate the inner one.
0
 
LVL 39

Accepted Solution

by:
itsmeandnobodyelse earned 50 total points
ID: 24887534
>>>> I'm sorry, but your code is still using pointer to pointers but you don't work with them that way

Yes, if you would try to change to the code I gave you, we surely could make better than by still going on with the pointer to pointer ...

>>>> AND, PLEASE, THIS IS NOT ASSIGNMENT.

Ok, it is hard to believe cause we have another question regarding 'General Tree' where it is an assignment, but I will trust you.

I'll give you full main function and CreateGeneralTree which I turned from your code to use pointers rather than pointers to pointer. I tried to make as less changes as possible but I had to remove some logical flaws.

I expect you to at least try the remaining functions on your own. Even if it is not homework you obviously are a learner. And you won't learn if you simply have to do a copy-paste.

Note, you can ask me for each single error or statement where you have difficulties. But if you still post your old structure I couldn't help you.


// put here the code I posted previously 

...
 

// continue here

   NewNode->val=val;

   NewNode->NChild=n;   //new node has n children

   GTreeNode empty = { 0 };

   for(i=0;i<n;i++)

      NewNode->Child[i] = empty;  //initiall ymake them all  Null

   Root=NewNode; // root points to newnode. root is root of tree.

   CreateGeneralTree(Root, n); //now get details of n childern of root & their children

   //ShowGeneralTree(NewNode);

   cin >> i;

   return i;

}

 

void CreateGeneralTree(GTreeNode * r, int n)

{

   int i,k, m;

   char ch ;

 

   //Enter values of Child Nodes.

   cout<<"\nNode Created at : "<< r<<"\n";

   for(i=0;i<n;i++)

   {

      cout<<"\tEnter value for Child "<< i << " : ";

      cin>>r->Child[i].val;

      r->Child[i].NChild=0;

      r->Child[i].Child=NULL;

   }

   ShowGTNode(r);  //chek is it ok.

   cout<<"\nDo You Wish to Enter Info of Child Nodes : ";

   cin >> ch;

   if(ch=='y' || ch=='Y')

   {

      for(k=0;k<n;k++)

      {

         cout<<"\n "<<k<<" Enter No. of Children of " << r->Child[k].val<<"  : ";

         cin>>m;

         r->Child[k].NChild=m ;

         if (m > 0) 

            r->Child[k].Child = new GTreeNode[m];

         else 

            r->Child[k].Child = NULL;
 

         CreateGeneralTree(&r->Child[k],m);   //recurisive

      }

   }

}

 

void ShowGTNode(GTreeNode *R)

{

    // continue here

Open in new window

0
 

Author Comment

by:soodsandeep
ID: 24888048
Thanks LetMeBe and itsmeandnobodyelse for your help.
itsmeandnobodyelse, i am trying ur code. and thanks a lot for trusting me.
0
 

Author Comment

by:soodsandeep
ID: 24890197
Thanks itsmeandnobodyelse.
Its working.
here is final code after implementing ShowNode function also. i have some questions that i am posting in next post after loading this code.

#include<iostream.h>

#include<process.h>

#include<conio.h>

struct GTreeNode

{

     int val;

     int NChild;

     GTreeNode *Child;  //now its not an array of pointers, Please explain, why ?
 

}*Root=NULL;
 

void CreateGeneralTree(GTreeNode*, int);

void ShowGTNode(GTreeNode *R);            
 

int main()

{

    int i, val, n;

    GTreeNode *NewNode ;

    system("cls"); //does not work.may be becoz i m using Turbo C++ version 3.0

    clrscr();

    cout<<"\nEnter Root Val " ;

    cin>>val ;

    cout<<"Enter No. of Children "  ;

    cin>>n;

    NewNode = new GTreeNode;

    if (n > 0)

       NewNode->Child = new GTreeNode[n];

    else

       NewNode->Child = NULL;

   NewNode->val=val;

   NewNode->NChild=n;   //new node has n children

   GTreeNode empty = { 0 };

   for(i=0;i<n;i++)

      NewNode->Child[i] = empty;  //initially make them all  Null

   Root=NewNode; // root points to newnode. root is root of tree.

   CreateGeneralTree(Root, n); //now get details of n childern of root & their children

   cout<<"\n OUTPUT : \n";
 

   ShowGTNode(Root);

getch();

return 0;

}
 

void CreateGeneralTree(GTreeNode *r, int n)

{

   int i,k, m;

   char ch ;
 

   //Enter values of Child Nodes.

   cout<<"\nNode Created at : "<< r<<"\n";

   for(i=0;i<n;i++)

   {

      cout<<"\tEnter value for Child "<< i << " : ";

      cin>>r->Child[i].val;

      r->Child[i].NChild=0;

      r->Child[i].Child=NULL;

      //if empty was global, can it be written here also. i mean, is not empty as

      //declared by you is serving same as NULL.

   }

   cout<<"\nDo You Wish to Enter Info of Child Nodes : ";

   //cin >> ch;  //chaged to getche();

   ch=getche();

   if(ch=='y' || ch=='Y')

   {

      for(k=0;k<n;k++)

      {

	 cout<<"\n "<<k<<" Enter No. of Children of " << r->Child[k].val<<"  : ";

	 cin>>m;

	 r->Child[k].NChild=m ;

	 if (m > 0)

	    r->Child[k].Child = new GTreeNode[m];

	 else

	    r->Child[k].Child = NULL;

	 CreateGeneralTree(&r->Child[k],m);   //Recursive

       }

   }

}
 

void ShowGTNode(GTreeNode *R) //now its simple.

{

	int i,n;

	cout<<"\nInfo about "<<R->val;

	n=R->NChild ;

	cout<<"\tChildren : "<<n  <<"\tAs  : ";

	for(i=0;i<n;i++)

		cout<<R->Child[i].val<<" ";

	for(i=0;i<n;i++)

	     if(R->Child[i].NChild > 0)

		  ShowGTNode(&(R->Child[i]));

}

Open in new window

0
 

Author Comment

by:soodsandeep
ID: 24890207
Please check line no. 8,  57 and definition of
void ShowGTNode(GTreeNode *R).

Thanks a lot.
0
 
LVL 12

Expert Comment

by:Let_Me_Be
ID: 24890227
8: It's not array of pointers because you don't need array of pointers. You only need an array (array and pointer are interchangeable).

57: Sorry I don't understand the question.
0
 
LVL 39

Expert Comment

by:itsmeandnobodyelse
ID: 24891865
>>>> GTreeNode *Child;  //now its not an array of pointers, Please explain, why ?

It is now an array of nodes.

If you manage an array of pointers you would need to allocate memory for the array *and* for each slot of the array. That could have advantages if you want to sort the nodes after creation. You could swap the pointers much easier than swapping nodes. But  I can't see any need for a permanent sorting.  

>>>> i mean, is not empty as declared by you is serving same as NULL.
 
As Let_Me_Be told, a pointer in C/C++ can be used to point to an array - more precisily to the first element of an array - instead of pointing to a single element. Setting the pointer to NULL in either case means there is nothing to point to. In our case it would mean the node has no children. This information is redundant as we already have a member that counts the number of children. So, the empty function could be implemented as


    bool GTreeNode::empty() { return NChild == 0; }

or

    bool GTreeNode::empty() { return Child == NULL; }

and both is equivalent (as long as the node isn't corrupted).


>>>> definition of void ShowGTNode(GTreeNode *R).
Below is my code:

You see I omitted to calling ShowGTNode rekursively as that already was done with ShowGeneralTree. So, I used ShowGtNode only for giving feedback after a node with children was newly created.

void ShowGTNode(GTreeNode *R)

{

   int i, n=R->NChild;

   cout<<"\nNo. Of Children : "<<n<< " ";

   for(i=0;i<n;i++)

	cout<<R->Child[i].val << " ";

}

Open in new window

0

Featured Post

Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

Join & Write a Comment

This article will show you some of the more useful Standard Template Library (STL) algorithms through the use of working examples.  You will learn about how these algorithms fit into the STL architecture, how they work with STL containers, and why t…
IntroductionThis article is the second in a three part article series on the Visual Studio 2008 Debugger.  It provides tips in setting and using breakpoints. If not familiar with this debugger, you can find a basic introduction in the EE article loc…
The viewer will learn how to clear a vector as well as how to detect empty vectors in C++.
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

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

13 Experts available now in Live!

Get 1:1 Help Now