查找二进制搜索树中的第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()。

请注意，在更改树时需要更新节点计数;这可以在时间复杂性没有（渐近）改变的情况下完成。