Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version
Go to top

Tree Container Library

, 22 Aug 2007
A generic template class library for storing data in a tree-like structure.
tcldoc_40802.zip
TCL.chm
tcldoc_4_07_01.zip
TCL.chm
tcl_3_55.zip
basic_tree.inl
associative_tree.inl
descendant_iterator.inl
ordered_iterator.inl
multitree.inl
tree.inl
child_iterator.inl
unique_tree.inl
sequential_tree.inl
tcl_4_07.zip
sequential_tree.inl
tree.inl
unique_tree.inl
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
tcl_4_08.zip
associative_tree.inl
basic_tree.inl
descendant_iterator.inl
descendant_node_iterator.inl
multitree.inl
sequential_tree.inl
tree.inl
unique_tree.inl
TCL.chm
tcl_test_suite_081606.zip
descendant_iterator_tester.inl
modifying_algorithm_tester.inl
nonmodifying_algorithm_tester.inl
ordered_iterator_checker.inl
sequential_tree_tester.inl
stl_algorithm_tester.inl
unique_tree_tester.inl
associative_tree_tester.inl
basic_tree_tester.inl
child_iterator_tester.inl
child_sequential_iterator_tester.inl
tree_container_library_demo.zip
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_explanation.rtf
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_explation.rtf
unique_tree_example_results.jpg
generic_example_diagram.jpg
generic_example_explanation.rtf
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_explanation.rtf
tree_container_library_demos.zip
generic_example_diagram.jpg
generic_example_results.jpg
polymorphic_example_diagram.jpg
polymorphic_example_results.jpg
sequential_tree_example_diagram.jpg
sequential_tree_example_results.jpg
unique_tree_example_diagram.jpg
unique_tree_example_results.jpg
tree_container_library_src.zip
multitree.inl
basic_tree.inl
Tree.inl
unique_tree.inl
tree_container_lib_src.zip
basic_tree.inl
associative_tree.inl
unique_tree.inl
Tree.inl
sequential_tree.inl
multitree.inl
<h1>
	Tree Container Library: Examples - Generic Example Explanation
</h1>
<hr />

<p>
	This example code shows all three 
	associative_tree containers at work.   
	Since this example makes use of the <code>find()</code> operation, which is only available to the associative_trees,
	the sequential_tree is not included in this example.
	The example uses template functions to perform the same
	operations on the three different tree types.  The code illustrates the differences between the tree containers.
	The code can be viewed and printed from the accompanied file generic_example_code.htm. <br/>
	This example is compatible with versions 3.50 and higher of the TCL.  The latest version of the TCL
	can be downloaded from the <a href='/tree_container_library/download.php'>TCL download page</a>.
</p>
<p>	
	This generic example, as well as the library, is now compatible with Visual C++ 6.0, VC7, VC8, and gcc.
	For the VC6 compiler, users need to un-check the <i>Enable minimal rebuild</i> option for successful compilation.
	Also for VC 6.0 users, the normal <code>#pragma warning (disable : xxxx)</code> directive
	is necessary to avoid the compiler warnings.
</p>
<p>
	The letters A to Z are inserted in the tree's to form the tree structure (shown to the right).
	The tree structure shows duplicated nodes for the vowels in a different color.  Depending
	on the tree container, not all of these duplicate nodes will appear in all the containers.
	A sample of the results to the console is also given to the right.
</p>
<p>
	Line 1 is used for Visual Studio compilers.  Those using MS compilers can un-comment this line.<br/>
	Lines 2 - 4 include the three types of tree containers from the TCL. If you have the TCL placed
	in a separate directory, you may need to modify the paths on these lines.  
</p>
<p>
	Lines 9 - 42 declare and in two cases, define the utility functions, placed in a namespace for convenience.  
	The functions are templatized, to accept all three types of tree containers.
</p>
<p>
	Lines 11 and 12 declare a function which will be covered further below.
	Line 14 begins a template function which prints the tree structure to std out, using simple recursion.  Line 16 prints the name of the
	current node.  Line 18 declares a const_iterator to iterate over the child nodes.  Lines 19 - 32 iterate over the children
	within a given parent.  The loop in lines 20 - 28 are needed only to print the lines connecting the nodes, and to 
	determine the amount of indent for a given child node.  To do this, the parent nodes are obtained repeatingly to the current depth,
	to determine if the parent in question is the last child.  If so, the vertical lines moving down from the nodes are not displayed.
	Line 181 prints the vertical line under the parent node at the current depth.  Line 182 prints the small horizontal line
	before the node.  Line 31 calls itself recursively.
