Click here to Skip to main content
15,867,568 members
Articles / Desktop Programming / MFC

Tree Container Library

Rate me:
Please Sign up or sign in to vote.
4.85/5 (29 votes)
22 Aug 2007Zlib10 min read 227.1K   7.2K   111  
A generic template class library for storing data in a tree-like structure.
<html>
<head>
<title>
Tree Container Library: sequential_tree Example Code
</title>
</head>
<body>
<pre>
<code>
  1 //#include "stdafx.h"
  2 #include "sequential_tree.h"
  3 #include &lt;cassert&gt;
  4 #include &lt;string&gt;
  5 #include &lt;iostream&gt;
  6 class CAlpha;
  7 namespace utility
  8 {
  9 	void load_tree(sequential_tree&lt;CAlpha&gt;&amp; alpha_tree );
 10 	template&lt;typename T&gt; void traverse_tree(T&amp; alpha_tree);
 11 
 12 	template&lt;typename T&gt; void print_tree(T&amp; alpha_tree, const int depth)
 13 	{
 14 		std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; std::endl;
 15 
 16 		typename T::const_iterator it = alpha_tree.begin(), it_end = alpha_tree.end();
 17 		for ( ; it != it_end; ++it ) {
 18 			for ( int i = 0; i &lt; depth; ++i ) {
 19 				T* parent = &alpha_tree;
 20 				for ( int j = depth - 1; j &gt; i; --j )
 21 					parent = parent-&gt;parent();
 22 
 23 				std::cout &lt;&lt;  (is_last_child(parent) ? " " : "|");
 24 
 25 				std::cout &lt;&lt; std::string(2, ' ');
 26 			}
 27 			std::cout &lt;&lt; "|" &lt;&lt; std::endl;
 28 			std::cout &lt;&lt; std::string(depth * 3 + 1, ' ') &lt;&lt; "- ";
 29 			print_tree(*it.node(), depth + 1);
 30 		}
 31 	}
 32 
 33 	template&lt;typename T&gt; bool is_last_child(const T* node)
 34 	{
 35 		T* parent = node-&gt;parent();
 36 		typename T::const_iterator it = parent-&gt;end();
 37 		--it;
 38 		return it-&gt;get_text() == node-&gt;get()-&gt;get_text();
 39 	}
 40 }
 41
 42 class CAlpha
 43 {
 44 public:
 45 	CAlpha()  {}
 46 	CAlpha(const std::string&amp; text_ ) : text(text_) {}
 47 	CAlpha(const char* text_ ) : text(text_) {}
 48 	~CAlpha() {}
 49
 50 	friend bool operator &lt; (const CAlpha&amp; lhs, const CAlpha&amp; rhs) 
 51 	{ return lhs.get_text() &lt; rhs.get_text(); }
 52 	std::string get_text() const { return text; }
 53 
 54 private:
 55 	std::string text;
 56 };
 57
 58 bool pred_fcn(const CAlpha&amp; lhs, const CAlpha&amp; rhs)
 59 {
 60 	return lhs.get_text() &gt; rhs.get_text();
 61 }
 62 
 63 struct comp_functor
 64 {
 65 	bool operator() (const CAlpha&amp; lhs, const CAlpha&amp; rhs) const
 66 	{
 67 		return lhs.get_text() &gt; rhs.get_text();
 68 	}
 69 };
 70 
 71 int main(int argc, char* argv[])
 72 {
 73 	// load and print tree&lt;&gt;
 74 	sequential_tree&lt;CAlpha&gt; alpha_tree(CAlpha("sequential_tree&lt;&gt;"));
 75 	
 76 	utility::load_tree( alpha_tree );
 77 	utility::print_tree(alpha_tree, 0);
 78 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 79 
 80 	alpha_tree.sort();
 81 	std::cout &lt;&lt; "Tree root sorted ascending" &lt;&lt; std::endl;
 82 	utility::print_tree(alpha_tree, 0);
 83 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 84 
 85 	alpha_tree.sort_descendants();
 86 	std::cout &lt;&lt; "Whole tree sorted ascending" &lt;&lt; std::endl;
 87 	utility::print_tree(alpha_tree, 0);
 88 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 89 
 90 	alpha_tree.sort(&pred_fcn);
 91 	std::cout &lt;&lt; "Tree root sorted descending" &lt;&lt; std::endl;
 92 	utility::print_tree(alpha_tree, 0);
 93 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 94 
 95 	alpha_tree.sort_descendants(comp_functor());
 96 	std::cout &lt;&lt; "Whole tree sorted descending" &lt;&lt; std::endl;
 97 	utility::print_tree(alpha_tree, 0);
 98 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
 99
100 	utility::traverse_tree(alpha_tree);
101 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl &lt;&lt; std::endl;
102
103 	return 0;
104 }
105
106 void utility::load_tree(sequential_tree&lt;CAlpha&gt;&amp; alpha_tree)
107 {
108 	// create a child iterator
109 	sequential_tree&lt;CAlpha&gt;::iterator it;  
110 
111 	// insert first node, A, and keep an iterator to it's node
112 	it = alpha_tree.insert(CAlpha("A"));
113 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A" );
114 
115 	// insert D and E under A
116 	it = alpha_tree.begin();
117 	assert(it != alpha_tree.end() &amp;&amp; it-&gt;get_text() == "A");
118 	it.node()-&gt;insert(CAlpha("E"));
119 	it.node()-&gt;insert(CAlpha("D"));
120 
121 	it = it.node()-&gt;begin();
122 	++it;
123 	// insert  J under D
124 	it.node()-&gt;insert(CAlpha("J"));
125 	// insert K under D and remember inserted node
126 	sequential_tree&lt;CAlpha&gt;::iterator child_it = it.node()-&gt;insert(CAlpha("K"));
127 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "K");
128 	// insert R and S under K
129 	child_it.node()-&gt;insert(CAlpha("S"));
130 	child_it.node()-&gt;insert(CAlpha("R"));
131 
132 	// increment it (now at D) to point to E
133 	--it;
134 	// insert L under E
135 	it.node()-&gt;insert(CAlpha("L"));
136
137 	it = alpha_tree.insert(CAlpha("B"));
138 	// insert F under B
139 	child_it = it.node()-&gt;insert(CAlpha("F"));
140 	// insert M under F
141 	it = child_it;
142 	child_it = it.node()-&gt;insert(CAlpha("M"));
143 	// insert T and U under M
144 	child_it.node()-&gt;insert(CAlpha("T"));
145 	child_it.node()-&gt;insert(CAlpha("U"));
146 
147 	// insert N under F  (it still points to F)
148 	child_it = it.node()-&gt;insert(CAlpha("N"));
149 	// insert V under N
150 	child_it.node()-&gt;insert(CAlpha("V"));
151 
152 	it = alpha_tree.begin();
153 	++it;
154 	it = alpha_tree.insert(it, CAlpha("C"));
155 	// insert G and H under C
156 	it.node()-&gt;insert(CAlpha("G"));
157 	child_it = it.node()-&gt;insert(CAlpha("H"));
158 	// insert O under H
159 	it = child_it;
160 	child_it = it.node()-&gt;insert(CAlpha("O"));
161
162 	child_it = it.node()-&gt;begin();
163 	assert(child_it != it.node()-&gt;end() &amp;&amp; child_it-&gt;get_text() == "O");
164 	// insert W under O
165 	child_it.node()-&gt;insert(CAlpha("W"));
166 	// insert P under H
167 	it.node()-&gt;insert(CAlpha("P"));
168
169 	// insert I under C using parent of H (which is C)
170 	child_it = it.node()-&gt;parent()-&gt;insert(CAlpha("I"));
171 	it = child_it;
172 
173 	// insert Q under original I
174 	child_it = it.node()-&gt;insert(CAlpha("Q"));
175 	// insert X under Q
176 	it = child_it;
177 	child_it = it.node()-&gt;insert(CAlpha("X"));
178 	// insert Y and Z under X
179 	it = child_it.node()-&gt;insert(CAlpha("Z"));
180 	child_it.node()-&gt;insert(it, CAlpha("Y"));
181 
182 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
183 }
184
185 template&lt;typename T&gt; void utility::traverse_tree(T&amp; alpha_tree)
186 {
187 	std::cout &lt;&lt; std::endl;
188
189 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::pre_order_iterator" &lt;&lt; std::endl;
190 	typename T::pre_order_iterator pre_it = alpha_tree.pre_order_begin();
191 	for ( ; pre_it != alpha_tree.pre_order_end(); ++pre_it ) {
192 		std::cout &lt;&lt; pre_it-&gt;get_text() &lt;&lt; " ";	
193 	}
194 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
195 
196 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::post_order_iterator" &lt;&lt; std::endl;
197 	typename T::const_post_order_iterator post_it = alpha_tree.post_order_begin();
198 	for ( ; post_it != alpha_tree.post_order_end(); ++post_it ) {
199 		std::cout &lt;&lt; post_it.node()-&gt;get()-&gt;get_text() &lt;&lt; " ";	
200 	}
201 	std::cout &lt;&lt; std::endl &lt;&lt; std::endl;
202
203 	std::cout &lt;&lt; alpha_tree.get()-&gt;get_text() &lt;&lt; "::level_order_iterator" &lt;&lt; std::endl;
204 	typename T::const_level_order_iterator level_it = alpha_tree.level_order_begin();
205 	for ( ; level_it != alpha_tree.level_order_end(); ++level_it ) {
206 		std::cout &lt;&lt; level_it-&gt;get_text() &lt;&lt; " ";	
207 	}
208
209 	std::cout &lt;&lt; std::endl;
210 }
211

</code>
</pre>


<script type="text/javascript" src="/stats/tracker.js.php"&gt;&lt;/script>
<noscript>
<p>
	&lt;img style="display: none" src="/stats/static.php" alt='site stats'/>
</p&gt;
</noscript>		


</body>
</html>

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The zlib/libpng License



Comments and Discussions