پیمایش غیر بازگشتی درخت های nتایی

به نام خدا

در زیر الگوریتم غیربازگشتی درخت های nتایی را مشاهده می نمایید.مثال: درخت هایی با گره های n-1 فرزند. این الگوریتم برای درخت های دودویی کار می کند. اما مزیت آن در پیمایش درختان پیچیده است.
پیمایش به صورت از بالا به پایین یا همان top to bottom صورت می گیرد. نحوه چگونگی استفاده از آن در سورس کد آمده است.

/**
* 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 <stack>

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<MYTYPE::iterator>(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<std::pair<Type, Iterator> > 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 */