java - 如何在基于 BST 的数组中找到第 k 个最小元素？ ( java )

Question

我被赋予了这个任务，但这对我来说似乎非常非常困难。

public class BinarySearchTree<A extends Comparable<? super A>> {

public int[] size
public Object[] list

public A get(int x) {
}

}

    7
   / \
  5   10
 / \  / \
3   6 9 11

The above tree would be stored as [7, 5, 10, 3, 6, 9, 11] in the list array.

所以我有这个结构。我必须使用子树的大小找到第 x 个最小的元素。我不知道如何首先找到子树的大小，然后使用该信息来找到第 x 个值。

有人有办法吗？我已经尝试了好几天，但即使是网络也没有给我太多信息。

感谢任何帮助，谢谢。

Answer 1

请记住 BST 是排序的。底层数组不是，但如果您以某种方式遍历树(留给您找出)，您将按升序获得每个元素。如果您设法找出如何做到这一点，则只需查看直到到达第 n 个元素。

我想您可以使用子树的大小来计算，但这听起来不必要地复杂(也就是说，代码可读性较差，数学不太难)并且在现实生活中不切实际。毕竟，BST 的存在是有原因的。

可以用尺寸来做。想象一下，你从根开始。设 L 为左子树的大小，R 为右子树的大小。你的节点总数将是 L + R + 1。你的根将有索引 L，如果 x 大于 L，你知道你会在右子树中找到你的元素，如果它更小，然后在你的左边寻找。 (假设 x 是空索引的)。这是一般模式，您可能可以自己找出其余的模式。