• Articles
• Non-recursive traversal of n-trees
Dec 29, 2012 (last update: Jan 27, 2013)

# Non-recursive traversal of n-trees

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102`` ``````/** * An universal template to traverse complex trees non-recursive * * (c) 2012 Heiko Schäfer * * This templates contain non-recursive functions to traverse n-trees * * Distribution of this file is only allowed if author is mentioned. Modifications of * the algorithm have to be reported to the author. * **/ #ifndef HGL_NR_TRAVERSER_H #define HGL_NR_TRAVERSER_H #include namespace HGL { namespace Algorithm { /** * @brief A condition on how to proceed before traversing child nodes * **/ typedef enum { /// Continue traversing the children of the current node CONTINUE, /// Discard all children of the current node DISCARD, /// Break, i.e. stop traversing at this point BREAK } COND; template < typename Iterator, typename Type, typename Begin, typename End, typename Top, typename Middle, typename Bottom > /** * @brief Traverses a n-tree (i.e. a tree with 0-n children on every node), performing actions on * every node * * @note This algorithm works non-recusive. * * The middle functor takes a node as argument: * @code * void middle(const HGL::IType *); * @endcode * * The top functor additionally returns Algorithm::COND: * @code * Algorithm::COND top(const HGL::IType *); * @endcode * * The function should be called with the type of iterator as template parameter: * @code * Algorithm::traverse(node, begin, end, top, middle, bottom); * @endcode * * @param root Node to start traversing * @param getBeginIterator functor to get the begin iterator to the children of the current node * @param getEndIterator functor to get the end iterator to the children of the current node * @param top functor called before traversing child nodes * @param middle functor called after completely traversing all children of current node * @param bottom functor called after traversing a node * * @author Heiko Schäfer **/ void traverse(Type root, Begin &getBeginIterator, End &getEndIterator, Top &top, Middle &middle, Bottom &bottom) { std::stack > stack; stack.push(std::make_pair(root, getBeginIterator(root))); while(!stack.empty()) { const COND &c = top(stack.top().first); if(c == CONTINUE) { while(!stack.empty()) { Iterator iter = stack.top().second; if(stack.top().second != getEndIterator(stack.top().first)) { ++(stack.top().second); stack.push(std::make_pair(*iter, getBeginIterator(*iter))); break; } else { middle(stack.top().first); stack.pop(); } } bottom(); } if(c == BREAK) break; } } } } #endif /* HGL_NR_TRAVERSER_H */ ``````