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

# Non-recursive traversal of n-trees

Below is an algorithm for non-recursive traversal of n-trees, i.e. trees with 1-n child nodes. Therefore it works for binary trees too, but the advantage lays in traversing complex trees.

The order in traversing is kept from top to bottom. Documentation on how to use is within the source code.

EDIT: of course the functors should be references instead of copies :-[

 ``123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102`` ``````/** * An universal template to traverse complex trees non-recursive * * (c) 2012 Heiko Sch?fer <[email protected]> * * 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 <[email protected]> **/ 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 */ ``````

### C++

• 1793521592 2018-02-23
• 2864591591 2018-02-23
• 6167231590 2018-02-23
• 3669201589 2018-02-23
• 7946381588 2018-02-23
• 8957701587 2018-02-23
• 3891941586 2018-02-23
• 6039851585 2018-02-23
• 2573991584 2018-02-23
• 7728781583 2018-02-23
• 3731582 2018-02-23
• 1007451581 2018-02-22
• 8908121580 2018-02-22
• 141161579 2018-02-22
• 9421578 2018-02-22
• 2826901577 2018-02-22
• 3647361576 2018-02-22
• 5717551575 2018-02-22
• 523811574 2018-02-22
• 6439871573 2018-02-22