Counting nodes in a tree

[David]

I have a simple tree structure where node x can have y children.
Node x's children are stored in an array.
I want to supply a node to a function and count the TOTAL number of
children for that node.
This is what I have come up with so far:

function count_total_chi ldren($tree)
{
$num_of_c = $tree->get_num_child( );
echo $num_of_c.'+';
$child_array = $tree->get_child_arr( );

for($i=0;$i<$nu m_of_c;++$i)
{
count_total_chi ldren($child_ar ray[$]);
}
}

Now this clearly does not work but its the closest I've come. What
this bit of code does is if a node has 5 children it will output
something like:

1+2+0+0+2+

Rather than print out the number I need to add it to a running total,
but I just cant seem to do it!

Ive tried using references but it doesnt work when you do the
recursive call?

Any help very greatly welcomed!

[Martin Buchleitner]

Re: Counting nodes in a tree

* biffta@hotmail. com (David) wrote:
[color=blue]
> I have a simple tree structure where node x can have y children.
> Node x's children are stored in an array.
> I want to supply a node to a function and count the TOTAL number of
> children for that node.
> This is what I have come up with so far:
>
> function count_total_chi ldren($tree)
> {
> $num_of_c = $tree->get_num_child( );
> $child_array = $tree->get_child_arr( );[/color]
$num_of_sub_c = 0;[color=blue]
> for($i=0;$i<$nu m_of_c;++$i)
> {[/color]
$num_of_sub_c += count_total_chi ldren($child_ar ray[$]);[color=blue]
> }[/color]
return num_of_c + num_of_sub_c;[color=blue]
> }
>[/color]

echo "Childrens: " + count_total_chi ldren($tree);



hth mabu

ps: just a short think about - errors could happen ;)

--
Are you Anonymous? Where? ... I don't think so ...

