查找二進制搜索樹中的第n個最小元素

Question

我已經編寫了一個算法來查找BST中的第n個最小元素，但它返回根節點而不是第n個最小元素。因此，如果您按順序輸入節點7 4 3 13 21 15，則在調用find（root，0）之後，該算法將返回值爲7而不是3的節點，並且對於調用find（root，1），將返回13而不是4。想法？

Binode* Tree::find(Binode* bn, int n) const 
{ 
    if(bn != NULL) 
    { 

    find(bn->l, n); 
    if(n-- == 0) 
     return bn;  
    find(bn->r, n); 

    } 
    else 
     return NULL; 
} 

和Binode的定義

class Binode 
{ 
public: 
    int n; 
    Binode* l, *r; 
    Binode(int x) : n(x), l(NULL), r(NULL) {} 
}; 

Answer 1

有你的代碼的幾個問題：

1）find()返回一個值（正確的節點，假設功能發揮預期） ，但是您不會將該值傳播到呼叫鏈，因此頂級呼叫不知道（可能）找到的元素

。

Binode* elem = NULL; 
elem = find(bn->l, n); 
if (elem) return elem; 
if(n-- == 0) 
    return bn;  
elem = find(bn->r, n); 
return elem; // here we don't need to test: we need to return regardless of the result 

2），即使你做的n在正確的地方遞減，變化不向上調用鏈傳播。你需要通過引用傳遞參數（請注意函數簽名int後&），這樣的變化是由原始價值，而不是在它的

副本。

Binode* Tree::find(Binode* bn, int& n) const 

我沒有測試過建議的更改，但他們應該把你在正確的方向進步

Answer 2

這是不可能通過自身有效地檢索二叉搜索樹的第n個最小元素。但是，如果您在每個節點中保留一個指示其整個子樹中的節點數的整數，則這成爲可能。從my generic AVL tree implementation：

static BAVLNode * BAVL_GetAt (const BAVL *o, uint64_t index) 
{ 
    if (index >= BAVL_Count(o)) { 
     return NULL; 
    } 

    BAVLNode *c = o->root; 

    while (1) { 
     ASSERT(c) 
     ASSERT(index < c->count) 

     uint64_t left_count = (c->link[0] ? c->link[0]->count : 0); 

     if (index == left_count) { 
      return c; 
     } 

     if (index < left_count) { 
      c = c->link[0]; 
     } else { 
      c = c->link[1]; 
      index -= left_count + 1; 
     } 
    } 
} 

在上面的代碼，node->link[0]和node->link[1]是node左右的孩子，node->count是在node的整個子樹的節點數量。

上述算法具有O（logn）時間複雜度，假設樹是平衡的。另外，如果你保留這些計數，另一個操作變得可能 - 給定一個指向節點的指針，可以有效地確定它的索引（與你要求的相反）。在我鏈接的代碼中，此操作稱爲BAVL_IndexOf()。

請注意，在更改樹時需要更新節點計數;這可以在時間複雜性沒有（漸近）改變的情況下完成。