如何在基于数组的BST中找到第k个最小的元素？（Java）
我被认为是一项任务，但这对我来说似乎非常困难。
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个值。
有人有办法吗？我已经尝试了好几天，但即使是网络也没有给我太多信息。
任何帮助表示赞赏，谢谢。
展开
收起
1
条回答
写回答
写回答
-
#include请记住，BST已排序。底层数组不是，但是如果您以某种方式遍历树（留给您查找），您将按升序获得每个元素。如果您确实设法做到这一点，则只需要查看直到到达第n个元素即可。
我想您可以使用子树的大小来弄清楚，但这听起来不必要地复杂（也就是说，代码的可读性较差，数学不太难）并且在现实生活中不切实际。毕竟，BST存在是有原因的。
可以处理尺寸。想象一下，您从根本开始。令L为左侧子树的大小，R为右侧子树的大小。您的总节点数将为L + R +1。您的根节点的索引为L，如果x大于L，您会知道您会在右侧子树中找到元素，如果较小，则向左看。（假设x为空索引）。这是一般模式，您可能可以自己解决其余的问题。
2019-12-04 16:57:08赞同 展开评论 打赏
版权声明：本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
相关问答
