为迭代树遍历实现迭代器

Question

因此，对于我遇到的这个家庭作业问题，我们必须为二叉树实现一个迭代器，该二叉树仅使用从右到左的预遍历遍历树中的正值（大于0）。遍历需要首先访问当前节点，然后是右子树，然后是左（预排序的定义）。

他们为我们提供了operator！=，begin（）和end（）的实现，我们必须构建构造函数，operator ++和operator *（在最终迭代器上调用operator *应该返回类型的默认值T）

我们也鼓励使用std :: stack，std :: queue和根C ++引用来解决此问题。

我最初想到的是在迭代器构造函数中具有int堆栈/队列，并检查您当前所处的值是否大于零；如果是这样，您可以将该值添加到堆栈/队列中，然后继续。否则，您只需继续进行迭代（当然，从当前节点开始，然后遵循预遍历的规则）。

我想我应该从构造函数开始。您认为我上面提到的方法行得通吗？还是该功能适用​​于操作员++？我的另一个想法是在构造函数中创建一个Iterator对象……并可能在operator ++中使用它？然后，我可以开始设置前面提到的实现（仅对正值进行迭代）。

我可能还不太了解迭代器，也希望对其中的任何指导感到满意。

即使类是模板，他们也将仅使用int数据进行测试。

非常感谢任何建议。

谢谢您的时间！

#include <iterator>
#include <stack>
#include <queue>
#include <iterator>

template <class T>
class Tree {
public:
    class Node {
        public:
            T data_;

            Node *left_;

            Node *right_;

            // Constructors
            Node(T data) : data_(data), left_(NULL), right_(NULL) {};
            Node(T data, Node *left, Node *right) : data_(data), left_(left), right_(right) {};
    };

    class Iterator : std::iterator<std::forward_iterator_tag, T> {
        private:
            Node *curr_;
            // TODO: your code here

        public:
            Iterator(Node *root);

            /**
            Progresses the iterator one step.
            **/
            Iterator & operator++();

            /**
            Accesses the data in the Iterator's current position.
            **/
            T operator*() const;

            /**
            Compares two iterators.
            **/
            bool operator!=(const Iterator &other);
    };

    /**
    Constructs an empty Tree.
    **/
    Tree() : root_(NULL) {};

    /**
    Destroys the Tree's associated dynamic memory as necessary.
    **/
    ~Tree() {};

    /**
    Returns a begin iterator that can be used to traverse the even data values in this tree.
    **/
    Iterator begin();

    /**
    Returns an end iterator for this tree.
    **/
    Iterator end();


    Node *getRoot() { return root_; }
    void setRoot(Node *root) { root_ = root; }

private:
    /**
    The root node of the Tree, or NULL if the Tree is empty.
    **/
    Node *root_;
};

================================================ =======================

#include "tree.h"

template <class T>
Tree<T>::Iterator::Iterator(Tree::Node *root) : curr_(root) {
    // TODO: your code here
}

template <class T>
typename Tree<T>::Iterator & Tree<T>::Iterator::operator++() {
    // TODO: your code here

return *this;
}

template <class T>
T Tree<T>::Iterator::operator*() const {
    // TODO: your code here
    return T(); // remove this line
}



/*******************
 ** Given code **
 *******************/
template <class T>
bool Tree<T>::Iterator::operator!=(const Tree<T>::Iterator &other) {
return !(curr_ == other.curr_);
}

template <class T>
typename Tree<T>::Iterator Tree<T>::begin() {
    return Iterator(root_);
}

template <class T>
typename Tree<T>::Iterator Tree<T>::end() {
    return Iterator(NULL);
}

Answer 1

你好，cs225同学，每当你参加考试时，祝你好运！