Click here to Skip to main content
14,212,717 members
Click here to Skip to main content
Posted 25 Jan 2006


37 bookmarked

A Tree Template Class in C++

Rate this:
3.63 (10 votes)
Please Sign up or sign in to vote.
3.63 (10 votes)
14 Feb 2006        
This article presents a Tree class, which lets you assemble any data type in a tree structure and then work with it using depth-first traversal.


Trees are used very frequently in programming. If you have used them a couple of times, you would have noticed that the code related to tree traversal and child management is pretty much the same in all the cases. For example, this typically would include methods such as:

void Node::add_child (Node* node);
void Node::set_parent (Node* parent);
int Node::num_children();
Node* Node::child (int i); // a get method

Yet, despite this repetitiveness, you have to code it every time you need to assemble a new data type in a tree. In this article, I present a Tree class, which lets you assemble any data type in a tree structure and then work with it using depth-first traversal. I have presently coded only DFS traversal. Later, other traversal styles can be coded in a similar fashion.

Using the class

Let me begin by showing how to use it:

typedef Tree <char> TreeCls;
TreeCls g_tree;

This line declares a Tree whose nodes can contain 'char' data. In a similar way, you can choose whatever 'node type' you want for your tree structure.

In this example, I create a global instance of this tree. At the moment, the tree does not contain any nodes. Now, we need to fill the tree with nodes. Creating this is slightly more involved than using the tree for traversal. Therefore, for now, let us assume that we can fill the tree using a function such as:


After this call, our global tree variable gets filled with some 'char' data. I will go into the details of this function later. Global variables are bad but this is just a snippet. In your code, you will perhaps fill your tree in some other way.

Let us say, we populated our tree with some nodes that may perhaps look like this:


If the above picture does not give a correct 'tree' visualization, then perhaps the following figure may clarify it:

   /  |  \
 /    |    \
2     3     4
     /|\    /\
    / | \  /  \
   5  6 7  8  9

The numbers are just used to assign a 'name' to each node ... so as to identify them.

Now, here is the code to traverse the tree in DFS order:

TreeCls::iterator_dfs it = g_tree.begin();
TreeCls::iterator_dfs it_end = g_tree.end();

while ( it != it_end ) 
    char& c = *it;
    std::cout << c << "\n";


First, you request for an iterator for the first node of the tree using the tree's begin() member function. Later, if you decide to add more iterator types, of course, you will have to change the name of the begin() function to something like begin_dfs().

end() gives you an iterator one past the last node in the DFS order. ++ moves the iterator in DFS order. At any time, you can dereference the iterator to return the reference to the 'char' that constitutes the data of the node.

Now, a little on the implementation details.

Basically, we need to convert a user's data type into a node that can be 'assembled' into a tree. Let us call the user's data type 'T'. The nodes in the tree cannot be of type T. This is because they need to support more operations than are perhaps defined in T. These operations are the ones we mentioned at the very start.

Thus, we define a nested type Node, inside our Tree class. This Node class 'contains' the T data type as a member variable. Rest of the variables of the Node type are for tree traversal and child management.

We also define the nested iterator_dfs data type. It defines the !=, ==, and ++ operators. Its dereference operator, operator *, and arrow operator, operator --> are coded to return the T type of the current node.

How does the iterator keep track of the 'current' node? Simple. It implements a simple DFS search using an explicit stack.

All these details can now be looked in the associated code.

Constructing the tree

Let us now come back to our problem of creating the tree in the first place. Initially, I had wanted to expose an interface that would look something like this:

typedef Tree<int> IntTree;
IntTree tree;

IntTree::iterator_dfs it = tree.begin();
*it = 5;

tree.add_child (it, 10);
tree.add_child (it, 125);

However, during implementation, it proved problematic. This is because of the way operator++() has been implemented. operator()++ for the iterator first collects all the children nodes in a stack and then returns the next node. Adding new nodes at the 'current' iterator could make the DFS-stack inconsistent. I could perhaps destroy the stack and re-traverse it but not only would that be in-efficient, it would be difficult to verify that as well.

