tree_class_doc

st_tree Home / st_tree Documentation

tree<Data, CSModel, Alloc>

Data – The data type to be contained in the tree and node containers. Each node contains an instance of Data.

CSModel – Specifies the storage model used by each node to store its child nodes. Default is raw<>. Options are:

• raw<> – nodes store their children using a vector<> storage model
• ordered<Compare> – nodes store children using an ordered multiset<> storage model. Compare defaults to std::less<Data>.
• keyed<Key, Compare> – nodes store children using a keyed map<> storage model. Compare defaults to std::less<Key>

Alloc – The allocator type. Defaults to std::allocator

tree_type – alias for tree’s type
data_type – alias for Data template parameter
cs_model_type – alias for CSModel storage model specifier
allocator_type – alias for Alloc allocator type

node_type – data type of nodes contained by the tree

value_type – data type contained by the tree container class. The value type of a tree is its node_type.
pointer – pointer to value_type
reference – reference to value_type
const_pointer – pointer to constant value_type
const_reference – reference to constant value_type
size_type – represents size (unsigned) values
difference_type – represents difference (signed) values
iterator – iterates over nodes of tree (breadth first order)
const_iterator
bf_iterator – iterates over nodes of tree, breadth first order
const_bf_iterator
df_pre_iterator – iterates over nodes of tree, depth-first preorder
const_df_pre_iterator
df_post_iterator – iterates over nodes of tree, depth-first postorder
const_df_post_iterator

tree() – default tree constructor: an empty tree
~tree() – destructor: all contained nodes are deallocated

tree(const tree& src) – copy constructor: deep copy of (src).
tree& operator=(const tree& src) – assignment operator: deep assignment of (src).

bool empty() – returns true if tree has no nodes
size_type size() – returns number of nodes in the tree

node_type& root() – return the root node. Throws st_tree::empty_exception if tree is empty.
const node_type& root() const

void insert(const data_type& data) – insert a root node containing (data)
void insert(const node_type& src) – insert copy of (src) to root of tree
void insert(const tree_type& src) – insert copy of root of (src) to root of tree

void erase() – erase the root node (node children are erased recursively)
void clear() – reset tree to empty: all nodes are deallocated
void swap(tree_type& src) – swap tree with (src)

void graft(node_type& src) – transfer (src) to root of tree (not copied).
Replaces contents of tree with src. Note src is removed from its original location.
void graft(tree_type& src) – transfer root of (src) to root of tree (not copied)
Replaces contents of tree with src. Note src is empty after this operation.

bool operator==(const tree& rhs) const – true if tree is equal to (rhs). Trees are equal if their root nodes are equal. Two nodes are equal if their data instances are equal, and if their child nodes are lexicographically equal (as defined by iterating begin() to end()).
bool operator!=(const tree& rhs) const

bool operator<(const tree& rhs) const – true if tree is less than (rhs). Tree (A) is less than tree (B) if A.root() < B.root(). Node (a) is less than (b) if a.data() < b.data(), otherwise if the children of (a) are lexicographically less than children of (b) (iterating begin() to end()).
bool operator>(const tree& rhs) const
bool operator<=(const tree& rhs) const
bool operator>=(const tree& rhs) const

iterator begin() – iteration over nodes of tree (breadth first traversal)
const_iterator begin() const
iterator end()
const_iterator end() const

bf_iterator bf_begin() – iteration over nodes of tree: breadth first traversal
const_bf_iterator bf_begin() const
bf_iterator bf_end()
const_bf_iterator bf_end() const

df_pre_iterator df_pre_begin() – iteration over nodes of tree: depth first pre order traversal
const_df_pre_iterator df_pre_begin() const
df_pre_iterator df_pre_end()
const_df_pre_iterator df_pre_end() const

df_post_iterator df_post_begin() – iteration over nodes of tree: depth first post order traversal
const_df_post_iterator df_post_begin() const
df_post_iterator df_post_end()
const_df_post_iterator df_post_end() const