Chapter 6. Programming with Templates

When Bjarne Stroustrup worked out the original C++ language design for templates, he referred to them as parameterized types: "parameterized" because they are factored out of the template definition, and "types" because each class or function template typically varies by one or a set of types being operated on or contained. The actual type is later specified by the user.

Stroustrup later changed the name to the more general template. A single template definition serves as a prescription for the automatic generation of a unique instance of a function or class based on a user-specified value or type.

Although we have extensively used class templates, such as the vector and string classes, we haven't yet implemented one of our own. We do that in this chapter, walking through the implementation of a binary tree class template.

If you're unfamiliar with the binary tree abstraction, the following is a brief review. A tree consists of nodes and vertices, or links, connecting the nodes. A binary tree maintains two links between nodes, typically called the left and right child. The tree has a first node called the root. Each left or right child may itself serve as root to a subtree. A node without children is called a leaf node.

Our binary tree implementation consists of two classes: a BinaryTree class, which holds a pointer to the root, and a BTnode helping class, which holds both the actual value and the left and right child links. It is the type of the node value that we parameterize.

What are the operations our BinaryTree must support? Users must both insert and remove an element as well as find whether an element is present, clear all tree elements, and print the tree in one of three traversal algorithms: inorder, preorder, or postorder.

In our implementation, the first value inserted into an empty tree becomes the root. Each subsequent value is inserted so that all values less than the root are placed in the root's left subtree. All values greater than the root are placed in the root's right subtree. A value occurs only once within a tree. An occurrence count keeps track of multiple insertions of the same value. For example, given the code sequence

BinaryTree<string> bt; 


bt.insert( "Piglet" ); 

Piglet becomes the root of our binary tree. Suppose that we next insert Eeyore:

bt.insert( "Eeyore" ); 

Because Eeyore is alphabetically less than Piglet, Eeyore becomes the left child of Piglet. Then suppose we next insert Roo:

bt.insert( "Roo" ); 

Because Roo is greater than Piglet, Roo becomes the right child of Piglet, and so on. Let's complete our tree by inserting the following elements:

bt.insert( "Tigger" ); 


bt.insert( "Chris" ); 


bt.insert( "Pooh" ); 


bt.insert( "Kanga" ); 

The resulting binary tree is pictured in Figure 6.1. In this example, Chris, Kanga, Pooh, and Tigger are leaf nodes.

Each traversal algorithm begins with the root node. In a preorder traversal, the node is displayed; then the left child is visited and then the right child. In an inorder traversal, the left child is first visited, then the node is displayed, and then the right child is visited. In a postorder traversal, the left child is visited; then the right child is visited, and then the node is displayed. For the tree in Figure 6.1, the three traversal algorithms display the nodes as follows:

// preorder traversal of Figure 6.1 binary tree 


Piglet, Eeyore, Chris, Kanga, Roo, Pooh, Tigger 





// inorder traversal of Figure 6.1 binary tree 


Chris, Eeyore, Kanga, Piglet, Pooh, Roo, Tigger 





// postorder traversal of Figure 6.1 binary tree 


Chris, Kanga, Eeyore, Pooh, Tigger, Roo, Piglet