c++ - 从二叉搜索树中的 end() 迭代器递减迭代器

Question

在二叉搜索树中，end()成员函数应简单地返回 iterator(nullptr) ， 正确的？但是节点 nullptr不包含有关其 left 的信息, right , 和 parent数据。那么我们如何从 end() 递减一个迭代器呢？ ？以下是我目前所拥有的(在 iterator<T> 类中定义)。我的iterator<T>类有node<T>* ptr作为其唯一的数据成员，以及我的 node<T>类有成员 T value; node *left, *right, *parent; .

    iterator& operator--() {
//      if (!ptr) what to do???
        if (ptr->left)
            ptr = node<T>::max_node(ptr->left);
        else {
            node<T>* previous = ptr;
            ptr = ptr->parent;
            while (ptr && ptr->left == previous) {
                previous = ptr;
                ptr = ptr->parent;
            }
        }
        return *this;
    }

Answer 1

如果您希望您的迭代器是双向迭代器，您需要提供必要的信息以在 end() 返回的迭代器中找到树的最后一个节点。 .为了避免处理特殊情况只是为了减少 end()迭代器，你可以使用一个“ secret ”节点，它使用它的左指针指向树的根。这样end()迭代器只是一个指向这个 secret 节点的指针:使用这种方法，不需要对递增、递减或比较进行任何特殊处理。

由于通常不希望将节点值存储在根中，因此通常的实现将节点拆分为 NodeBase只持有导航所需的指针和 NodeValue派生自 NodeBase并添加节点的值。根使用 NodeBase成员和迭代器键入一个 NodeBase* : 导航只需要指针。由于只允许取消引用有效的迭代器 static_cast<NodeValue*>(n)可用于获取 NodeValue访问节点的值时。