help with recursion code please

[csx]

Hi all,
I'm trying to count the number of leafnodes for a particular node.

What im trying to do is make a function, that taking the tree structure:

key row desc parent
1 1 A 0
2 2 B 1
3 2 C 1
4 3 D 3
5 3 E 3
6 4 F 4
7 4 G 4
8 4 H 4

which has the diagram:

http://www.pcm.uklinux.net/structure.jpg

The function would take a node, for instance, lets say we were to pass in
// passing in 'nodes[1]' (i.e. B) = should return - 0 leaf nodes
// passing in 'nodes[2]' (i.e. C) = should return - 4 leaf nodes
// passing in 'nodes[0]' (i.e. A) = should return - 5 leaf nodes


My problem is mainly with the implementation. Here's the code I currently
have:

The function 'int countLeafNodes( node parentNode)'

It works when there isnt a child associated with the parent. However, when
there are child nodes, I just dont know how to recursively search down to
the leaf nodes and count them.

could someone please help with the implementation for the function.



#include "stdafx.h"
#include <vector>

#include <iostream> // we have to use STD::cout with this
#include <string>
using namespace std; // Now don't need to specify the namespace, i.e.
STD::COUT

struct node
{
int key, row, parent;
char description;
node( int k=0, int r=0, char d='temp', int p=0 )
: key(k), row(r), description(d), parent(p) {}
};


vector<node> nodes;



// input - Pass in the node to use as the parent node (doesnt have to be the
root)
// output - The number of leaf nodes for the node passed in.
int countLeafNodes( node parentNode)
{
// simple case, check that is doesn't have any children.
for (int i=0; i<nodes.size() ; i++) {
// search though all nodes, lookup the parent field,
// see if 'parentNode.key ' is listed under parent field of other nodes.
// If none found, this indicates it doesn't have children!
if (parentNode.key != nodes[i].parent)
{
return 0; // no match found, return 0.
}
}


// a match was found.
// But need to recursively determine if this also has children
// and so on...
for (int j=0; j<nodes.size() ; j++) {
if (parentNode.key == nodes[j].parent)
{
int tempkey = nodes[j].key;

// tempkey will refer to one of the child nodes for the parent node
passed in
// but I then need to recursively check for their children
// and so on...
// return the count of all the leaf nodes for this parent.
}
}
}




int _tmain(int argc, _TCHAR* argv[])
{
nodes.resize(10 ); // allocate space for 10 nodes in the vector
nodes[0] = node(1,1,'A',0) ; // nodes[0]
nodes[1] = node(2,2,'B',1) ; // nodes[1]
nodes[2] = node(3,2,'C',1) ; // nodes[2]
nodes[3] = node(4,3,'D',3) ; // nodes[3]
nodes[4] = node(5,3,'E',3) ; // nodes[4]
nodes[5] = node(6,2,'F',4) ; // nodes[5]
nodes[6] = node(7,2,'G',4) ; // nodes[6]
nodes[7] = node(8,2,'H',4) ; // nodes[7]

// passing in 'nodes[1]' (i.e. B) = should return - 0 leaf nodes
// passing in 'nodes[2]' (i.e. C) = should return - 4 leaf nodes
// passing in 'nodes[0]' (i.e. A) = should return - 5 leaf nodes
int numChildren = countLeafNodes( nodes[2]);
cout << "number of leafnodes for this node is: " << numChildren << endl;

return 0;
}

Any help is much appreciated!
Thankyou in advance.

[Unforgiven]

Re: help with recursion code please

