ntree - an N-ary Tree Container

Introduction

This component is an STL-like template class which implements an N-ary tree data structure.

Instantiation

The ntree template takes a single type as its template argument:

template<typename T> class ntree

This type is the type to be stored on each node of the tree structure. For example, a variable representing a tree of strings can be created like this:

ntree<string> strings;

Basics - Nodes and Iterators

An ntree is a tree of nodes, each one containing the user type (represented by T in the template declaration). Each node also contains hidden field which you don't need to know about but which implement the tree structure.

Like other STL containers, the ntree uses an iterator as a pseudo-pointer or handle to a node. These iterators act like pointers when they are dereferenced and give access to the user data (type T) associated with that node.

There are two basic iterator types defined in ntree:

These names follow the normal conventions for STL classes. An iterator is used to act on a non-const ntree and can modify it, whereas the const_iterator act on a const ntree and can only perform read-only operations on it.

However, the iterator concept starts to break down a bit here and the ntree iterator does not allow increment or decrement operations to step through the tree. However, you should see the prefix_iterator and postfix_iterator defined in the next section.

Iterators act very much like STL list iterators in that changing an ntree does not invalidate iterators except for those pointing to nodes that have been erased from the tree.

Since there are no increment or decrement operations on an iterator, other methods are provided to allow tree traversal. Here's the traversal functions for iterators:

iterator ntree::root(void);
unsigned ntree::children(iterator);
iterator ntree::child(iterator, unsigned child);
iterator ntree::parent(iterator);

Note: These methods are members of the ntree class, not the iterator class.

Thus, you can traverse a tree by first getting the root node, then iterating through its child nodes. Alternatively, you can walk up the tree from a node to the root by following the parent pointers. Children are accessed by a numeric offset starting at 0. Thus a node with 4 children will have offsets of 0..3 to access them.

There's an identical set of these functions acting on const_iterator of course.

STLplus iterators are slightly different to STL iterators in that they know which container they belong to. When an iterator is first declared, but not assigned to, it is known as a null iterator. Then, when it is assigned to so that it points to a node in the tree, it is known as a valid iterator. If the iterator is made to point off the edge of the tree - for example the parent of the root node, then it becomes an end iterator.

This concept is similar to STL iterators like the list iterator, where an iterator that walks off the end of the list becomes an end iterator. However, the STL has no concept of a null iterator and therefore no direct equivalent of a valid iterator.

The iterator has a set of functions for testing these conditions:

bool iterator::null(void) const;
bool iterator::end(void) const;
bool iterator::valid(void) const;

Note that these functions are members of the iterator class, not the ntree class.

Exactly one of these conditions will always be true, since the iterator must be one of null, end or valid.

Only a valid iterator can be dereferenced to access the node type T pointed to by the iterator. Any attempt to dereference an end or null iterator will result in an exception being thrown. See the section below on Exceptions to see which.

Example:

ntree<string> data;
...
ntree<string>::iterator i = data.root();
if (i.valid())
{
  for (unsigned j = 0; j < i->length(); j++)
  ...
}

When dereferencing an iterator, you access the user data type T. In the above examples, this is type std::string. A non-const iterator gives access to a reference to this type which can be assigned to as well as read. Thus you can change the contents of a node. However, a const_iterator gives access to a const reference which cannot be assigned to but can be read. This is how all STL-like iterators work.

Manipulating Trees

When you declare an ntree, the result is an empty tree - namely a tree with a null root. Typically, the root has to be handled slightly differently to other nodes, since it does not have a parent node. This functionality is provided by the insert(T) function, where T is the user data type as usual:

iterator ntree::insert(const T&);

This clears any previous tree contents, creates a root node and assigns the data in type T to this node. It returns an iterator to the root node.

Once there is a root node, other nodes are added by specifying the parent node to add it to and the index to add it into the child pointers. For example, inserting at position 0 prepends it to the list of child nodes, whilst inserting at the position indicated by the current number of children will append it to the list. For example, inserting at position 4 for a node with 4 children (offsets 0..3 remember) will append it to the list. For convenience there is an append function to make this particular action simpler. Thus, there are two functions for adding a non-root node:

iterator ntree::insert(iterator parent, unsigned offset, const T& node_data);
iterator ntree::append(iterator parent, const T& node_data);

It is also possible to add a copy of another tree to a node, thus adding a whole subtree in one go. Once again, there is an append function for the most common kind of insertion:

iterator ntree::insert(iterator, unsigned, const ntree<T>&);
iterator ntree::append(iterator, const ntree<T>&);

By the way, adding a copy of another tree as the root of this tree is done by simple assignment of one tree to another - assignment does a copy.

There are three erase functions: one to erase the whole tree, one to erase a node and its children and one to erase a single child of a node:

