 Home
 Services
 FAQ
 Portfolio
 Latest News
 Datasoft Talk
 Tree Container Library
 Overview
 Usage
 Interface
 Iterators
 Iterator Overview
 Child Iterators
 Reverse Iterators
 Descendant Iterators
 Ordered Iterators
 Design
 Auxiliary Code
 Implementation
 basic_tree
 associative_tree
 tree/multitree
 unique_tree
 sequential_tree
 child iterators
 descendant iterators
 orderediterators
 Examples
 STL Compatibility
 Overview
 STL Containers
 STL Algorithms
 Development History
 Version History
 Credits
 Documentation
 Download
 About Us
The Tree Container Library
A C++ generic tree container library which, not only works much like the STL, but is also compatible with the STL algorithms. The Tree Container Library is used worldwide in thousands of industries and organizations. It is completely free to use, and is licensed under the zlib/libpng license.
This page describes the public interface which is available to all four tree containers in the TCL. Many of public functions described here are
defined in the base class for all trees, basic_tree. For info on the class design, see Design.
Many of the basic functions return child
iterators. All occurences of the term iterator below refer to the appropriate type of child iterator for the specific tree
container, or tree_type. The two child iterators
are named,
iterator
and const_iterator
as in the STL. Associative tree child iterators are bidirectional iterators.
sequential_tree child iterators are random access iterators. The descendant
iterators iterate over all descendants
of a tree or node.
The documentation below applies to TCL versions 3.50 and higher. The latest version of the TCL can be downloaded from the TCL
download page.
In the function signatures below, stored_type is used to refer to the type of elements being stored in the nodes of the tree container. The term node_compare_type is used to refer to the function object for associative trees which provides the comparison operator for the tree nodes.
The list below is categorized for easy reference.
Tree Construction

tree()
multitree()
unique_tree()
sequential_tree()
Default constructor for the trees. Creates a tree with a single node, the root node. This node is will contain an element which is created with the default constructor for stored_type. Since theset()
operation for associative trees has been discontinued, if you wish to set the element of the root node explicitly, you should use the constructor which follows.
Complexity: Constant 
tree(const stored_type& element)
multitree(const stored_type& element)
unique_tree(const stored_type& element)
sequential_tree(const stored_type& stored_type)
Constructs a tree which will contain a single node, the root node, and sets the element within the root node. Since theset()
operation is discontinued for associative trees, you should use this constructor if you wish to set the root node with an element.
Complexity: Constant 
tree(InputIterator it_beg, InputIterator it_end, const stored_type& element = stored_type())
multitree(InputIterator it_beg, InputIterator it_end, const stored_type& element = stored_type())
unique_tree(InputIterator it_beg, InputIterator it_end, const stored_type& element = stored_type())
sequential_tree(InputIterator it_ben, InputIterator it_end, const stored_type& element = stored_type())
Range constructors for the trees. Inserts elements in the range of [beg_it, end_it). The input range must be for a standard STL container, or a tree container of the same type. The parent node it initiated with element. If the input range is for a tree container of the same type, it will insert the child nodes within the range along with their descendants.
Complexity: Logarithmic 
tree(const tree& tree_obj)
multitree(const multitree& tree_obj)
unique_tree(const unique_tree& tree_obj)
sequential_tree(const sequential_tree& tree_obj)
Copy constructors for tree container. Copies the whole tree structures.
Complexity: Logarithmic
Inserting nodes

