计算2-3 Tree，C ++中叶子的数量 [英] Count the number of leaf in a 2-3 Tree, C++

问题描述

大家好！现在，我试图在2-3树中获取叶子数（节点没有子节点）。在我的代码中，我总是得到相同数量的叶子，它是1，它应该大于1.我不知道我的代码有什么问题？拜托，任何人都可以给我任何想法!!!!



谢谢，

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,

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

推荐答案

你的代码对我来说是正确的，但只是有点笨拙。所以它应该做正确的事情。该错误必须在代码的另一部分。你为什么不通过附加调用你的函数的代码来改进你的问题，我们看看它。



我发现你的代码几乎是笨拙的命名。我希望函数IsLeaf返回一个bool，如果这是一个叶节点，则为true。在你的情况下，我会命名函数： CountLeafNodes 。



你已经命名了你的第一个也是唯一一个参数function root 。但实际上，您打算在任何节点上调用该函数，而不仅仅是树的根节点。那你为什么不命名呢 pNode ？因为你不会通过这个参数返回一个值，我会按值而不是通过引用来传递它。所以会带我们：

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:

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:

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?

尝试这样的事情......

Try something like this...

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

PS：我还没有测试过这个。

P.S: I haven't tested this.

你的代码对我来说看起来不对，但只是有点笨拙。所以它应该做正确的事情。该错误必须在代码的另一部分。你为什么不通过附加调用你的函数的代码来改进你的问题，我们看看它。



我发现你的代码几乎是笨拙的命名。我希望函数IsLeaf返回一个bool，如果这是一个叶节点，则为true。在你的情况下，我会命名函数： CountLeafNodes 。



你已经命名了你的第一个也是唯一一个参数function root 。但实际上，您打算在任何节点上调用该函数，而不仅仅是树的根节点。那你为什么不命名呢 pNode ？因为你不会通过这个参数返回一个值，我会按值而不是通过引用来传递它。所以会带我们：

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:

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:

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?

这篇关于计算2-3 Tree，C ++中叶子的数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！