在BST中查找第k个最小值

Question

这是我必须在二叉搜索树中找到第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个最小的节点.