Want to win a PS4? Go Premium and enter to win our High-Tech Treats giveaway. Enter to Win

x
Solved

# Implementing General Tree

Posted on 2009-07-15
Medium Priority
4,808 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]);
}
``````
0
Question by:soodsandeep
[X]
###### Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

• Help others & share knowledge
• Earn cash & points
• Learn & ask questions
• 8
• 4
• 4
• +1
17 Comments

LVL 40

Expert Comment

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

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

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

ID: 24867627
i also request infinity08, to please check this.
0

LVL 39

Expert Comment

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

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 ;
``````
0

LVL 39

Expert Comment

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
``````
0

Author Comment

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

Author Comment

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();
}
``````
0

Author Comment

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

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

itsmeandnobodyelse earned 200 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
``````
0

Author Comment

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

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]));
}
``````
0

Author Comment

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

Thanks a lot.
0

LVL 12

Expert Comment

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

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 << " ";
}
``````
0

## Featured Post

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

When writing generic code, using template meta-programming techniques, it is sometimes useful to know if a type is convertible to another type. A good example of when this might be is if you are writing diagnostic instrumentation for code to generatâ€¦
Container Orchestration platforms empower organizations to scale their apps at an exceptional rate. This is the reason numerous innovation-driven companies are moving apps to an appropriated datacenter wide platform that empowers them to scale at a â€¦
The viewer will learn how to pass data into a function in C++. This is one step further in using functions. Instead of only printing text onto the console, the function will be able to perform calculations with argumentents given by the user.
The viewer will be introduced to the technique of using vectors in C++. The video will cover how to define a vector, store values in the vector and retrieve data from the values stored in the vector.
###### Suggested Courses
Course of the Month10 days, 14 hours left to enroll

#### 618 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.