Использование итератора для прохождения порядка BST справа налево

Question

Так что я понятия не имею, как создать или использовать итератор для этой задачи:

Реализовать итератор для двоичного дерева, который выполняет итерацию только по ненулевым значениям в дереве, используя правый порядоклевый обход. Напомним, что сначала он пересекает правое поддерево, затем текущий узел, а затем левое поддерево.

Хотя класс Tree является шаблонным и может содержать данные любого типа, мы будем тестировать только с указателями.

Выполните следующие функции в tree.cpp:

Tree<T>::Iterator constructor
Tree<T>::Iterator::operator++
Tree<T>::Iterator::operator* (note: calling operator* on an end iterator should return a default value of type T)
The following Iterator functions are implemented for you:

Tree<T>::Iterator::operator!=
Tree<T>::begin()
Tree<T>::end()
You may add private members to the Iterator class in tree.h if desired.

Частичный кредит доступен для рабочего итератора, который включает все значения в дереве (полный кредит требует только значения, отличные от NULL).

Потенциально полезные ссылки. Ссылка на очередь ссылок на стек. Справочный корень Компиляция и тестирование Предоставляются Makefile и основная функция с базовым использованием Iterator. Чтобы скомпилировать и протестировать, выполните:

make && ./main

tree.h

#ifndef TREE_H
#define TREE_H

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

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 non-NULL 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.cpp"

#endif

tree.cpp

#ifndef TREE_CPP
#define TREE_CPP

#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
}



/*******************
 ** PROVIDED 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);
}

#endif

Makefile

EXENAME = main

CXX = clang++
CXXFLAGS = -std=c++11 -g -O0 -Wall -Wextra

all : $(EXENAME)

$(EXENAME): main.cpp tree.o
    $(CXX) $(CXXFLAGS) main.cpp tree.o -o $(EXENAME)

bst.o: tree.h tree.cpp
    $(CXX) $(CXXFLAGS) -c tree.cpp

.PHONY: clean
clean:
    rm -f *.o $(EXENAME)

main.cpp

#include <iostream>
#include <algorithm>
#include "tree.h"

template <class T>
void print(std::vector<T> v) {
    std::cout << "<";
    for (size_t i = 0; i < v.size(); i++) {
        std::cout << v[i] << (i != v.size()-1 ? ", " : "");
    }
    std::cout << ">" << std::endl;
}

int main() {
    Tree<int*> t;
    int *vals = new int[6];
    t.setRoot(
        new Tree<int*>::Node(&vals[0],
            new Tree<int*>::Node(&vals[1],
                NULL,
                new Tree<int*>::Node(NULL)),
            new Tree<int*>::Node(&vals[2],
                new Tree<int*>::Node(&vals[3]),
                new Tree<int*>::Node(NULL,
                    new Tree<int*>::Node(&vals[4]),
                    new Tree<int*>::Node(&vals[5])))));

    std::vector<int*> expected = { &vals[5], &vals[4], &vals[2], &vals[3], &vals[0], &vals[1] };
    std::vector<int*> actual;
    for ( int *i : t ) actual.push_back(i);
    std::cout << "Expected: "; print(expected);
    std::cout << "Actual  : "; print(actual);
    delete[] vals;
}

Я знаю шаблон обхода, но ничего не знаю о том, как использовать итератор или структуру данных для использования. Объяснение кода и ответа было бы очень полезно, так как я действительно хочу понять теорию, стоящую за этим