void ntree::erase(void);
void ntree::erase(iterator);
void ntree::erase(iterator, unsigned);

The difference between the last two maybe needs more explanation. The first form erases the node pointed to by the iterator. It removes the node from its parent's child list and deletes all of its children. The second form is effectively the same, but seen from the point of view of the parent node. In this case, a single child node indicated by the unsigned offset is removed from the node's child list and deleted. In all cases the whole subtree below the deleted node is also deleted.

To copy a subtree of an ntree, use the subtree functions:

ntree<T> ntree::subtree(void);
ntree<T> ntree::subtree(iterator);
ntree<T> ntree::subtree(iterator, unsigned);

The first function makes a subtree out of the whole tree, effectively making an exact copy of the whole tree. The second form copies the tree starting from the node pointed to by the iterator. Thus the resulting tree will have a copy of this node as its root. The third form copies the tree one level down from this, copying from the designated child of the pointed-to node.

The final set of functions allow parts of an ntree to be cut off and made into new trees:

ntree<T> ntree::cut(void);
ntree<T> ntree::cut(iterator);
ntree<T> ntree::cut(iterator, unsigned);

These are very similar to the subtree functions except that they are destructive. They remove part or all of the source tree. The first cuts the whole tree leaving it empty and creating a new tree which contains all of the old tree. The second cuts out the designated node and its subtree, removing it from its parent node's child list. The last removes a child and makes a new tree out of it.

Traversal Iterators

Earlier it was pointed out that ntree iterators are only used to point to nodes, they cannot be used to iterate through the tree (so making the name iterator a bit inappropriate, but I did that for consistency with other data structures). There are in fact two pairs of iterators which can be used to traverse an ntree. These are the prefix_iterator and the postfix_iterator. As usual with STL-like containers, they occur in non-const and const form, giving four iterators in all:

These iterators are used just like other STL-like iterators, except bear in mind that only forward traversals are possible, by which I mean that only the ++ operator is provided.

The iteration is started by prefix_begin() for prefix iterators and postfix_begin() for postfix iterators. Similarly the end of iteration is tested by comparing with prefix_end() or postfix_end(). Specifically, the functions are:>/p>

const_prefix_iterator ntree::prefix_begin(void) const;
prefix_iterator ntree::prefix_begin(void);
const_prefix_iterator ntree::prefix_end(void) const;
prefix_iterator ntree::prefix_end(void);

const_postfix_iterator ntree::postfix_begin(void) const;
postfix_iterator ntree::postfix_begin(void);
const_postfix_iterator ntree::postfix_end(void) const;
postfix_iterator ntree::postfix_end(void);

An example:

ntree<string> data;
...
for (ntree<string>::prefix_iterator i = data.prefix_begin(); i != data.prefix_end(); i++)
{
  ...
}

These traversal iterators allow access to the node data just as the simple iterator does - by dereferencing the iterator. The iterators also have the tests for end, null and valid iterators, and it is only legal to dereference a valid iterator.

However, you cannot use the traversal iterators to access other information from the ntree class such as the parent node or the child nodes, since the functions providing this information only take simple iterators. For this reason, all the traversal iterators have a member function called simplify(). For example, a prefix_iterator simplifies to an iterator and a const_postfix_iterator simplifies to a const_iterator. The full set of simplify functions are:

iterator prefix_iterator::simplify(void) const;
const_iterator const_prefix_iterator::simplify(void) const;
iterator postfix_iterator::simplify(void) const;
const_iterator const_postfix_iterator::simplify(void) const;

Once the simple iterator has been extracted, it can be used to access other information from the ntree class.

Exceptions Thrown by Ntree

When errors are discovered within an ntree, it resorts to throwing an exception to indicate that error.

There are three standard STLplus exceptions that can be thrown by ntree, all indicating a misuse of the iterators:

null_dereference - logic_error
This is used to indicate that an iterator which is null has been dereferenced. You should always be sure that iterators are non-null before using the * or -> operators.
end_dereference - logic_error
This is used to indicate that an iterator that is pointing to an end element has been dereferenced. In line with STL conventions, the end iterator points to the element after the last element in a container, so dereferencing such an iterator is illegal (the memory pointed to will be unconstructed). In this case this happens when accessing the parent of the root node or using the traversal iterators and walking off the end of the tree.
wrong_object - logic_error
This is used to indicate that an iterator which was created by one container has been used in a different container. For example, if you have two ntree objects in your program, create an iterator from one ntree and then use it in another, then this will throw the wrong_object exception.

These exceptions are common to all STLplus iterators and are explained in the STLplus exceptions policy.

In addition, an ntree can throw one C++ standard exception related to the misuse of integer indices:

std::out_of_range - logic_error
Thrown when an integer offset is used to access a child, where the offset is out of range of the children.