iterator insert(const stored_type& element)
This is the standard insertion function for all trees. The parameter is a reference to the stored object being stored in the node. This function is polymorphic, and allows the insertion of objects derived fromstored_type
. The object is inserted into a child node of the parent in which the function was called. Aniterator
is returned which points to the inserted node. Fortree
andunique_tree
, if the element already exists within a child node, then the object is not inserted, and the end iterator is returned.
Forsequential_tree
, this function inserts the object as the last child of the parent.
Complexity: Logarithmic 
iterator insert(const tree_type& tree_obj)
This function inserts a tree (or subtree) into a tree node of the same type. All descendants of the inserted tree are inserted in the process.
Complexity: Logarithmic 
iterator insert(iterator pos, stored_type& element)
For associative trees, inserts stored_type using pos as a hint. For sequential_tree, inserts element before pos.
Complexity: Logarithmic 
iterator insert(iterator pos, tree_type& tree_obj)
For associative trees, inserts the tree/node obj (and it's descendants) using pos as a hint. For sequential_tree, inserts tree_obj before pos.
Complexity: Logarithmic 
void insert(InputIterator beg_it, InputIterator end_it)
Inserts elements of the range [beg_it, end_it) into the tree. The input range can be a STL container range, or a range from a tree container of the same type. If the range is from a tree container of the same type, all child nodes within the range and their descendants will be inserted.
Complexity: Logarithmic
Removing nodes

void erase(iterator pos)
*** for associative trees ***
iterator erase(iterator pos)
*** for sequential_tree ***
Erases the child node (and it's descendants if any) at the position of pos. Caller must insure that pos is valid. For sequential_tree, the return value specifies the position of the following element, or end().
Complexity: Logarithmic 
void erase(iterator beg_it, iterator end_it)
*** for associative trees ***
iterator erase(iterator beg_it, iterator end_it)
*** for sequential_tree ***
Erases all child nodes in the range of [beg_it, end_it), along with any descendants they may have. Caller must insure that the range is valid. For sequential_tree, the return value specifies the position of the following element, or end().
Complexity: Logarithmic 
void clear()
Clears (erases) alldescendants
of the node. The node itself is not erased, and itselement
remains intact.
Complexity: Logarithmic
Querying node state

stored_type* get()
Returns a pointer to the element, within the node. Remember that the nodes are not themselves the elements but rather contain elements.
Complexity: Constant 
const stored_type* get() const
Returns const pointer to the element within the node.
Complexity: Constant 
tree_type* parent()
Returns a pointer to the parent node, or NULL if there is no parent node (indicating that this is the root node).
Complexity: Constant 
bool is_root()
Indicates whether node is the root node in the tree structure.
Complexity: Constant 
bool empty()
Indicates if the node has or has no children. Cares not about the element within the node itself.
Complexity: Constant 
size_type size()
Returns the number of child nodes within the node. Only counts the immediate children, not the descendants.
Complexity: Constant 
size_type max_size()
Returns the maximum number of child nodes possible for a single node.
Complexity: Constant
Comparison Operations

bool operator ==(const tree_type& lhs, const tree_type& rhs)
Returns true if every lhs node, including the root, children, and all descendants, is equal to those in rhs. All nodes must also be in the same order in both trees. The node_compare_type is used on each node to determine equality.
Complexity: Logarithmic 
bool operator !=(const tree_type& lhs, const tree_type& rhs)
determines if rhs is not equal to lhs. See operator =() above for more info.
Complexity: Logarithmic 
bool operator <(const tree_type& lhs, const tree_type& rhs)
Returns true if lhs is lexicographically less then rhs.
Complexity: Logarithmic 
bool operator <=(const tree_type& lhs, const tree_type& rhs)
*** equivalent to !(rhs < lhs) ***
bool operator >(const tree_type& lhs, const tree_type& rhs)
*** equivalent to (rhs < lhs) ***
bool operator >=(const tree_type& lhs, const tree_type& rhs)
*** equivalent to !(lhs < rhs) ***
Complexity: Logarithmic
Iterator retrieval
The following iterator retrieval operations specify the element iterator retrieval operations.

iterator begin()
const_iterator begin() const
Returns an iterator pointing to the first child in the node. If the node is empty, returns the end iterator.
Complexity: Constant 
iterator end()
const_iterator end() const
Returns an iterator pointing past the last child node. Iterators can be checked against the end iterator to see if an operation succeeded, or if they have traversed through all the children.
Complexity: Constant 
reverse_iterator rbegin()
const_reverse_iterator rbegin() const
Returns a reverse iterator pointing to the last child in the node(). If the node is empty, returns rend(). This iterator reverses the increment and decrement operators, and is similar in operation to the reverse iterators in the STL.
Complexity: Constant 
reverse_iterator rend()
const_reverse_iterator rend() const
Returns an iterator pointing prior to the beginning child node. Use this operation to determine the end of a reverse iterator traversal.
Complexity: Constant 
pre_order_iterator pre_order_begin()
const_pre_order_iterator pre_order_begin() const
Returns the beginning pre_order_iterator for the node.pre_order_begin()
will by nature return an iterator pointing to the called node.
Complexity: Constant 
pre_order_iterator pre_order_end()
const_pre_order_iterator pre_order_end() const
Returns the endingpre_order_iterator
for the node. While using thepre_order_iterator
, it must be checked againstpre_order_end()
to know when all the descendants have been traversed.
Complexity: Constant 
post_order_iterator post_order_begin()
const_post_order_iterator post_order_begin() const
Returns the beginning post_order_iterator for the node.post_order_begin()
will by nature return an iterator pointing to the deepest first descendant node, if any.
Complexity: Logarithmic 
post_order_iterator post_order_end()
const_post_order_iterator post_order_end() const
Returns the endingpost_order_iterator
for the node. While using thepost_order_iterator
, it must be checked againstpost_order_end()
to know when all the descendants have been traversed.
Complexity: Constant 
level_order_iterator level_order_begin()
const_level_order_iterator level_order_begin() const
Returns the beginning level_order_iterator for the node.level_order_begin()
will by nature return an iterator pointing to the called node.
Complexity: Constant 
level_order_iterator level_order_end()
const_level_order_iterator level_order_end() const
Returns the endinglevel_order_iterator
for the node. While using thelevel_order_iterator
, it must be checked againstlevel_order_end()
to know when all the descendants have been traversed.
Complexity: Constant
The following iterator retrieval operations specify the node_iterator retrieval operations.

node_iterator node_begin()
const_node_iterator node_begin() const
Returns a node iterator pointing to the first child in the parent node. If the parent node is empty, returns node_end().
Complexity: Constant 
node_iterator node_end()
const_node_iterator node_end() const
Returns a node iterator pointing past the last child node. Node iterators can be checked againstnode_end()
to see if an operation succeeded, or if they have traversed through all the children.
Complexity: Constant 
reverse_node_iterator node_rbegin()
const_reverse_node_iterator node_rbegin() const
Returns a reverse node iterator pointing to the last child in the node(). If the node is empty, returns node_rend(). This node iterator reverses the increment and decrement operators, and is similar in operation to the reverse iterators in the STL.
Complexity: Constant 
reverse_node_iterator node_rend()
const_reverse_node_iterator node_rend() const
Returns a node iterator pointing prior to the beginning child node. Use this operation to determine the end of a reverse node iterator traversal.
Complexity: Constant 
pre_order_node_iterator pre_order_node_begin()
const_pre_order_node_iterator pre_order_node_begin() const
Returns the beginning pre_order_node_iterator for the called node.pre_order_node_begin()
will by nature return an iterator pointing to the called node.
Complexity: Constant 
pre_order_node_iterator pre_order_node_end()
const_pre_order_node_iterator pre_order_node_end() const
Returns the endingpre_order_node_iterator
for the node which the operation is called. While using thepre_order_node_iterator
, it must be checked againstpre_order_node_end()
to know when all the descendants have been traversed.
Complexity: Constant 
post_order_node_iterator post_order_node_begin()
const_post_order_node_iterator post_order_node_begin() const
Returns the beginning post_order_node_iterator for the node.post_order_node_begin()
will by nature return an iterator pointing to the deepest first descendant node, if any.
Complexity: Logarithmic 
post_order_node_iterator post_order_node_end()
const_post_order_node_iterator post_order_node_end() const
Returns the endingpost_order_node_iterator
for the node which the operation is called. While using thepost_order_node_iterator
, it must be checked againstpost_order_node_end()
to know when all the descendants have been traversed.
Complexity: Constant 
level_order_node_iterator level_order_node_begin()
const_level_order_node_iterator level_order_node_begin() const
Returns the beginning level_order_node_iterator for the node.level_order_node_begin()
will by nature return an iterator pointing to the called node.
Complexity: Constant 
level_order_node_iterator level_order_node_end()
const_level_order_node_iterator level_order_node_end() const
Returns the endinglevel_order_node_iterator
for the node which the operation is called. While using thelevel_order_node_iterator
, it must be checked againstlevel_order_node_end()
to know when all the descendants have been traversed.
Complexity: Constant
Miscellaneous operations

void set_clone(stored_type* (*pFcn)(const stored_type&))
Sets a clone function needed when the tree contains objects of derived types. The clone function that you define and pass to this function, takes a const reference to anelement
as it's only parameter, and returns a pointer to theelement
. Normally, this function will just call a virtual function ofstored_type
calledclone()
.clone()
would then be overridden in all the derived classes, to return a pointer to itself (return new derived_type(*this);
)
Complexity: Constant