一千萬個為什麽

搜索

在BST中查找第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個最小元素。

最佳答案

BST是排序的二叉樹,有序遍歷(左子樹,當前節點,右子樹)將給出排序的節點值。要查找第k個最小節點,只需使用計數器進行有序遍歷。計數器從0開始,每當遍歷一個節點時,將其增加1,當它到達k時,該節點是第k個最小的節點。

轉載註明原文: 在BST中查找第k個最小值