[ devnull{at}chao sfactory{dot}or g | http://www.chaosfactory.org/ ]

[Savut]

Re: Counting nodes in a tree

function count_total_chi ldren($tree) {
$num_of_c = $tree->get_num_child( );
echo $num_of_c.'+';
$child_array = $tree->get_child_arr( );

for($i=0;$i<$nu m_of_c;++$i) {
count_total_chi ldren($child_ar ray[$]);
}
}

You mean this is your code ? Should not work at all as count_total_chi ldren
is looped inside count_total_chi ldren

Savut

"David" <biffta@hotmail .com> wrote in message
news:3eb239cb.0 403100930.2a129 bce@posting.goo gle.com...[color=blue]
> I have a simple tree structure where node x can have y children.
> Node x's children are stored in an array.
> I want to supply a node to a function and count the TOTAL number of
> children for that node.
> This is what I have come up with so far:
>
> function count_total_chi ldren($tree)
> {
> $num_of_c = $tree->get_num_child( );
> echo $num_of_c.'+';
> $child_array = $tree->get_child_arr( );
>
> for($i=0;$i<$nu m_of_c;++$i)
> {
> count_total_chi ldren($child_ar ray[$]);
> }
> }
>
> Now this clearly does not work but its the closest I've come. What
> this bit of code does is if a node has 5 children it will output
> something like:
>
> 1+2+0+0+2+
>
> Rather than print out the number I need to add it to a running total,
> but I just cant seem to do it!
>
> Ive tried using references but it doesnt work when you do the
> recursive call?
>
> Any help very greatly welcomed![/color]

[David]

Re: Counting nodes in a tree

> You mean this is your code ? Should not work at all as count_total_chi ldren[color=blue]
> is looped inside count_total_chi ldren[/color]

Ever hear of a little thing named recursion?

[David]

Re: Counting nodes in a tree

If we forget errors for the time being this does not work:
[color=blue]
> function count_total_chi ldren($tree)
> {
> $num_of_c = $tree->get_num_child( );
> **echo $num_of_c;
> $child_array = $tree->get_child_arr( );
> $num_of_sub_c = 0;
> for($i=0;$i<$nu m_of_c;++$i)
> {
> $num_of_sub_c += count_total_chi ldren($child_ar ray[$]);
> }
> return num_of_c + num_of_sub_c;
> }
>
>
> echo "Childrens: " + count_total_chi ldren($tree);[/color]

This simply returns 0 every time. HOWEVER if we echo to the screen
$num_of_c seen at **, thie output the numbers we are trying to add up
e.g. 1+0+3...

This means the function is working but we are losing track these
variable as we go through.

The problem remains how do we keep track of these values then return
them at the end???

[Eric Bohlman]

Re: Counting nodes in a tree

biffta@hotmail. com (David) wrote in
news:3eb239cb.0 403100930.2a129 bce@posting.goo gle.com:
[color=blue]
> I have a simple tree structure where node x can have y children.
> Node x's children are stored in an array.
> I want to supply a node to a function and count the TOTAL number of
> children for that node.[/color]

I think you mean the total number of *descendants*; when talking about tree
structures, "children" refers only to the *immediate* descendants of a
node.
[color=blue]
> This is what I have come up with so far:
>
> function count_total_chi ldren($tree)
> {
> $num_of_c = $tree->get_num_child( );
> echo $num_of_c.'+';
> $child_array = $tree->get_child_arr( );
>
> for($i=0;$i<$nu m_of_c;++$i)
> {
> count_total_chi ldren($child_ar ray[$]);
> }
> }
>
> Now this clearly does not work but its the closest I've come. What
> this bit of code does is if a node has 5 children it will output
> something like:
>
> 1+2+0+0+2+
>
> Rather than print out the number I need to add it to a running total,
> but I just cant seem to do it![/color]

Merely echoing a bunch of numbers followed by plus signs doesn't cause PHP,
or whatever's displaying the output, to add them up.

A function should return a value. What you want is something like:

function count_descendan ts($tree)
{
$num_of_c = $tree->get_num_child( );
$num_descendant s = $num_of_c;
$child_array = $tree->get_child_arr( );

for($i=0;$i<$nu m_of_c;++$i)
{
$num_descendant s += count_descendan ts($child_array[$i]);
}
return($num_des cendants);
}

Note that it's important here that $num_descendant s be a local variable
rather than a global one, since each recursive invocation of the function
needs its own value for it.

[php newbie]

Re: Counting nodes in a tree

You are close. You need to add the individual results up like this:

function count_total_chi ldren($tree)
{
$num_children = 0;

$child_array = $tree->get_child_arr( );
for($i=0;$i<$nu m_of_c;++$i)
{
count_total_chi ldren($child_ar ray[$]);
}

return $num_children + $tree->get_num_child( );
}



biffta@hotmail. com (David) wrote in message news:<3eb239cb. 0403100930.2a12 9bce@posting.go ogle.com>...[color=blue]
> I have a simple tree structure where node x can have y children.
> Node x's children are stored in an array.
> I want to supply a node to a function and count the TOTAL number of
> children for that node.
> This is what I have come up with so far:
>
> function count_total_chi ldren($tree)
> {
> $num_of_c = $tree->get_num_child( );
> echo $num_of_c.'+';
> $child_array = $tree->get_child_arr( );
>
> for($i=0;$i<$nu m_of_c;++$i)
> {
> count_total_chi ldren($child_ar ray[$]);
> }
> }
>
> Now this clearly does not work but its the closest I've come. What
> this bit of code does is if a node has 5 children it will output
> something like:
>
> 1+2+0+0+2+
>
> Rather than print out the number I need to add it to a running total,
> but I just cant seem to do it!
>
> Ive tried using references but it doesnt work when you do the
> recursive call?
>
> Any help very greatly welcomed![/color]

[David]

Re: Counting nodes in a tree

> I think you mean the total number of *descendants*; when talking about tree[color=blue]
> structures, "children" refers only to the *immediate* descendants of a
> node.[/color]

OK!
[color=blue]
> Merely echoing a bunch of numbers followed by plus signs doesn't cause PHP,
> or whatever's displaying the output, to add them up.[/color]

Give me some credit! I just wanted to illustrate that the function was
iterating correctly so the problem was the lack of a running counter.
[color=blue]
> A function should return a value. What you want is something like:
>
> function count_descendan ts($tree)
> {
> $num_of_c = $tree->get_num_child( );
> $num_descendant s = $num_of_c;
> $child_array = $tree->get_child_arr( );
>
> for($i=0;$i<$nu m_of_c;++$i)
> {
> $num_descendant s += count_descendan ts($child_array[$i]);
> }
> return($num_des cendants);
> }[/color]

I tried this and it works very well, but in the meantime got it to
work a different way. What do you think?

function count_total_des c($tree,&$count er){

$num_of_c = $tree->get_num_child( );
$child_array = $tree->get_child_arr( );

for($i=0;$i<$nu m_of_c;++$i){
$counter++;
count_total_chi ldren($child_ar ray[$i],$counter);
}
return $counter;
}

/*So you call the function like this:*/

$counter = 0;
count_total_des c($tree,$counte r);

[php newbie]

Re: Counting nodes in a tree

Oops! There was an omission in the loop. Here is the code:

function count_total_chi ldren($tree)
{
$num_children = 0;

$child_array = $tree->get_child_arr( );
for($i=0;$i<$nu m_of_c;++$i)
{
$num_children += count_total_chi ldren($child_ar ray[$i]);
}

return $num_children + $tree->get_num_child( );
}



newtophp2000@ya hoo.com (php newbie) wrote in message news:<124f428e. 0403110938.2754 c942@posting.go ogle.com>...[color=blue]
> You are close. You need to add the individual results up like this:
>
> function count_total_chi ldren($tree)
> {
> $num_children = 0;
>
> $child_array = $tree->get_child_arr( );
> for($i=0;$i<$nu m_of_c;++$i)
> {
> count_total_chi ldren($child_ar ray[$]);
> }
>
> return $num_children + $tree->get_num_child( );
> }
>[/color]