</p>
<p>
	The function starting on line 35 is needed to determine if the passed node is the last node within it's parent.
	It does this by obtaining the pointer to it's parent, in line 37.  Then an iterator to the last node in the parent
	is obtained in lines 38 - 39.  This is safe, because we know the parent contains at least one node, (the node which was passed).
	Line 40 compares the passed node against the last node of the parent, and returns the result.
</p>
<p>
	Lines 44 - 58 define a class, CAlpha, which will serve as the storage type for the trees, to store in the tree nodes.
	It's a very basic class, which only holds the state of name that it's given.   As with the STL, a default constructor
	must be present to use the class in the TCL.   Also, notice that the less operator is defined.  If this operator isn't
	defined for the storage class, a comparison operation must be supplied explicitly as the second template parameter
	in the tree declarations.   Also, a constructor accepting a string is supplied for convenience.
</p>
<p>
	Line 60 starts main(). <br/>
	Lines 62 - 68 load, print, and traverse the sample tree container. <br/>
	Lines 70 - 76 load, print, and traverse the sample multitree container. <br/>
	Lines 78 - 84 load, print, and traverse the sample unique_tree container. <br/>
	Lines 63, 71, and 79 declare the tree containers.  The container declarations are very similar
	to that of the STL containers.  The second template parameter is not needed in the declarations, 
	since CAlpha defines it's own &lt; operator.  The second template parameter for all three
	tree containers defaults to std::less&lt;stored_type&gt;, where CAlpha is stored_type in this case,
	which causes the &lt; operator or CAlpha to be used for the node comparisons. <br/>
	The tree constructors take an argument of stored_type.  This allows the constructors to
	set the root node stored_type and text.  This text will be used
	in the output, when the tree's are printed to std::cout.
</p>
<p>
	Line 89 begins the template function which populate the tree containers.
	The template parameter, T, parametizes the type of container passed, or, in succession: <br/>
	<code>tree&lt;CAlpha&gt;</code>, <code>multitree&lt;CAlpha&gt;</code>, and <code>unique_tree&lt;CAlpha&gt;</code> <br/>
	Line 92 creates a child iterator.
	This iterator will be used for finding, traversing, and inserting nodes. <br/>
	Beginning with version 3.50 of the TCL, the * and -&gt; operations of the iterators return a reference and pointer
	to the stored_type object contained in the nodes, not to the nodes themselves, as in previous versions.
	Thus, to access the underlying node from an iterator, we must use the iterator's node() operation.
	Line 95 inserts the first node into the tree.  Notice that the insert() operation takes a stored_type,
	(<i>an object of the type being stored</i>), or in this case, a CAlpha object.  Notice also that the insert() operation
	returns an iterator.  This iterator will point to the inserted node if successful, or to the end() iterator
	of the parent, if unsuccessful.
	Line 96 tests that the insertion was successful.  Tree const_iterators, like the const_iterators in the STL, can
	only access stored_type's (CAlpha) const class members.
</p>
<p>
	Line 98 attempts to insert a duplicate node in the root node.  A duplicate node is determined by the comparison
	operation of the tree, in this case, the &lt; operator of CAlpha.  This insert() operation will fail for the tree
	container, since duplicate nodes are not allowed under a given parent.  It will also fail for the unique_tree container,
	since duplicate nodes are not allowed in the entire tree, let alone a given parent.  The operation will be successful in 
	the multitree container, since duplicate nodes are allowed under a given parent in the multitree container. <br/>
	Lines 99 - 100 test the outcome of the duplicate insertion, and display the results to std::cout.
</p>
<p>
	Line 103 positions the iterator at the beginning node of the tree, or node A.  The begin() operation returns an iterator
	to the first node of a node (not necessarily the root) that it's called on.  If the node contains no 
	children, then the 
	node's end() iterator is returned.  Remember that a tree is regarded as an ordinary node, and that all nodes in a tree
	can be considered trees themselves.  <br/>
	Line 105 inserts node D in node A.  Notice that the insertion operation is performed on the iterator through the 
	iterator's node() operation.  This shows how the underlying node operations are exposed to the iterator with the iterator's node() operation.  
	A second iterator is created, child_it, and used for the remaining of the function, to retreive the return
	iterator value of insert operations performed by the first created iterator.
	Line 106 inserts node E also in node A.  Since no nodes will be inserted in node E, the return iterator
	of the insert() operation need not be saved.
