C++ 获取二叉搜索树中的节点数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/15372979/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
getting the number of nodes in a binary search tree
提问by compprog254
So I'm working on a method that gets the number of nodes in a binary search tree, when I have 3 nodes, it gives me 3, but if I do 5 it gives me 4, what do I need to change?
所以我正在研究一种获取二叉搜索树中节点数的方法，当我有 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
}
}
回答by Nick Mitchinson
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;
}
}
While this is a different approach, I find that is it easier to read through than what you had.
虽然这是一种不同的方法，但我发现它比你所拥有的更容易阅读。
回答by OmnipotentEntity
Other people have already chimed in with a correct algorithm. I'm just going to explain why your algorithm doesn't work.
其他人已经加入了正确的算法。我只是要解释为什么你的算法不起作用。
The logic behind your algorithm seems to be: keep a running count value. If the leaf is null then it has no children so return the count, if the leaf is not null then recurse down the children.
你的算法背后的逻辑似乎是：保持一个运行计数值。如果叶子为空，则它没有孩子，因此返回计数，如果叶子不为空，则向下递归孩子。
This is backwards though. Because you're going to need to pass your int by reference, not value, and then not increment if it's null, increment if it's not null, and recurse.
虽然这是倒退。因为你需要通过引用传递你的 int，而不是值，如果它为空则不递增，如果它不为空则递增，然后递归。
So your original idea would work with some modifications, but Nick Mitchinson and arrows have a better way. This is your algorithm fixed so it works:
因此，您最初的想法可以进行一些修改，但 Nick Mitchinson 和 Arrows 有更好的方法。这是你的算法固定所以它的工作原理：
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
}
But again, there are better ways to write this. And the other answers show them.
但同样，有更好的方法来写这个。其他答案显示了它们。
回答by OmnipotentEntity
int BinaryTree::size(Node *n) const
{
if(!n)
return 0;
else
return size(n->getLeft()) + 1 + size(n->getRight());
}
