以最佳方式在二进制搜索树中找到第k个最小元素

我需要在二进制搜索树中找到第k个最小的元素,而无需使用任何静态/全局变量。如何有效实现?我想到的解决方案是在O(n)中进行操作,这是最糟糕的情况,因为我计划对整个树进行有序遍历。但在内心深处,我觉得我没有在这里使用BST属性。我的假设解决方案正确还是有更好的解决方案?



慕的地6264312
浏览 610回答 3
3回答

慕码人8056858

一个更简单的解决方案是进行有序遍历并跟踪当前要打印的元素(不打印)。当我们达到k时,打印元素并跳过其余的树遍历。void findK(Node* p, int* k) {&nbsp; if(!p || k < 0) return;&nbsp; findK(p->left, k);&nbsp; --k;&nbsp; if(k == 0) {&nbsp;&nbsp; &nbsp; print p->data;&nbsp; &nbsp; return;&nbsp;&nbsp;&nbsp; }&nbsp;&nbsp; findK(p->right, k);&nbsp;}

江户川乱折腾

public int ReturnKthSmallestElement1(int k)&nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; Node node = Root;&nbsp; &nbsp; &nbsp; &nbsp; int count = k;&nbsp; &nbsp; &nbsp; &nbsp; int sizeOfLeftSubtree = 0;&nbsp; &nbsp; &nbsp; &nbsp; while(node != null)&nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; sizeOfLeftSubtree = node.SizeOfLeftSubtree();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (sizeOfLeftSubtree + 1 == count)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return node.Value;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (sizeOfLeftSubtree < count)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.Right;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count -= sizeOfLeftSubtree+1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; node = node.Left;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return -1;&nbsp; &nbsp; }这是我基于上述算法在C#中的实现,只是以为我会发布它,以便人们可以更好地理解它对我有用谢谢你IVlad
打开App,查看更多内容
随时随地看视频慕课网APP