16

C++ STL 类 std::map 使用二叉树实现 O(log(n)) 查找。但是对于树,迭代器如何工作并不是很明显。++ 运算符在树结构中的实际含义是什么?尽管“下一个元素”的概念在数组中有明显的实现,但对我来说,在树中并不那么明显。如何实现树迭代器?

4

4 回答 4

8

对于中序遍历(可能也适用于其他人),如果您的节点中有父指针,则可以进行非递归遍历。应该可以只在迭代器中存储两个指针:您需要指示您在哪里,并且您可能(我现在不做研究)需要类似“previous”指针的东西,这样您就可以弄清楚您当前的移动方向(即我是否需要进入左子树,或者我是否刚从它回来)。

如果我们刚刚进入节点,“ Previous”可能类似于“parent”;“left”如果我们从左子树返回,“right”如果我们从右子树返回,“self”如果我们返回的最后一个节点是我们自己的。

于 2012-09-04T08:42:45.897 回答
3

我想添加我的两美分作为评论,但由于我不能,我将不得不添加一个答案。我一直在谷歌上搜索并且很沮丧,因为我找到的所有答案,这些除外,都假设一个堆栈或其他一些可变大小的数据结构。我确实找到了一些代码。它表明它可以在没有堆栈的情况下完成,但我发现它很难遵循,因此决定从第一原则解决这个问题。

首先要注意的是该算法是“左贪心”的。因此,当我们从根开始时,我们会立即尽可能向左走,因为最左边的节点是我们首先需要的节点。这意味着我们永远不需要考虑左子树。它已经被迭代了。

迭代的顺序是左子树、节点、右子树。因此,如果我们位于给定节点,我们知道它的左子树和节点本身已经被访问过,我们接下来应该访问右子树,如果有的话,尽可能向左走。

否则,我们必须上树。如果我们要从一个左孩子到它的父母,那么接下来是父母。(之后我们将访问它的右子树,如前所述。)

最后一种情况是当我们从一个正确的孩子变成它的父母时。父母已经被拜访过,所以我们必须再次上去。事实上,我们必须继续向上直到我们到达根或树,或者发现自己从左孩子移动到父母。正如我们已经看到的,在这种情况下,父节点是下一个节点。(根可能由一个空指针表示,如在我的代码中,或一些特殊的哨兵节点。)

下面的代码可以很容易地适应 STL 风格的迭代器

// Go as far left from this node as you can.
// i.e. find the minimum node in this subtree
Node* Leftmost(Node* node)
{
    if (node == nullptr)
        return nullptr;
    while (node->left != nullptr)
        node = node->left;
    return node;
}

// Start iterating from a root node
Node* First(Node* root)
{
    return Leftmost(root);
}

// The iteration is current at node.  Return the next node
// in value order.
Node* Next(Node* node)
{
    // Make sure that the caller hasn't failed to stop.
    assert(node != nullptr);

    // If we have a right subtree we must iterate over it,
    // starting at its leftmost (minimal) node.

    if (node->right != nullptr)
        return Leftmost(node->right);
    
    // Otherwise we must go up the tree

    Node* parent = node->parent;
    if (parent == nullptr)
        return nullptr;

    // A node comes immediately after its left subtree

    if (node == parent->left)
        return parent;

    // This must be the right subtree!
    assert(node == parent->right);

    // In which case we need to go up again, looking for a node that is
    // its parent's left child.

    while (parent != nullptr && node != parent->left)
    {
        node = parent;
        parent = node->parent;
    }

    // We should be at a left child!
    assert(parent == nullptr || node == parent->left);

    // And, as we know, a node comes immediately after its left subtree

    return parent;
}
于 2020-07-09T11:29:34.173 回答
2

考虑地图中不小于当前元素但也不是当前元素的所有元素的集合。“下一个元素”是该组元素中小于该组中所有其他元素的元素。

为了使用地图,您必须有一个密钥。并且该键必须实现“小于”操作。这决定了映射的形成方式,以便查找、添加、删除、递增和递减操作是有效的。

通常,地图内部使用某种树。

于 2012-09-04T08:34:21.030 回答
0

stl_tree.h中映射迭代器运算符++ watch 的标准实现:

_Self&
operator++() _GLIBCXX_NOEXCEPT
{
_M_node = _Rb_tree_increment(_M_node);
return *this;
}

_Rb_tree_increment实现在这里讨论

于 2021-12-27T19:47:35.217 回答