You need to implement the simplest container for the binary tree, define the begin (), end () functions and reload the ++ and * operators for the iterator. To navigate through the elements, I decided to write tree nodes to the STL-list and move the iterator along it. The leftmost element of the tree is considered the beginning of the container, the element beyond the rightmost one is the end of the container.

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

The problem is that if changes occur in the tree (add / delete a node), then the entire list will have to be rebuilt. That is, I must at any time have access to the tree itself or to its root. What can be done in this case?

  • Cool implementation of an iterator that occupies O(N) memory for a tree of N elements. Try to copy it somewhere in the performance-critical code section. - Costantino Rupert
  • I agree that such an iterator cannot be called. Yes, and the tree as such is difficult to imagine a container like STL. But how can you then implement at least a kind of iterator in my case? - carapuz
  • Add in the Node to the Left, Right also the Parent (reference to the parent, for the root NULL). Accordingly, it will be necessary to change the methods of inserting and deleting nodes, but the crawling (the amount of data in the iterator) will be easier. - avp
  • one
    @carapuz See how iterators are made in STL tree containers. As a good reference, I can offer you [iterator description tree.hh ] [1] [1]: tree.phi-sci.com/tree.pdf - Costantino Rupert

1 answer 1

If you access the nodes of the tree through an iterator, then this is quite possible. After removing one object from the container, in most cases all iterators become invalid. And in this regard, the tree has to be rebuilt.

  • that is, I need to execute, say, one iteration, to create an iterator, work with it and then delete it. and for the next operation, create a new iterator if the tree has changed? or is it still possible to somehow change an existing iterator? - carapuz
  • @carapuz, IMHO iterator should always keep track of the current state of the object. At the very least, it should not reference deleted items in the collection. Unfortunately, far everyone follows this model. - avp 9:47 pm
  • one
    @avp: This is really difficult, because the iterator exists separately from the container, and the container does not know when the iterator is still alive, and when it has already been destroyed, because the client no longer needs it. Therefore, the container cannot inform the iterator that it has changed the structure. STL iterators simply cease to be valid after any container changes, and this is their official architecture. (Necroposting, yes.) - VladD
  • @VladD, yes, difficult. Therefore, there are a lot of mistakes with them (the programmer believes that he was given the right tool, but he is rarely flawed, rarely anyone says). - avp
  • one
    @avp: A textbook example of a leaky abstraction, as for my taste. Therefore, there are questions "how to remove from the container during the iteration on it." Design error, in one word. - VladD