尋找在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，因此當前節點必須是第四。

你明白了。