Нужно реализовать простейший контейнер для бинарного дерева, определить функции begin(), end() и перегрузить для итератора операторы ++ и *. Для перемещения по элементам решил узлы дерева записывать в STL-list и уже по нему двигать итератор. Самый крайний левый элемент дерева считается началом контейнера, элемент за крайним правым - конец контейнера.
template <typename T>
class Node
{
private:
T data;
Node<T> *left, *right;
bool flag;
friend class Tree<T>;
public:
Node(): flag(false), left(NULL), right(NULL){}
~Node(){if(left){delete left; left = NULL;}
if(right){delete right; right = NULL;}}
};
template <typename T>
class Tree
{
private:
friend class Iterator;
Node<T>* head;
public:
class Iterator
{
private:
list<Node<T> > li;
typename std::list<Node<T> >::iterator li_it;
void build(Node<T>*);
public:
Iterator();
~Iterator();
Iterator(const Iterator&);
Iterator& operator ++ ();
T& operator * ();
};
Проблема в том, что если в дереве происходят изменения (добавили/удалили узел), то весь list придется перестраивать. То есть я должен в любой момент времени иметь доступ к самому дереву ну или к его корню. Что можно предпринять в этом случае?
O(N)
памяти для дерева изN
элементов. Попробуйте его покопировать где-нибудь вperformance-critical
участке кода.STL
-подобныхtree
контейнерах. В качестве хорошего референса могу предложить вам [описание итераторовtree.hh
.][1] [1]: tree.phi-sci.com/tree.pdf