1. Introduction

One of the most highly respected computer scientists of the twenty-first century, Dr. Donald Knuth, describes trees as,

"the most important nonlinear structures that arise in computer algorithms." [1]

As Knuth argues above, trees are important. Unfortunately, trees are also complex. In his revered series of computer science books, The Art of Computer Programming, Dr. Knuth dedicates nearly one-fifth of his first volume solely to the discussion of trees, explaining their driving concepts and numerous uses. As detailed by Knuth in his text, the concepts surrounding trees are so vast it takes a great deal of energy to convey them correctly. It is my hope that this installment of the C++ tree series will explain the core::tree<> design and implementation correctly (and clearly) that when finishing this article, the core::tree<> design, implementation and use will seem simple and natural.

This article is presented in the following fashion:

1. Introduction
2. Terminology
3. Concept of Design
4. Subtleties of the core::tree<>
5. The core::tree<> API
6. Conclusion
7. Acknowledgements
8. References
9. core::tree<> and core::multitree<> source

A detailed analysis of the design concepts used to build the core::tree<> and a thorough explanation of how those design concepts fit together, will be given. Moreover, all the current interfaces for the core::tree<> and the core::tree<>::iterator will be explained in detail. Coding examples are provided using the core::tree<> throughout the article.

2. Terminology

The acronym "STL" refers to C++'s Standard Template Library [4].

The term "single-level container" refers to a container with a single-level, such as a vector, set, list, deque, or any of the STL containers -- not a tree container, which can potentially contain many levels.

The terms "tree" and "subtree" will be used interchangeably throughout this article. In general, both terms refer to the same concept, except; 1) a tree contains a root node that has no parent and 2) a subtree has a root node that has a parent and, thus, is a child of a parent tree (as noted by Knuth's definition of trees below).

The term "node" will be used to identify the wrapper of a single element within a container, including tree containers.

The term "branch" will be used to identify a single node within a tree container and only a tree container.

The term "tree" and "subtree" will follow Knuth's definition from The Art of Computer Programming [2]:

A finite set T of one or more nodes such that:

1. there is one specially designated node called the root of the tree, root(T); and
2. the remaining nodes (excluding the root) are partitioned into m >= 0 disjoint sets T1, ..., Tm, and each of these sets in turn is a tree. The trees T1, ..., Tm are called the subtrees of the root.

Figure 2.1: Simple Tree

In short, the above definition says "trees are defined by trees". Truthfully, there is no distinction between a node in a tree and the tree itself (as all nodes in a tree are trees themselves). Knuth notes that his definition of trees is a recursive one, as he defines trees in terms of trees. He further explains that trees can be defined in nonrecursive ways, yet it is most appropriate to define trees recursively as recursion is an innate characteristic of tree structures [3].

Figure 2.1 illustrates the basic concepts of a tree. All nodes within the blue border make up the tree contained by node 1's root. All nodes within the green border on the left make up the subtree contained by node 2's root. All nodes within the green border on the right make up the subtree contained by node 3's root.

Node 1 is the root node of the entire tree. There is only one root node for the tree in its entirety. However, for each subtree there is a root node for that subtree, therefore each node of a tree is considered a root node for the subtree it creates (even if that subtree contains only the root node) [11].

For example, node 2 is the root node for the subtree created from 2, 4, 5 and 6, and node 3 is the root node for the subtree created from 3, 7, 8 and 9. Node 4 is also the root node for the subtree it creates, however, its subtree consists only of itself (node 4). The same is true of nodes 5, 6, 7, 8 and 9.

Concept of Design