c++ - 获取二叉搜索树中的节点数

Question

所以我正在研究一种获取二叉搜索树中节点数的方法，当我有 3 个节点时，它给了我 3，但是如果我做 5，它给了我 4，我需要改变什么？

int BinaryTree::size(int count, Node *leaf) const
{
    if(leaf != NULL)//if we are not at a leaf
    {
        size(count + 1, leaf->getLeft());//recurisvly call the function and increment the count
        size(count + 1, leaf->getRight());
    }
    else
    {
        return count;//return the count
    }

}

Answer 1

int BinaryTree::size(Node *leaf) const 
{
    if(leaf == NULL) { //This node doesn't exist. Therefore there are no nodes in this 'subtree'
        return 0;
    } else { //Add the size of the left and right trees, then add 1 (which is the current node)
        return size(leaf->getLeft()) + size(leaf->getRight()) + 1;
    }
}

虽然这是一种不同的方法，但我发现它比你所拥有的更容易阅读。

Answer 2

其他人已经提出了正确的算法。我只是要解释为什么你的算法不起作用。

您的算法背后的逻辑似乎是：保持运行计数值。如果叶子为空，则它没有子节点，因此返回计数，如果叶子不为空，则向下递归子节点。

虽然这是倒退。因为您将需要通过引用而不是值来传递您的 int，如果它为空则不递增，如果它不为空则递增，然后递归。

因此，您最初的想法可以进行一些修改，但 Nick Mitchinson 和箭头有更好的方法。这是您的算法已修复，因此可以正常工作：

int BinaryTree::size(Node *leaf, int& count=0) const
{
    if(leaf != NULL)//if we are not at a leaf
    {
        count++;
        size(leaf->getLeft(), count);//recurisvly call the function and increment the count
        size(leaf->getRight(), count);
    }

    return count;//return the count
}

但同样，有更好的方法来写这个。其他答案显示了它们。

Answer 3

int BinaryTree::size(Node *n) const
{
    if(!n) 
        return 0;
    else
        return size(n->getLeft()) + 1 + size(n->getRight()); 
}