The Tree Container Library

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 bi-directional 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 the set() 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 the set() 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 from stored_type. The object is inserted into a child node of the parent in which the function was called. An iterator is returned which points to the inserted node. For tree and unique_tree, if the element already exists within a child node, then the object is not inserted, and the end iterator is returned.
  For sequential_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) all descendants of the node. The node itself is not erased, and its element 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 ending pre_order_iterator for the node. While using the pre_order_iterator, it must be checked against pre_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 ending post_order_iterator for the node. While using the post_order_iterator, it must be checked against post_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 ending level_order_iterator for the node. While using the level_order_iterator, it must be checked against level_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 against node_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 ending pre_order_node_iterator for the node which the operation is called. While using the pre_order_node_iterator, it must be checked against pre_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 ending post_order_node_iterator for the node which the operation is called. While using the post_order_node_iterator, it must be checked against post_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 ending level_order_node_iterator for the node which the operation is called. While using the level_order_node_iterator, it must be checked against level_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 an element as it's only parameter, and returns a pointer to the element. Normally, this function will just call a virtual function of stored_type called clone(). clone() would then be overridden in all the derived classes, to return a pointer to itself (return new derived_type(*this); )
  Complexity: Constant