Question:
I want to write an iterator for a self-written tree (avl), but I can't figure out how the iterator should behave during incrementing? That is, depending on the position of the element pointed to by the iterator (being in the right or left branch), it should behave differently. In addition, it should be able to climb up the tree, but the nodes only point to the descendants, not the parents. Need to append a pointer to the child to each node? How is a similar problem solved in stl ?
Answer:
-
If you want to implement a "lightweight" iterator over a tree, then yes, in such a situation you will have to somehow store pointers to their ancestors in the tree nodes in one way or another. The details of such storage may differ, but the general idea remains the same: it is necessary to be able to determine its ancestor for a given tree node based on the information stored in the tree itself.
If such storage is implemented in the tree itself, then traversing the tree with an iterator becomes a relatively trivial task (depending on which traversal order you need).
-
If you do not have the ability to store the child-ancestor relationship in the tree itself, then the "levoy" iterator will not work: each iterator will have to store a "heavy" state inside itself. Namely: the path from the root of the tree to the current node of the tree. This path will give the iterator the ability to return from the child to the front when the need arises during the traversal.
Of course, if you have a choice, the most sensible option is the first option with a "leeworthy" iterator. This is exactly how it is done in the STL.