Count the number of leaf in a 2-3 Tree, C++

Question

0.00/5 (No votes)

See more:

Hello everyone ! Now, I am trying to get the number of leaf (nodes has no children) in a 2-3 tree. In my code, I am always getting the same number of leaf which is 1, and it should be more than 1. I do not know what is wrong with my code? Please, anyone can give me any ideas !!!!

Thank You,

C++

int Tree::IsLeaf(node *&root)
{
    if(!root)
    {
        return 0;
    }
    else if(!root->left &&  !root->middle && !root->right)
    {
        return 1;
    }
    else
    {
        return IsLeaf(root->left) + IsLeaf(root->middle) + IsLeaf(root->right);
    }
}

Posted 22-Aug-13 16:40pm

Member 10205297

Updated 22-Aug-13 20:15pm

nv3

v2

Add a Solution

Comments

Philippe Mori 24-Aug-13 9:59am

To help you, we need to see the definition of node class. It might be there that there is a conflict. Does left, middle and right return pointers or reference? In the latter case, is there any possible conversion to bool in which case it might explain the weird behavior.

By the way, it would be very easy to figure out the problem using a debugger. For example, you can put a breakpoint on each return line and see if they are hit at least one each (in the case the has more than one node).

3 solutions

Solution 4

Your code looks correct to me, but just a little clumsy. So it should actually do the right thing. The bug must be in another part of the code. Why don't you improve your question by appending the code that calls your function and we take a look at that.

What I find clumsy about your code is mostly the naming. I would expect a function "IsLeaf" to return a bool which is true if this is a leaf node. In your case I would name the function: CountLeafNodes.

You have named the first and only argument of your function root. But in fact, you intend to call the function on any node, not just the root node of the tree. So why don't you name it then pNode? And as you are not going to return a value via this argument, I would transfer it by value and not by reference. So would bring us to:

C++

int Tree::CountLeafNodes (node* pNode)

Now things start to fall in place. The last little modification I would suggest is to move this entire code into your node class. In your code you are accessing the members of class node in many locations and that is a sure sign that your function sits in the wrong class. If you make that a member function of node, things look even easier:

C++

int node::CountLeafNodes ()
{
    // are we a leaf node, then return 1
    if (left==0 && middle==0 && right==0)
        return 1;

    // count the sum of leaf nodes of all our sub-trees
    int count = 0;
    if (left)
        count += left->CountLeafNode();
    if (middle)
        count += middle->CountLeafNode();
    if (right)
        count += right->CountLeafNode();
    return count;
}

Looks a lot easier to read, doesn't it?

Posted 23-Aug-13 3:28am

nv3

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

nv3 · Accepted Answer · 2013-08-23T03:28:00

Your code looks correct to me, but just a little clumsy. So it should actually do the right thing. The bug must be in another part of the code. Why don't you improve your question by appending the code that calls your function and we take a look at that.

What I find clumsy about your code is mostly the naming. I would expect a function "IsLeaf" to return a bool which is true if this is a leaf node. In your case I would name the function: CountLeafNodes.

You have named the first and only argument of your function root. But in fact, you intend to call the function on any node, not just the root node of the tree. So why don't you name it then pNode? And as you are not going to return a value via this argument, I would transfer it by value and not by reference. So would bring us to:

C++

int Tree::CountLeafNodes (node* pNode)

Now things start to fall in place. The last little modification I would suggest is to move this entire code into your node class. In your code you are accessing the members of class node in many locations and that is a sure sign that your function sits in the wrong class. If you make that a member function of node, things look even easier:

C++

int node::CountLeafNodes ()
{
    // are we a leaf node, then return 1
    if (left==0 && middle==0 && right==0)
        return 1;

    // count the sum of leaf nodes of all our sub-trees
    int count = 0;
    if (left)
        count += left->CountLeafNode();
    if (middle)
        count += middle->CountLeafNode();
    if (right)
        count += right->CountLeafNode();
    return count;
}

Looks a lot easier to read, doesn't it?

saad_lah · Accepted Answer · 2013-08-22T19:56:00

Solution 2

Try something like this...

C++

int count=0;     // you can use count with & sign in function parameters

int tree(node *&root)
{
    if(!root)
    {  
          return 0;
    }
    else if(!root->left && !root->middle && !root->right)
    { 
             count++;
    }
    else if(root->left)
    {
          tree(root->left);
    }
    else if(root->middle)
    {
          tree(root->middle);
    }
    else if( root->right)
    {
    tree(root->right);
    }
 return count;
}

P.S: I haven't tested this.

Posted 22-Aug-13 19:56pm

saad_lah

Updated 22-Aug-13 20:17pm

v3

Comments

Member 10205297 23-Aug-13 4:38am

THANK YOU FOR YOUR RESPONSE, BUT YOUR CODE IS INCORRECT !!!! THANK YOU AGAIN, I ALREADY FOUND THE CORRECT SOLUTION.

saad_lah 23-Aug-13 10:44am

But it is working.

Philippe Mori 24-Aug-13 9:53am

Not much different or better than original code.