Реализация итератора для обхода дерева предварительного заказа - PullRequest
Новая
       17

Реализация итератора для обхода дерева предварительного заказа

0 голосов
/ 25 октября 2019

Итак, для этой домашней задачи мы должны реализовать итератор для двоичного дерева, который перебирает только положительные (больше 0) значения в дереве, используя предварительный порядок обхода справа налево. Обход должен сначала посетить текущий узел, затем правое поддерево, а затем левое (определение предзаказа).

Они дали нам реализацию для оператора! =, Начало () и конец (), и мы должны построить конструктор, оператор ++ и оператор * (вызов оператора * на конце итератора должен вернутьзначение по умолчанию типа T)

Мы также рекомендуем использовать std :: stack, std :: queue и корневую ссылку C ++ для решения этой проблемы.

То, что я изначально думал о том, чтобы иметь стек / очередь целых в конструкторе итератора, и проверить, больше ли значение, в котором вы находитесь, больше нуля;если это так, вы можете добавить это значение в стек / очередь и затем двигаться дальше. Иначе, вы просто продолжаете итерацию вперед (начиная с текущего узла, конечно, а затем следуя правилам обхода предзаказа).

Полагаю, мне следует начать с конструктора. Как вы думаете, метод, о котором я говорил выше, работает? Или эта функциональность должна быть для оператора ++? У меня была еще одна идея - создать объект Iterator в конструкторе ... и, возможно, использовать его в операторе ++? Затем я мог бы начать настройку реализации, о которой я упоминал ранее (перебирая только положительные значения).

Возможно, я тоже просто не понимаю итераторов и буду признателен за любые рекомендации.

Они также будут проводить тестирование только с данными 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);
}
...