0

我已经编写了一种算法，用于在 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) {}
};
4

2 回答 2

2

仅靠自身无法有效地检索二叉搜索树中的第 n 个最小元素。但是，如果您在每个节点中保留一个整数，表示其整个子树中的节点数，这确实成为可能。从我的通用 AVL 树实现：

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]的左右子节点， 是 的整个子树中的节点数。nodenode->countnode

假设树是平衡的，上述算法具有 O(logn) 时间复杂度。此外，如果您保留这些计数，则可以进行另一个操作 - 给定一个指向节点的指针，可以有效地确定其索引（与您要求的相反）。在我链接的代码中，此操作称为BAVL_IndexOf().

请注意，节点计数需要随着树的变化而更新；这可以在时间复杂度没有（渐近）变化的情况下完成。

于 2012-04-28T12:05:51.747 回答
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在正确的位置进行减量，更改也不会在调用链中向上传播。您需要通过引用传递参数（注意函数签名中的&after int），因此更改是在原始值上进行的，而不是在它的副本上

.

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

我尚未测试建议的更改，但它们应该使您朝着正确的方向前进

于 2012-04-28T11:54:10.377 回答