c - 搜索二叉搜索树，使用计数器进行迭代

Question

我有一个正在使用的函数，它在二叉搜索树中搜索一个数字。我使用了一个外部 int，它可以在每次迭代时由函数递增，因为如果数字不是根，函数会调用自身。

我只是在学习二叉搜索树，但我知道我忽略了一种更好的方法......例如使用返回计数器的 int 方法，但我无法弄清楚......

编辑：我知道数字肯定会在 BST 中，我只需要看看 BST 搜索与通过数组搜索相同数字的效果如何。

// This external int can be incremented by the searchBST function 
// to keep track of iterations

int bcounter = 0;

// Search Binary Search Tree function

node* searchBST(node ** tree, int num){

bcounter++;

if(num < (*tree)->data) {
    searchBST(&((*tree)->left), num);
}
else 
    if(num > (*tree)->data) {
    searchBST(&((*tree)->right), num);
}
else 
    if(num == (*tree)->data) {
    return *tree;
}
}

Answer 1

您的计数器正在计算找到的元素的深度，而不是树中元素的数量。如果那是您正在寻找的东西，那么您很好。

如果你想找出元素的数量，你需要做类似的事情

if (node is not null) {
  // count this node, it is not null
  count++;
  visit(node left);
  visit(node right);
}

首先访问左还是右并不重要，您只想访问所有感兴趣的节点。