计算 BST 中小于 X 的节点数

Question

我有一个代码给了我这些问题。关于我所犯的错误，或者我应该做出的任何改变，你能给我一些提示或指导吗？错误是：

BSTNode'<'Golfer'>'无法转换为 BinarySearchTree'<'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() 实际上给你 BST 中的一个节点而不是完整的左子树。

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 变量（并为每个访问的节点不断增加它），一旦任何节点的值变得大于 X，就 'break'.

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

BST：二叉搜索树

计算 BST 中小于 X 的节点数

Counting number of nodes less than X in BST

java

binary-tree