在bst中第k個最小數字

Question

我有以下代碼用於在bst中查找第k個最小數字。

int kthsmallest(node* root, int* currentpos, int k){ 

    if(root->left != NULL){ 
      return kthsmallest(root->left, currentpos, k); 
    } 

    (*currentpos)++; 
    if(*currentpos == k){ 
      return root->n; 
    } 

    if(root->right != NULL){ 
      return kthsmallest(root->right, currentpos, k); 
    } 

} 

來電（假設我在BST 10號）：

int temp=0; 
    for(i=1; i<10; i++){ 
      temp=0; 
      printf("%d ", kthsmallest(root, &temp, i)); 
    } 

這工作得很好，直到它打印出來的前幾個葉節點。但是，在此之後它不會給任何其他節點正確的答案。我在這裏錯過了什麼？

Answer 1

爲了遍歷BST以排序的方式打印出BST。當您遍歷Inorder時，按列表中的元素，然後從頭開始返回列表的第k個元素。