Click here to Skip to main content
11,479,486 members (35,443 online)
Click here to Skip to main content
Add your own
alternative version

Tree Container Library

, 22 Aug 2007 Zlib 158.7K 6K 109
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 - sequential_tree example explanation
</h1>
<hr />

<p>
	This bit of code (click on the code link to the right) shows the sequential_tree container at work.   It uses functions to perform 
	many of the same operations performed in the 
	generic example.  
	The code illustrates how the sequential_tree container is used.
	The code can be viewed an printed from the the file sequential_example_code.htm. <br/>
	A source file of this example is included in the download<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 compatible with Visual C++ 6.0, 7.0, and 8.0, as well as 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 #include in line 1 is commented out.  Microsoft compilers need this line, so if you're compiling
	with a microsoft compiler, you can un-comment this line.  Line 2 includes the header for sequential_tree.
	Since we will be working with the sequential_tree container exclusively, we won't need to include
	the header for the other trees.  Lines 3 - 5 include STL needed headers.
</p>
<p>
	Line 7 declares a namespace utility, where we will define our utility functions.  Line 9 declares the <code>load_tree()</code>
	function.  This function is very similar the function of the same name in the 
	generic example.  Line 10 declares the function
	<code>traverse_tree()</code>, and line 11 starts the definition of <code>traverse_tree()</code>.  Both of these
	functions are the same as described in the generic example, and will not be described here.  The same is true
	of the function <code>is_last_child()</code> beginning on line 33.
</p>
<p>
	Lines 42 - 56 define the class CAlpha, which will be our 
	stored_type.
	Notice that a less-than operator has been defined for this class.  This definition is not required for the
	sequential_tree, because sequential_tree uses a std::vector for it's internal storage, rather than a std::set, which is used
	by the associative trees.
	It <b>is</b> required, however, to be able to call sequential_tree's <code>sort()</code> (parameter-less) function, as we do 
	in this example.   sequential_tree's sort() (with no parameter) function uses the less-than operation of stored_type, to 
	sort the child nodes within a parent node.
</p>
<p>
	Lines 58 - 61 define a 
	predicate function
	which will be used for one of the methods to sort sequential_tree's child nodes. Notice that it performs the comparison
	<code>lhs.get_text() &gt; rhs.get_text()</code> which has the affect of sorting child nodes in descending order.
	Lines 63 - 69 define a 
	function_object
	which will also be used for one of the methods to sort the child nodes.  Notice that it performs the comparison
	<code>lhs.get_text() &gt; rhs.get_text()</code> which has the affect of sorting child nodes in descending order.
</p>
<p>
	Lines 71 - 100 define main().  Line 74 declares the sequential_tree object we will use in this example,
	and sets it's root node.  Line 76 calls a utility functions which loads the tree.  Line 77 calls
	a utility function which prints the tree.  The function <code>print_tree()</code> is the same function as
	described in the generic example.  Line
	80 sorts only the child nodes within the 
	root node, 
	using the less-than operator defined in CAlpha,
	which will sort the nodes in an ascending manner.  Note that the <code>sort()</code> functions sort only the 
	children
	within the node which the function is called, while the <code>sort_descendant()</code> operations sort
	the descendants
	within the node which the function is called.  Line 81 sends a description of the tree to std::cout, and line
	82 prints the tree structure.
</p>
	Line 85 sorts all the descendants of the root node, which is the whole tree structure.  Since sort_descendant() is called
	with no parameters, the less-than operator of CAlpha determines the sort order, which is ascending.  Lines 86 - 88 
	display the newly sorted tree structure.   Line 90 sorts the children only, within the root node, using the 
	binary predicate function defined on line 58.  This predicate function is defined to sort the nodes in a descending
	manner, so the operation will sort the root nodes children (nodes A, B &amp; C) in a descending order.  Lines 91 - 93
	display the newly sorted tree structure.  
<p>
	Line 95 sorts all the descendants of the root node (the whole tree), using the function object defined on line 63.  The 
	function object is defined to sort the nodes in a descending order also, so after performing this operation, all the nodes
	in the tree structure will be ordered in a descending order.  Lines 96 - 98 display the newly sorted tree structure.
</p>
<p>
	Line 100 calls a function which demonstrate the use of 
	descendant iterators.
	This function is described in detail in the generic example.
</p>
<p>
	Line 106 begins the function which loads (inserts) the tree nodes.  Line 109 creates a tree iterator.  This iterator is created 
	in the same manner as all the trees in the TCL.  Line 112 inserts the first node, A, into the root node.  If <code>insert()</code>
	is used with only a single parameter specifying the node to be inserted, that node is inserted as the last child within the node.
	Another <code>insert()</code> operation, described below, accepts an additional (first) parameter, which specifies the 
	<i>position</i> in which to insert the new child node.  Line 113 insures the node was inserted successfully.  Since <em>it</em>
	now points to node A, lines 118 and 119 can use this iterator to insert nodes E and D into node A.  Note the order in which nodes
	E and D are inserted.  sequential_tree, unlike the 
	associative trees
	does not naturally order child nodes within their parent, so the nodes will be ordered in the way they are inserted, until a 
	sort() operation is performed on the parent node.
</p>

<p>
	Line 121 positions <em>it</em> at node E, and line 122 moves <em>it</em> to node D.  Line 124 inserts node J into node D.
	Line 126 inserts node K into node D, storing an iterator to the newly inserted node.  Then, nodes S and R are inserted
	into node K in lines 129 and 130.   Line 133 decrements <em>it</em> back to node E, where line 135 inserts node L.
</p>
<p>
	Line 137 inserts node B in the root node, and line 138 inserts node F in node B.  Line 141 shows that the TCL iterators
	can be assigned.  Line 142 inserts node M into node F, and lines 144 and 145 insert nodes T and U into node M.
	Line 148 inserts node N into node F, and line 150 inserts node V into node N.
</p>
<p>
	Line 152 positions <em>it</em> at the first child of the root node, or node A.  Line 153 increments <em>it</em> to 
	point to node B.  Line 154 demonstrates another form of sequential_tree's insert().  The first parameter of this
	insert() operation specifies the position at which the new node will be inserted.  The new node given as the second parameter
	will be inserted immediately before the iterator specified as the first parameter.  In this case, node C will be inserted
	before node B.   Lines 156 and 157 insert nodes G and H into node C, and line 160 inserts node O into node H.
</p>
<p>
	Line 162 position <em>it</em> at node O, and lines 165 inserts node W into node O.  Node P is then inserted into
	node H in line 167.  Line 170 demonstrates the use of the <code>parent()</code> operation.  At this time, <em>it</em>
	points to node H, so the parent() operation returns node C which is used to insert node I (into node C).  
	Line 171 makes <em>it</em> point to node I, and lines 174 inserts node Q into node I.  Line 177 inserts node
	X into node Q, and line 179 inserts node Z into node X.   Line 180 also inserts node Y into node X, and 
	since it uses the two parameter form of insert, and the first parameter points to the first child, node Y is
	inserted <i>before</i> node Z.
</p>
<p>
	By studying the output from the program, you can validate the operations of the insertions, iterations, 
	and sort behavior.
</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 | Terms of Use | Mobile
Web02 | 2.8.150520.1 | Last Updated 22 Aug 2007
Article Copyright 2006 by Mitchel Haas
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid