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.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]

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) {}
};

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.

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.parent)
{
return 0; // no match found, return 0.
}

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.

}

// a match was found.

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.

// 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.
}
}
}

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.key ) /* nodes is a child */
{
totalLeafs += countLeafNodes(nodes);
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.

 

[csx]

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.