C ++, Реализация специального итератора для двоичных деревьев (long)

Пожалуйста, будьте любезны - это мой первый вопрос. = P

В основном в качестве летнего проекта я просматривал список структур данных на странице википедии и пытался их реализовать. В прошлом семестре я прошел курс C ++ и нашел, что это очень весело, в качестве последнего проекта я реализовал биномиальную кучу - это тоже было очень весело. Может, я ботаник, но люблю структуры данных.

В общем, достаточно предыстории. Проект идет хорошо, я начинаю с Binary Trees. Чтобы пойти намного дальше, мне нужно создать итераторы для обхода деревьев. Я уже решил, что создам два типа итераторов для каждого метода обхода (обычный итератор и константный итератор), я просто не знаю, как это сделать. Я слышал о наследовании от материала итератора stl или даже об использовании Boosts iterator_facade (что кажется хорошим вариантом)

Я даже не пытался написать код итератора, так как не знаю, с чего начать, но я мой текущий код есть на github. Вы можете проверить это здесь .

Если вы против github, я вставляю соответствующие определения классов. Реализация этих функций на самом деле не поможет, но если они вам по какой-то причине понадобятся, дайте мне знать. Кроме того, класс узла имеет родительский указатель для целей итерации.

#ifndef __TREES_HXX
#define __TREES_HXX
#include   // For NULL
#include  // for std::max

// Node class definition. These nodes are to be used for any
// tree where the structure is
//    node
//     /\
// left  right
//  /\    /\
//
// etc., basically two children.
template 
class Node
{
  public:
    T data_;
    Node* left_;
    Node* right_;
    Node* parent_; // Needed for iterators

    explicit Node(T const&);
    Node(Node const&);
};

template 
class BinaryTree
{
  protected:
    typedef Node* node_t;
    size_t tree_size;

  public:
    typedef T value_type;

    explicit BinaryTree();
    explicit BinaryTree(T const&);
    ~BinaryTree();

    virtual node_t insert(node_t&, T) = 0;
    virtual T& lookup(node_t const&, T const&) const = 0;
    inline virtual size_t size() const;
    inline virtual size_t depth(node_t const&) const;
    inline bool empty() const;
    inline void clear(node_t);

    node_t root;
};

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

/* Implementation of our Binary Tree is in
 * this file. The node class is in Trees.hxx
 * because it's intended to be a general class.
 */

 #ifndef __BINARY_TREE_HXX
 #define __BINARY_TREE_HXX

 #include "Trees.hxx"


 template 
 class BiTree : public BinaryTree
 {
   private:
     typedef typename BinaryTree::node_t node_t;

   public:
     typedef typename BinaryTree::value_type value_type;

     BiTree() : BinaryTree()
     {
     }

     BiTree(T const& data) : BinaryTree(data)
     {
     }

     node_t insert(node_t&, T);
     T& lookup(node_t const&, T const&) const; // Note: This should return an iterator to the node where the stuff is found
 };

Я думаю, что это все - спасибо за ваше время! Если вам нужна дополнительная информация, дайте мне знать.