BSTree 🌳

iterator.hpp

#include <node.hpp>

namespace BSTree {

    template<typename T>
    class iterator;

    template <typename T>
    class pre_iterator;

    template <typename T>
    class post_iterator;

    template<typename T>
    class iterator {

        using pointer = T *;
        using reference = T &;
        using value_type = T;

    public:
        iterator(const iterator &);

        ~iterator();

        iterator& operator=(const iterator &);

        virtual iterator& operator++();

        virtual reference operator*() const;

        virtual iterator operator++(int);

        value_type operator*() const;

        pointer operator->() const;

        reference operator*() const;

        iterator operator++(int);

        friend bool operator==(const iterator&, const iterator&);

        friend bool operator!=(const iterator&, const iterator&);

        friend void swap(iterator& lhs, iterator& rhs);

    private:
        Node* ptr;
    };

    template <typename T>
    class pre_iterator : iterator<T> {
    protected:
        pre_iterator();
        pre_iterator(Node* ptr);
    // ...
    };

    template <typename T>
    class post_iterator : iterator<T> {
    protected:
        post_iterator();
        post_iterator(Node* ptr);
    // ...
    };
}

main.cpp

int main() {
  
    using BSTree::Tree;
    Tree<int> tree = {5, 3, 4, 2, 7, 9, 6, 8};

    auto it = tree.begin();
    auto end = tree.end();

    for (; it != end; ++it ) {
        std::cout << *it << ' ';
    }
  
    std::cout << std::endl;
  
    auto rit = tree.rbegin();
    auto rend = tree.rend();
    for(; rit != rend; ++rit) {
      std::cout << *it << ' ';
    }
    std::cout << std::endl;
}

node.hpp

namespace BSTree {
    template <typename T>
    struct Node {
        T data;
        Node * left;
        Node * right;
        Node * parent;
    };
}

tree.hpp

#include <hode.hpp>
#include <iterator.hpp>

namespace BSTree {

    template <typename T>
    class Tree {
    public:
        using iterator = pre_order::iterator;
        using reverse_iterator = post_order::iterator;

        Tree(std::initializer_list<T>);

        auto push_back(const T&) -> void;

        auto begin() -> iterator;
        auto end() -> iterator;

        auto rbegin() -> reverse_iterator;
        auto rend() -> reverse_iterator;

    private:
        Node<T>* root;
    };
}