/**
* Treat the bst as a sorted list in descending order and find the element
* in position k.
*
* Time complexity BigO ( n^2 )
*
* 2n + sum( 1 * n/2 + 2 * n/4 + ... ( 2^n-1) * n/n ) =
* 2n + sigma a=1 to n ( (2^(a-1)) * n / 2^a ) = 2n + n(n-1)/4
*
* @param t The root of the binary search tree.
* @param k The position of the element to find.
* @return The value of the element at position k.
*/
public static int kElement2( Node t, int k ) {
int treeSize = sizeOfTree( t );
return kElement2( t, k, treeSize, 0 ).intValue();
}
/**
* Find the value at position k in the bst by doing an in-order traversal
* of the tree and mapping the ascending order index to the descending order
* index.
*
*
* @param t Root of the bst to search in.
* @param k Index of the element being searched for.
* @param treeSize Size of the entire bst.
* @param count The number of node already visited.
* @return Either the value of the kth node, or Double.POSITIVE_INFINITY if
* not found in this sub-tree.
*/
private static Double kElement2( Node t, int k, int treeSize, int count ) {
// Double.POSITIVE_INFINITY is a marker value indicating that the kth
// element wasn't found in this sub-tree.
if ( t == null )
return Double.POSITIVE_INFINITY;
Double kea = kElement2( t.getLeftSon(), k, treeSize, count );
if ( kea != Double.POSITIVE_INFINITY )
return kea;
// The index of the current node.
count += 1 + sizeOfTree( t.getLeftSon() );
// Given any index from the ascending in order traversal of the bst,
// treeSize + 1 - index gives the
// corresponding index in the descending order list.
if ( ( treeSize + 1 - count ) == k )
return (double)t.getNumber();
return kElement2( t.getRightSon(), k, treeSize, count );
}
-1
签名：
Node * find(Node* tree, int *n, int k);
呼叫：
*n = 0;
kthNode = find(root, n, k);
定义：
Node * find ( Node * tree, int *n, int k)
{
Node *temp = NULL;
if (tree->left && *n<k)
temp = find(tree->left, n, k);
*n++;
if(*n==k)
temp = root;
if (tree->right && *n<k)
temp = find(tree->right, n, k);
return temp;
}
0
那么这是我的2美分......
int numBSTnodes(const Node* pNode){
if(pNode == NULL) return 0;
return (numBSTnodes(pNode->left)+numBSTnodes(pNode->right)+1);
}
//This function will find Kth smallest element
Node* findKthSmallestBSTelement(Node* root, int k){
Node* pTrav = root;
while(k > 0){
int numNodes = numBSTnodes(pTrav->left);
if(numNodes >= k){
pTrav = pTrav->left;
}
else{
//subtract left tree nodes and root count from 'k'
k -= (numBSTnodes(pTrav->left) + 1);
if(k == 0) return pTrav;
pTrav = pTrav->right;
}
return NULL;
}
0
这就是我，它的工作原理 . 它将在o（log n）中运行
public static int FindkThSmallestElemet(Node root, int k)
{
int count = 0;
Node current = root;
while (current != null)
{
count++;
current = current.left;
}
current = root;
while (current != null)
{
if (count == k)
return current.data;
else
{
current = current.left;
count--;
}
}
return -1;
} // end of function FindkThSmallestElemet
12
好吧，我们可以简单地使用顺序遍历并将访问过的元素推送到堆栈上 . 流行k次，得到答案 .
我们也可以在k元素后停止
159
完整BST案例的解决方案： -
Node kSmallest(Node root, int k) {
int i = root.size(); // 2^height - 1, single node is height = 1;
Node result = root;
while (i - 1 > k) {
i = (i-1)/2; // size of left subtree
if (k < i) {
result = result.left;
} else {
result = result.right;
k -= i;
}
}
return i-1==k ? result: null;
}
使用 order statistics tree 的IVlad解决方案是最有效的 . 但是如果你不能使用 order statistics tree 并且坚持使用普通的旧BST，那么最好的方法是进行Inorder Traversal（如prasadvk所指出的） . 但是如果你想要返回第k个最小元素并且不仅仅是打印出值，那么他的解决方案是不够的 . 此外，由于他的解决方案是递归的，因此存在堆栈溢出的危险 . 因此，我编写了一个java解决方案，它返回第k个最小节点并使用堆栈来执行In Order Traversal . 运行时间是O（n），而空间复杂度是O（h），其中h是树的最大高度 .
// The 0th element is defined to be the smallest element in the tree.
public Node find_kth_element(Node root , int k) {
if (root == null || k < 0) return null;
Deque<Node> stack = new ArrayDeque<Node>();
stack.push(root);
while (!stack.isEmpty()) {
Node curr = stack.peek();
if (curr.left != null) {
stack.push(curr.left);
continue;
}
if (k == 0) return curr;
stack.pop();
--k;
if (curr.right != null) {
stack.push(curr.right);
}
}
return null;
}
10
最好的方法已经存在 . 但我想为此添加一个简单的代码
int kthsmallest(treenode *q,int k){
int n = size(q->left) + 1;
if(n==k){
return q->val;
}
if(n > k){
return kthsmallest(q->left,k);
}
if(n < k){
return kthsmallest(q->right,k - n);
}
public class KthSmallestElementWithAux {
public int kthsmallest(TreeNode a, int k) {
TreeNode ans = kthsmallestRec(a, k).node;
if (ans != null) {
return ans.val;
} else {
return -1;
}
}
private Result kthsmallestRec(TreeNode a, int k) {
//Leaf node, do nothing and return
if (a == null) {
return new Result(k, null);
}
//Search left first
Result leftSearch = kthsmallestRec(a.left, k);
//We are done, no need to check right.
if (leftSearch.node != null) {
return leftSearch;
}
//Consider number of nodes found to the left
k = leftSearch.k;
//Check if current root is the solution before going right
k--;
if (k == 0) {
return new Result(k - 1, a);
}
//Check right
Result rightBalanced = kthsmallestRec(a.right, k);
//Consider all nodes found to the right
k = rightBalanced.k;
if (rightBalanced.node != null) {
return rightBalanced;
}
//No node found, recursion will continue at the higher level
return new Result(k, null);
}
private class Result {
private final int k;
private final TreeNode node;
Result(int max, TreeNode node) {
this.k = max;
this.node = node;
}
}
}
1
public int printInorder(Node node, int k)
{
if (node == null || k <= 0) //Stop traversing once you found the k-th smallest element
return k;
/* first recur on left child */
k = printInorder(node.left, k);
k--;
if(k == 0) {
System.out.print(node.key);
}
/* now recur on right child */
return printInorder(node.right, k);
}
30 回答
这里只是一个概念的概述：
在BST中，节点
T的左子树仅包含小于T中存储的值的元素 . 如果k小于左子树中的元素数，则kth最小元素必须属于左子树 . 否则，如果k较大，则k最小元素位于右子树中 .我们可以扩充BST以使其中的每个节点存储其左子树中的元素数量（假设给定节点的左子树包括该节点） . 通过这条信息，通过反复询问左子树中的元素数量来遍历树是很简单的，以决定是否递归到左子树或右子树 .
现在，假设我们在节点T：
如果是 k == num_elements(left subtree of T) ，那么我们要找的答案就是节点
T中的值 .如果 k > num_elements(left subtree of T) ，那么显然我们可以忽略左子树，因为那些元素也将小于
k最小 . 因此，我们将问题简化为找到右子树的k - num_elements(left subtree of T)最小元素 .如果 k < num_elements(left subtree of T) ，则
k最小的是左子树中的某个位置，因此我们将问题减少为在左子树中找到k最小的元素 .复杂性分析：
这需要
O(depth of node)时间，在 balancer BST的最坏情况下为O(log n)，对于随机BST平均为O(log n).BST需要
O(n)存储，并且需要另一个O(n)来存储有关元素数量的信息 . 所有BST操作都需要O(depth of node)时间，并且需要O(depth of node)额外的时间来维护用于插入，删除或轮换节点的"number of elements"信息 . 因此，存储关于左子树中的元素数量的信息保持了BST的空间和时间复杂度 .一个更简单的解决方案是进行顺序遍历并跟踪当前要打印的元素（不打印它） . 当我们到达k时，打印元素并跳过树遍历的其余部分 .
这是我在C＃中实现的基于上面的算法只是想我发布它所以人们可以理解它对我有用
谢谢你IVlad
更简单的解决方案是进行顺序遍历并使用计数器k跟踪当前要打印的元素 . 当我们到达k时，打印元素 . 运行时为O（n） . 记住函数返回类型不能为void，它必须在每次递归调用后返回其更新的k值 . 对此更好的解决方案是增强的BST，在每个节点处具有排序的位置值 .
//添加没有递归的java版本
您可以使用迭代的inorder遍历：http://en.wikipedia.org/wiki/Tree_traversal#Iterative_Traversal，在将一个节点弹出堆栈后，可以简单地检查第k个元素 .
只给出一个简单的二叉搜索树，你可以做的就是从最小的开始，然后向上遍历以找到正确的节点 .
如果您经常这样做，可以向每个节点添加一个属性，表示其左侧子树中有多少个节点 . 使用它，您可以将树直接下降到正确的节点 .
使用计数器递归有序行走
这个想法类似于@prasadvk解决方案，但它有一些缺点（见下面的注释），所以我将其作为一个单独的答案发布 .
注释（和@ prasadvk解决方案的不同之处）：
在 three 位置需要进行
if( counter == k )测试：（a）在左子树之后，（b）在根之后，以及（c）在右子树之后 . 这是 ensure that kth element is detected for all locations ，即不管它所在的子树如何 .确保 only the result element is printed 需要
if( result == -1 )测试，否则将打印从第k个最小到根的所有元素 .对于 not balancer 搜索树，需要O（n） .
对于 balanced 搜索树，在最坏的情况下需要O（k log n）但在 Amortized 意义上只是O（k） .
拥有并管理每个节点的额外整数：子树的大小给出O（log n）时间复杂度 . 这种 balancer 搜索树通常称为RankTree .
通常，有解决方案（不基于树） .
问候 .
这很有效：status：是否保存元素的数组 . k：是要找到的第k个元素 . count：跟踪树遍历期间遍历的节点数 .
虽然这绝对不是问题的最佳解决方案，但我认为有些人可能会感兴趣的是另一个潜在的解决方案：
签名：
呼叫：
定义：
那么这是我的2美分......
这就是我，它的工作原理 . 它将在o（log n）中运行
好吧，我们可以简单地使用顺序遍历并将访问过的元素推送到堆栈上 . 流行k次，得到答案 .
我们也可以在k元素后停止
完整BST案例的解决方案： -
Linux内核具有出色的增强红黑树数据结构，支持linux / lib / rbtree.c中O（log n）中基于秩的操作 .
一个非常粗糙的Java端口也可以在http://code.google.com/p/refolding/source/browse/trunk/core/src/main/java/it/unibo/refolding/alg/RbTree.java找到，还有RbRoot.java和RbNode.java . 第n个元素可以通过调用RbNode.nth（RbNode节点，int n），传入树的根来获得 .
这是 C# 中的简洁版本 returns 是第k个最小元素，但需要将k in作为ref参数传递（它与@prasadvk的方法相同）：
找到 the 最小节点是O（log n），然后O（k）遍历到第k个节点，所以它是O（k log n） .
http://www.geeksforgeeks.org/archives/10379
这是这个问题的确切答案： -
1.在O（n）时间内使用inorder遍历2.在k log n时间内使用增广树
我找不到更好的算法 . 所以决定写一个:)如果这是错的，请纠正我 .
}
这是java代码，
max(Node root, int k) - 找到第k个最大的
min(Node root, int k) - 找到最小的kth
这也行得通 . 只需在树中使用maxNode调用该函数
def k_largest（self，node，k）：如果k <0：返回None
如果k == 0：返回节点else：k - = 1返回self.k_largest（self.predecessor（node），k）
我认为这比接受的答案更好，因为它不需要修改原始树节点来存储它的子节点数 .
我们只需要使用有序遍历从左到右计算最小节点，一旦计数等于K就停止搜索 .
使用
order statistics tree的IVlad解决方案是最有效的 . 但是如果你不能使用order statistics tree并且坚持使用普通的旧BST，那么最好的方法是进行Inorder Traversal（如prasadvk所指出的） . 但是如果你想要返回第k个最小元素并且不仅仅是打印出值，那么他的解决方案是不够的 . 此外，由于他的解决方案是递归的，因此存在堆栈溢出的危险 . 因此，我编写了一个java解决方案，它返回第k个最小节点并使用堆栈来执行In Order Traversal . 运行时间是O（n），而空间复杂度是O（h），其中h是树的最大高度 .最好的方法已经存在 . 但我想为此添加一个简单的代码
}
使用辅助Result类来跟踪是否找到节点和当前k .
这个java递归算法一旦找到第k个最小元素就停止递归 .
我写了一个简洁的函数来计算第k个最小元素 . 我使用有序遍历并在它到达第k个最小元素时停止 .