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

Non-recursive traversal of n-trees

Score: 3.3/5 (61 votes)
*****
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 :-[

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
/**
 * An universal template to traverse complex trees non-recursive
 *
 * (c) 2012 Heiko Schäfer <heiko@rangun.de>
 *
 * 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 <heiko@rangun.de>
 **/
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 */