csx wrote:[color=blue]
> Hi all,
> I'm trying to count the number of leafnodes for a particular node.
>
> What im trying to do is make a function, that taking the tree
> structure:
>
> key row desc parent
> 1 1 A 0
> 2 2 B 1
> 3 2 C 1
> 4 3 D 3
> 5 3 E 3
> 6 4 F 4
> 7 4 G 4
> 8 4 H 4
>
> which has the diagram:
>
> http://www.pcm.uklinux.net/structure.jpg
>
> The function would take a node, for instance, lets say we were to
> pass in // passing in 'nodes[1]' (i.e. B) = should return - 0 leaf
> nodes // passing in 'nodes[2]' (i.e. C) = should return - 4 leaf
> nodes // passing in 'nodes[0]' (i.e. A) = should return - 5 leaf
> nodes
>
>
> My problem is mainly with the implementation. Here's the code I
> currently have:
>
> The function 'int countLeafNodes( node parentNode)'
>
> It works when there isnt a child associated with the parent. However,
> when there are child nodes, I just dont know how to recursively
> search down to the leaf nodes and count them.
>
> could someone please help with the implementation for the function.
>
>
>
> #include "stdafx.h"
> #include <vector>
>
> #include <iostream> // we have to use STD::cout with this
> #include <string>
> using namespace std; // Now don't need to specify the namespace, i.e.
> STD::COUT
>
> struct node
> {
> int key, row, parent;
> char description;
> node( int k=0, int r=0, char d='temp', int p=0 )
> : key(k), row(r), description(d), parent(p) {}
> };[/color]

There are better ways of building trees, but since I don't know what you're
trying to do eventually, this might be the best for your situation.
[color=blue]
> vector<node> nodes;
>
> // input - Pass in the node to use as the parent node (doesnt have to
> be the root)
> // output - The number of leaf nodes for the node passed in.
> int countLeafNodes( node parentNode)
> {
> // simple case, check that is doesn't have any children.
> for (int i=0; i<nodes.size() ; i++) {
> // search though all nodes, lookup the parent field,
> // see if 'parentNode.key ' is listed under parent field of other
> nodes. // If none found, this indicates it doesn't have children!
> if (parentNode.key != nodes[i].parent)
> {
> return 0; // no match found, return 0.
> }[/color]

This can't be right. Now the function returns 0 if the first node in the
vector is not a child of the current node, which can't possibly be what you
want to do.
[color=blue]
> }
>
> // a match was found.[/color]

You can't get here, unless *all* nodes are children of the current node,
which can't be true, unless there's only one node which is its own parent,
but that's a graph, not a tree.
[color=blue]
> // But need to recursively determine if this also has children
> // and so on...
> for (int j=0; j<nodes.size() ; j++) {
> if (parentNode.key == nodes[j].parent)
> {
> int tempkey = nodes[j].key;
>
> // tempkey will refer to one of the child nodes for the
> parent node passed in
> // but I then need to recursively check for their children
> // and so on...
> // return the count of all the leaf nodes for this parent.
> }
> }
> }[/color]

You'll need something more along these lines:

int countLeafNodes( const node &parentNode) /* note the reference (&): it
saves stack space, which can be important if you're doing very deep
recursion */
{
int totalLeafs = 0;
bool hasChildren = false;
for( int i = 0; i < nodes.size(); i++ )
{
if( parentNode.key == nodes[i].key ) /* nodes[i] is a child */
{
totalLeafs += countLeafNodes( nodes[i]);
hasChildren = true;
}
}
if( hasChildren )
return totalLeafNodes;
else /* this node is a leaf itself */
return 1;
}

You also might consider implementing the for-loop using iterators.

This can be done much more effecient if you use a struct/class representing
a node that has pointers to its children instead of a global node-list.

--
Unforgiven

"Most people make generalisations "
Freek de Jonge

[csx]

Re: help with recursion code please

Hi and thankyou!! for the helping with the code. But Idont think it does
what I need, which is my fault for not clearly explaining it.
With reference to the diagram I created:

http://www.pcm.uklinux.net/structure.jpg

For the Node3 (i.e. C) it should return a count of 4. These would be 6, 7,
8, and 5 which are F, G, H and E respectively.
I need to go right to the bottom of the tree structure and get a count of
the leaf nodes.

So, for the root node, A. The count would be 5.
These nodes would be B, F, G, H, E.

Its this that I just can't figure out how to do.



[color=blue]
> You'll need something more along these lines:
>
> int countLeafNodes( const node &parentNode) /* note the reference (&): it
> saves stack space, which can be important if you're doing very deep
> recursion */
> {
> int totalLeafs = 0;
> bool hasChildren = false;
> for( int i = 0; i < nodes.size(); i++ )
> {
> if( parentNode.key == nodes[i].key ) /* nodes[i] is a child */
> {
> totalLeafs += countLeafNodes( nodes[i]);
> hasChildren = true;
> }
> }
> if( hasChildren )
> return totalLeafNodes;
> else /* this node is a leaf itself */
> return 1;
> }
>[/color]