The General_tree class attempts to create a class in the spirit of the STL for hierarchically ordered data. The ordering is explicit: the programmer decides what which objects descend from others.

There are three means of traversing a general tree:

• A general iterator which traverses through siblings and allows access to the corresponding iterators through children or an iterator accessing the parent.
• A depth-first traversal iterator which linearly steps through the objects in a depth-first traversal order. This does not allow either pre- or post-order traversals, however.
• A breadth-first traversal iterator which linearly steps through the objects in a breadth-first traversal order.

Children are ordered; however, the default insert function simply appends the new child onto the list of children.

The memory requirements are Θ(n) in the number of nodes; however, an additional 36 bytes (twice that on 64-bit computers) are required per node. The explicit iterator requires only Θ(1) memory; however, the depth- and breadth-first traversal iterators could require O(n) memory.

General Tree
class General_tree<Type>

Constructors

General_tree<Type>( Type const &obj )

The constructor creates a root node containing an argument which is passed to it. As a tree has a single root, this one object may be modified but cannot be deleted.

Accessors

bool empty() const

By design, this must return false—there is always a root node. (Θ(1))

int size() const

The size function returns the number of objects stored within the general tree. (Θ(1))

int height() const

The height function returns the height (the length of the longest path from the root to a node) of the general tree. (Θ(1))

Mutators

void clear() const

The clear function removes all objects other than the root node from the general tree. (Θ(n))

Iterator Functions

iterator begin()

Returns a explicit (programmer-directed) iterator referring to the root node. (Θ(1))

iterator end()

Returns an iterator referring to one-past-the-root-node. (Θ(1))

iterator begin_depth()

Returns a depth-first traversing iterator referring to the root node. (Θ(1))

iterator end_depth()

Returns a depth-first traversing iterator referring to one-past-the-last-node of the depth-first traversal ordering. (Θ(1))

iterator begin_breadth()

Returns a breadth-first traversing iterator referring to the root node. (Θ(1))

iterator end_breadth()

Returns a breadth-first traversing iterator referring to one-past-the-last-node of the breadth-first traversal ordering. (Θ(1))

Iterator
class General_tree<Type>::iterator

The iterator class refers to a node within the general tree and allows the programmer to iterate between the referred node and its siblings. Means of finding accessors for the children of the referred node and an accessor to the parent of the referred node allow the programmer to traverse the tree.

int degree()

The degree of the referred node (the number of children). (Θ(1))

int depth()

The depth of the referred node (the length of the path from the root node to the current node). (Θ(1))

int height()

The height of the subtree formed by the referred node and its ancestors. (Θ(1))

int size()

The number of nodes of the subtree formed by the referred node and its ancestors. (Θ(1))

bool root()

Returns true if the currently referenced tree node the root node; otherwise false. (Θ(1))

bool leaf()

Returns true if the currently referenced tree node is a leaf node (having no children); otherwise false. (Θ(1))

iterator parent()

Return an iterator to the parent of the current node. (Θ(1))

void insert( Type const &obj )

Insert a new child to the referred node where the child stores the argument obj. (Θ(d) where d is the depth of the referred node)

iterator begin()

Return an iterator referring to the first child of the referred node. (Θ(1))

iterator end()

Return an iterator referring to the iterative successor of the last child of the referred node. (Θ(1))

iterator &operator++()
++itr

Set the reference to the next sibling (if any) and return a reference to this iterator. (Θ(1))

iterator &operator++( int )
itr++

Set the reference to the next sibling (if any) but return an iterator referring to the original node. (Θ(1))

iterator &operator*()
*itr

Return a reference to the object stored in the referred node. (Θ(1))

bool operator==( iterator const &rhs )

Return true if the two iterators are referring to the same node and false otherwise. (Θ(1))

bool operator!=( iterator const &rhs )

Return true if the two iterators are referring to different nodes and false otherwise. (Θ(1))

Depth-first Traversal
class General_tree<Type>::depth_iterator

The depth_iterator class stores a reference to a node within the tree steps through the tree in a depth-first traversal order.

int degree()

The degree of the referred node (the number of children). (Θ(1))

int depth()

The depth of the referred node (the length of the path from the root node to the current node). (Θ(1))

int height()

The height of the subtree formed by the referred node and its ancestors. (Θ(1))

int size()

The number of nodes of the subtree formed by the referred node and its ancestors. (Θ(1))

bool root()

Returns true if the currently referenced tree node the root node; otherwise false. (Θ(1))

bool leaf()

Returns true if the currently referenced tree node is a leaf node (having no children); otherwise false. (Θ(1))

depth_iterator &operator++()
++itr

Set the reference to the next node following a depth-first traversal of the tree and returns a reference to this iterator. (O(m) where m is the maximum degree of any node within the tree but amortized Θ(1))

depth_iterator &operator++( int )
itr++

Set the reference to the next node following a depth-first traversal of the tree but return an iterator referring to the original node. (O(m) where m is the maximum degree of any node within the tree but amortized Θ(1))

depth_iterator &operator*()
*itr

Return a reference to the object stored in the referred node. (Θ(1))

bool operator==( depth_iterator const &rhs )

Return true if the two depth-first traversal iterators are referring to the same node and false otherwise. (Θ(1))

bool operator!=( depth_iterator const &rhs )

Return true if the two depth-first traversal iterators are referring to different nodes and false otherwise. (Θ(1))

Breadth-first Traversal
class General_tree<Type>::breadth_iterator

The breadth_iterator class stores a reference to a node within the tree steps through the tree in a breadth-first traversal order.

int degree()

The degree of the referred node (the number of children). (Θ(1))

int depth()

The depth of the referred node (the length of the path from the root node to the current node). (Θ(1))

int height()

The height of the subtree formed by the referred node and its ancestors. (Θ(1))

int size()

The number of nodes of the subtree formed by the referred node and its ancestors. (Θ(1))

bool root()

Returns true if the currently referenced tree node the root node; otherwise false. (Θ(1))

bool leaf()

Returns true if the currently referenced tree node is a leaf node (having no children); otherwise false. (Θ(1))

iterator parent()

Return an iterator to the parent of the current node. (Θ(1))

breadth_iterator &operator++()
++itr

Set the reference to the next node following a breadth-first traversal of the tree and returns a reference to this iterator. (O(m) where m is the maximum degree of any node within the tree but amortized Θ(1))

breadth_iterator &operator++( int )
itr++

Set the reference to the next node following a breadth-first traversal of the tree but return an iterator referring to the original node. (O(m) where m is the maximum degree of any node within the tree but amortized Θ(1))

breadth_iterator &operator*()
*itr

Return a reference to the object stored in the referred node. (Θ(1))

bool operator==( breadth_iterator const &rhs )

Return true if the two breadth-first traversal iterators are referring to the same node and false otherwise. (Θ(1))

bool operator!=( breadth_iterator const &rhs )

Return true if the two breadth-first traversal iterators are referring to different nodes and false otherwise. (Θ(1))