寻找在BST

Question

这里的第k个最小值是我的二叉搜索树，找到第k个最小值：

struct treeNode 
{ 
    int data; 
    struct treeNode *left, *right: 
}; 

int rank(stuct treeNode* ptr, int k) 
{ 
    if(node == NULL) 
    return root; 

    while(ptr->left != NULL) { 
    ptr = ptr->left; 
    return rank(ptr->left) 
    } 
} 

这显然是不正确的。如果没有提供解决方案，有人能指导我正确的方向，我该如何解决这个问题？我无法弄清楚如何找到BST中第k个最小的元素。

Answer 1

甲BST是一个排序二叉树中，在序遍历（左子树，当前节点，右子树）会给排序节点值。要找到第k个最小的节点，只需使用计数器按顺序遍历即可。计数器从0开始，每当遍历一个节点时，增加1，当它达到k时，节点是第k个最小的节点。

Answer 2

这应该工作：

int rank(struct treeNode* n,int k,int* chk) 
    { 
    if(!n) return -1; 
    int _chk = 0; 
    if(!chk) chk = &_chk; 

    int t = rank(n->left,k,chk); 
    if(t>=0) return t; 

    if(++*chk > k) return n->data; 

    int t = rank(n->right,k,chk); 
    if(t>=0) return t; 
    return -1; 
    } 

呼叫作为rank(root,k,0)

Answer 3

如果每个子树的大小，这可能是可行的，而无需将数据读入一个数组（或以其他方式穿越树）并数起来。如果您不保留尺寸信息，您需要辅助功能来计算尺寸。

的基本思路，弄清楚什么是当前节点的索引。如果它小于k，则需要搜索左侧子树。如果它大于k，则搜索右侧偏移从左侧算起的节点和当前的节点。请注意，这与通过常规BST进行搜索基本相同，除了这次我们正在通过索引而不是数据进行搜索。一些伪代码：

if size of left subtree is equal to k: 
    // the current node is kth 
    return data of current node 
else if size of left subtree is greater than k: 
    // the kth node is on the left 
    repeat on the left subtree 
else if size of left subtree is less than k: 
    // the kth node is on the right 
    reduce k by the size of the left subtree + 1 // need to find the (k')th node on the right subtree 
    repeat on the right subtree 

为了说明这一点，考虑这棵树与标记指数（甚至不担心数据，因为它并不重要搜索）：

 3 
    / \ 
    2  6 
    / /\ 
    0  4 7 
    \  \ 
    1  5 

假设我们想找到第二（k = 2）。
在3开始，左子树的大小是3
它大于ķ所以移到左子树。
左子树的大小是2
k是2也如此当前节点必须是第二。

假设我们想找到第4个（k = 4）。
从3开始，左子树的大小为3.
它小于l，因此将新k调整为0（k'= 4 - （3 + 1））并移至右子树。
在6开始，左子树的大小是2
它是大于k”（0），从而移动到左子树。
左子树的大小为0。
K”也为0，因此当前节点必须是第四。

你明白了。