DaniWeb Forum Index > Software Development > C

C RSS

recursive findaverage function for Binary search tree

•

Join Date: Apr 2004

Posts: 353

Reputation: Asif_NSU is on a distinguished road

Solved Threads: 3

Asif_NSU

Offline

Posting Whiz

recursive findaverage function for Binary search tree

Nov 21st, 2004

I need to add a recursive function, called findaverage() into BST class that takes as input the root of the BST and returns the average of the entire integer items stored in that BST of integers.

Plz help me with this function especially without using any static variables.

"He who mixes with people and endures the harm they do is better than he who does not mix and endures." (Tirmidhi)

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 11

Chainsaw

Offline

Unprevaricator

Re: recursive findaverage function for Binary search tree

Nov 21st, 2004

How about something along these lines, assuming every node has a value 'myValue' and a left and right child pointer:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
int BST::findTotal( int &nodesFound )
{
    nodesFound++;
    int total = myValue;
    if (left != NULL) total += left->findTotal( nodesFound );
    if (right != NULL) total += right->findTotal( nodesFound );
    return total;
}
. . . 
    // Find average:
    int nodesFound = 0;
    int total = root.FindTotal( nodesFound );
    printf( "average is %d in %d nodes\n", (nodesFound == 0) ? 0 : total/nodesFound, nodesFound );
int BST::findTotal( int &nodesFound )
{
    nodesFound++;
    int total = myValue;
    if (left != NULL) total += left->findTotal( nodesFound );
    if (right != NULL) total += right->findTotal( nodesFound );
    return total;
}
. . . 
    // Find average:
    int nodesFound = 0;
    int total = root.FindTotal( nodesFound );
    printf( "average is %d in %d nodes\n", (nodesFound == 0) ? 0 : total/nodesFound, nodesFound );

•

Join Date: Apr 2004

Posts: 353

Reputation: Asif_NSU is on a distinguished road

Solved Threads: 3

Asif_NSU

Offline

Posting Whiz

Re: recursive findaverage function for Binary search tree

Nov 22nd, 2004

i wanted to see the findaverage function independent. Most of my friends solved the problem using a global variable total and some did using static variables(none of which i liked). There are two things involved into finding the average recursively. First i need to find the total which i can do using a separate recursive function. Then i can also write a recursive function to count the number of nodes. The last thing is to divide the total with the number of treenodes. But the problem was set to test if we could incorporate the functionality of these two recursive functions into one recursive function in order to find the average. I think i once read something called running sum and running average. I think that might help me do this the way i want. But the problem is i dont quite remember it clearly. Can anyone help?

"He who mixes with people and endures the harm they do is better than he who does not mix and endures." (Tirmidhi)

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 11

Chainsaw

Offline

Unprevaricator

Re: recursive findaverage function for Binary search tree

Nov 22nd, 2004

I suppose with floating point numbers you could keep a running average as you go, but why do this extra weirdness when you can get the total and total count recursively? Is it just because that's the assignment?

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 11

Chainsaw

Offline

Unprevaricator

Re: recursive findaverage function for Binary search tree

Nov 22nd, 2004

And, using statics and globals really undermines the meaning of a recursive function, in my humble opinion. It also makes the function non-thread-safe, which may be ok in this instance but isn't a good general-purpose solution.

At the very least, you could have a class that contains member variables so you don't need globals and statics; something like:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
class ABSTAverage
{
public:
    ABSTAverage()
    {
        m_total = 0;
        m_count = 0; // replacement for globals
    }
    int findAverage( BST* node )
    {
        if (node == NULL) return 0;
        m_count++;
        m_total += node->myValue; 
        findAverage( node->left );
        findAverage( node->right );
        return m_total / m_count;   // return the average
    }
protected:
    int m_total, m_count;
};
class ABSTAverage
{
public:
    ABSTAverage()
    {
        m_total = 0;
        m_count = 0; // replacement for globals
    }
    int findAverage( BST* node )
    {
        if (node == NULL) return 0;
        m_count++;
        m_total += node->myValue; 
        findAverage( node->left );
        findAverage( node->right );
        return m_total / m_count;   // return the average
    }
protected:
    int m_total, m_count;
};

And that would be better, but it still seems sorta inelegant.

•

Join Date: Apr 2004

Posts: 353

Reputation: Asif_NSU is on a distinguished road

Solved Threads: 3

Asif_NSU

Offline

Posting Whiz

Re: recursive findaverage function for Binary search tree

Nov 23rd, 2004

•

I suppose with floating point numbers you could keep a running average as you go, but why do this extra weirdness when you can get the total and total count recursively? Is it just because that's the assignment?

>>I know it's weird, and yes thats just bcos it was the assignment. You said i could do this with running average, could u plz show me how?That's what i have been trying to do. Unfortunately, i dont remember that running avg thing very well.

•

using statics and globals really undermines the meaning of a recursive function, in my humble opinion.

>>I do agree with u, and that's why i have been looking for something different.

•

you could have a class that contains member variables so you don't need globals and statics

>>But this findaverage() was supposed to be a member function of my BST(binary search tree) class. Making another class would somehow complicate things(right?), and the assignment asked us to write only a recursive function to do the job. I had to do it something like this:

 Help with Code Tags 
 C Syntax (Toggle Plain Text) 
int main()
{
     BST mytree;
    //insert nodes  into the tree
    cout<<"\nAVERAGE = "<<mytree.FindAverage(mytree.getRoot());//passed the root of tree to the findaverage function
    return 0;
}
int main()
{
     BST mytree;
    //insert nodes  into the tree
    cout<<"\nAVERAGE = "<<mytree.FindAverage(mytree.getRoot());//passed the root of tree to the findaverage function
    return 0;
}

"He who mixes with people and endures the harm they do is better than he who does not mix and endures." (Tirmidhi)

•

Join Date: Jun 2004

Posts: 436

Reputation: Chainsaw is an unknown quantity at this point

Solved Threads: 11

Chainsaw

Offline

Unprevaricator

Re: recursive findaverage function for Binary search tree

Nov 23rd, 2004

I'm no math major, but the running average idea is something like this:

can you add these as static members to BST? Static because you need this for the whole tree, not just for a single node:

...
static double m_averageSoFar; // used only in findAverage()
static double m_averageCount; // ditto
...

and those get initialized to zero SOMEHOW when you call findAverage for the very first time. Ick ick ick. Like "if (node == &root) <set statics to zero>" I hate that!

for each node, you would say something like:

// reconstitute the total and add this node's value
double totalSoFar = (m_averageSoFar * m_averageCount) + (double)myValue;
m_averageCount += 1.0; // account for this new node
m_averageSoFar = (totalSoFar / m_averageCount); // running average

Have you considered the possability that the lesson here is that some things don't directly lend themselves to a recursive algorithm? That maybe something like computing the total value and count might be well suited to recursion, but average needs:
<setup>
call a different recursive function (like getting total value/count)
<finish>

?
Maybe its a trick question! :-)