</p>

<p>
	Line 109 shows that you can assign one iterator to another.  Line 111 inserts node J in node D.  Since no nodes will be inserted
	in node J, the return iterator need not be saved.  Node K is then also inserted in node D in line 113.  The return iterator
	is saved, since nodes will be inserted in node K.  Nodes R and S are inserted in node K in lines 116 - 117.
	At this time, iterator it points to node D.  After incrementing it in line 120, it will point to node E.  Line 122 then inserts
	node L in node E.
</p>
<p>
	With all the descendents of node A, line 124 inserts node B in the root node.  Then an attempt is made in line 126 to insert a second node
	E in node B.  Since this second node E has a different parent than the first node E, the insertion will succeed for  
	tree, as well as for multitree.  It will fail for unique_tree, however, since unique_tree guarantees that every node in the 
	entire tree will be unique.  Lines 127 - 128 display the results of the insertion of the second node E.
</p>
<p>
	In line 129, node F is next inserted in node B.  Then in line 132, Node M is inserted in node F.  In lines 134 - 135, nodes T and U 
	are inserted in node M.  Since iterator it still points to node F, it is used in line 138 to insert node N in node F.  Line 140 
	makes an attempt to insert a second node U.   Since the second node U has a different parent than the first node U, the insertion
	will be successful for tree and multitree.  It will fail, however for unique_tree.  Line 140 tests for the success of the insert
	operation be testing the return value of insert() directly.  Line 141 displays the results of the insert operation if unsuccessful.
	Line 143 inserts node V into node N.
</p>
<p>
	With the descendants of node B inserted, line 145 inserts node C in the root node.  Nodes G and H are inserted in node C
	in lines 147 - 148.  Node O is then inserted in node H in line 151.  In line 153, an attempt is made to insert a second node O
	in node H.  This insertion should fail for tree, since tree insures all nodes are unique with a given parent.  The insertion will
	also fail for unique_tree.  
</p>
<p>
	Since iterator it now points to node H, and the first insertion of node O in node H was successful, line 157 will
	set child_it to node O.  Line 160 then inserts node W in node O.  With iterator it still pointing to node H, 
	line 162 inserts node P in node H.
</p>
<p>
	Line 165 inserts a node using the parent() operation.  Since iterator it now points to node H, and node H's parent
	is node C, line 165 inserts node I in node C.  Afterwards, in line 169, an attempt is made to insert another node I,
	in the first node I.  Of course, the operation will be successful for multitree.  Since the two node I's have different parents,
	the insertion will also be successful for tree.  The insertion will fail for unique_tree.  Lines 170 - 171 display the result
	of the failed insertion.
</p>
<p>
	With iterator it pointing to the first node I, line 174 inserts node Q in node I.  Line 177 then inserts node X in node Q.
	And finally, lines 179 - 180 insert nodes Y and Z in node X.
</p>
<p>
	The function template starting on line 185 uses the 
	descendant iterators
	(<a href='/tree_container_library/iterators/descendant.php'>see here</a>) 
	to traverse all three trees in pre-order, post-order, and level-order manners.  A list of nodes is printed for each type
	of descendant iterator to check the behavior of the iterators. Lines 189, 196, and 203 print the tree type and descendant 
	iterator type.  Lines 190, 197, and 204 declare the descendant iterators.  Notice that a non-const descendant iterator
	is created for the pre_order_iterator, while const descendant iterators are created for the post_order_iterator and 
	level_order_iterator.  In this example, it doesn't matter if the iterator is const or non-const, because the operations
	performed on the iterators are const operations.  If non-const operations were being performed on the iterators, all of them
	would need to be non-const.
</p>
<p>
	Lines 191, 198, and 205 start the iterators looping through the tree structures.  The syntax of the descendant iterator use
	is very similar to that of the STL iterators.  Lines 192, 199 and 206 print the text of the current node.
</p>

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

Share

About the Author

Mitchel Haas
Software Developer Datasoft Solutions
United States United States
I'm a c++ programmer in the midwest, now using VC7 at work and at home. I enjoy creating generic libraries, and template based programming.
 
I also enjoy web development (xhtml, css, javascript, php).

| Advertise | Privacy | Mobile
Web03 | 2.8.140926.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid