计数小于BST中小于x的节点的数量

Question

我有一个给我这些问题的代码。您能给我一些提示或指南，以了解我要犯的错误或我应该做的任何更改？错误是：

bstnode'＆lt;'高尔夫球手'>'不能转换为binarysearchtree'＆lt;'golfer'>'。

public int countLess (BinarySearchTree <Golfer> tree, int value) {
BSTNode<Golfer> node = tree.node;
if (node == null) 
return 0;
int left = countLess(node.getLeft(), value);
int right  = countRight(node.getRight(), value);
return (node.getInfo() > maxValue ? 1:0) + countLeft + countRight;
}

Answer 1

我认为应该是这样的东西，因为我猜node.getLeft()实际上给了您一个节点，而不是完整的左子树。

public int countLess (BSTNode <Golfer> node, int value) {
    if (node == null) 
         return 0;
    int left = countLess(node.getLeft(), value);
    int right  = countLess(node.getRight(), value);
    return (node.getInfo() > maxValue ? 1:0) + left + right;
}

希望这能解决您的问题。如果您可以共享BinarySearchTree和BstNode类实现的实现，我可以提供更正确的解决方案。

Answer 2

我认为您应该对BST进行术语遍历。 BST的内存遍历始终为您以升序顺序为您提供元素。只需在执行术语遍历时保留一个count变量（并继续为每个访问的节点递增）即可

您的count变量中的最终值将是答案。

bst：二进制搜索树