c++ - BST - 查找元素的数量

Question

有没有办法找到二叉搜索树中元素的数量？

struct node
{
    node *p, *left, *right;
    int key;
};

这是我节点的结构，p 指针指向父元素。

我需要找到该数字来分配内存以搜索树并返回包含所有元素的数组。

我想出了这样的事情：

int numberOfElements(node *root, int count = 0)
{
    if(root)
    {
        numberOfElements(root->left, ++count);
        numberOfElements(root->right, ++count);
    }
    return count + 1;
}

但是，它显示了一些随机结果：P 对于“1、2”显示 2，对于“1、2、3、4、5、6、7”，它显示 3 等等...

我想在一个函数中执行此操作，这就是为什么 count 是这里的一个参数。

我怎样才能做到这一点？

Answer 1

您似乎根本没有使用的返回值numberOfElements。此版本可能有效：

int numberOfElements(node *root)
{
    if(root)
    {
        return numberOfElements(root->left) + 
               numberOfElements(root->right) + 1;
    }
    return 0;
}

通常，这种树的大小应该记录在一个字段中，并且每次修改树时都会更新。没有人期望 O(N) 运行时间只是为了找到一棵树的大小。

Answer 2

您不需要第二个参数：

int numberOfElements(node *root) {
    if (root) {
        return 1 + numberOfElements(root->left) + numberOfElements(root->right);
    } else {
        return 0;
    }
}