Therefore, I decided to let go this approach and instead, made the internal Node class public, even though I had wanted to keep that private (as the applications should not know about the actual node class of the tree).

So to build the tree, we have to use the Node class' raw interface, like this:

TreeCls::Node* node = new TreeCls::Node ( char ('a') ) ;
parent_node -> add_child (node);

parent_node is the node to which you want to add the child. The Node class defines three CTORs; a no argument one, one with an argument of type T (by value), and a third with a parent node and a T type value.

The function read_tree_from_file() is just to make a complete test. It is not part of the Tree class code. It reads the tree description from a text file, which contains the number of children of all the nodes as the nodes are encountered in a DFS traversal. Thus given the file:


The first 3 means the root node has three children. Traverse down to the first child, and it has two children. Both these children have 0 children. Then, the second child has again 0 children. And then the third child has one child. (Note: this is not the same tree as the one shown above.)

The function simply creates a stack, reads a number, creates that many child nodes, and sets the appropriate parent for these new child nodes. As each node is created, it is assigned a char value. This later helps in 'printing' the tree.

The Tree class is in its own .h file. The other file is for testing it. The project was created using VC++ 2005 Express.

You are free to use this code without any restrictions in your efforts. All comments and criticism are welcome.


This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


About the Author

Ahmed Qazi
Web Developer
United States United States
Biography: Still in the making!

Comments and Discussions

GeneralMemery Leaks Pin
0898908829-Jan-07 20:07
member0898908829-Jan-07 20:07 
GeneralRe: Memery Leaks Pin
Grotichaz Morek9-Mar-07 5:08
memberGrotichaz Morek9-Mar-07 5:08 
GeneralRe: Memery Leaks Pin
Ahmed Qazi28-Mar-07 11:06
memberAhmed Qazi28-Mar-07 11:06 
GeneralGeneral Question regarding trees Pin
wdhough23-Feb-06 6:06
memberwdhough23-Feb-06 6:06 
GeneralRe: General Question regarding trees Pin
wdhough23-Feb-06 6:07
memberwdhough23-Feb-06 6:07 
GeneralRe: General Question regarding trees Pin
Ahmed Qazi24-Feb-06 6:33
memberAhmed Qazi24-Feb-06 6:33 
GeneralRe: General Question regarding trees Pin
wdhough24-Feb-06 6:40
memberwdhough24-Feb-06 6:40 
Generalproblem compiling under VS 2005 Pin
volker bijewitz12-Feb-06 20:06
membervolker bijewitz12-Feb-06 20:06 
GeneralRe: problem compiling under VS 2005 Pin
Ahmed Qazi14-Feb-06 9:07
memberAhmed Qazi14-Feb-06 9:07 
GeneralRe: problem compiling under VS 2005 Pin
volker bijewitz14-Feb-06 21:32
membervolker bijewitz14-Feb-06 21:32 
GeneralRelated Structures Pin
Sean Parent31-Jan-06 7:50
memberSean Parent31-Jan-06 7:50 
GeneralSTL implementation Pin
yafan27-Jan-06 9:57
memberyafan27-Jan-06 9:57 
GeneralRe: STL implementation Pin
Pierre Couderc30-Jan-06 19:37
memberPierre Couderc30-Jan-06 19:37 
QuestionWhy not use STL? Pin
Shawn Poulson26-Jan-06 2:55
memberShawn Poulson26-Jan-06 2:55 
AnswerRe: Why not use STL? Pin
Ahmed Qazi26-Jan-06 7:13
memberAhmed Qazi26-Jan-06 7:13 
AnswerRe: Why not use STL? Pin
le_tot30-Jan-06 23:06
memberle_tot30-Jan-06 23:06 
There is actually a tree implementation in the STL called core::tree.
it's not in the standard but many stl algorithm work on this container.


General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Layout: fixed | fluid

Article Copyright 2006 by Ahmed Qazi
Everything else Copyright © CodeProject, 1999-2019

Server Web01
Version 2.8.190619.2