BST - 查找元素数量

有没有方法可以找到二叉搜索树中的元素数量？BST - 查找元素数量

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是一个参数在这里。

我该怎么做？

来源

2013-04-20 user2252786

记得按引用次数传递。 – stardust 2013-04-20 16:28:21

或保存返回值并将它们相加。 – Detheroc 2013-04-20 16:29:29

你似乎从你的函数中返回一些东西。我想知道这样的事情可能会有用。如果我们只能调用一个函数，然后以某种方式查看这个值，并且可能将其保存以供将来参考... – 2013-04-20 16:31:02

你不需要第二个参数：

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

来源

2013-04-20 16:32:14 NPE

不错！谢谢：D – user2252786 2013-04-20 16:33:30

你似乎并不在所有使用的numberOfElements返回值。该版本可能工作：

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

通常，这种树的大小应该被记录在一个领域，你每次修改树时被更新。没有人期望O（N）运行时间只是为了找到一棵树的大小。

来源

2013-04-20 16:33:37

@seh哦，我的错，已更新。 – 2013-04-20 16:36:16

BST - 查找元素数量

回答

相关问题