Introduction
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);
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:
read_tree_from_file();
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:
1
|--2
|--3
|--5
|--6
|--7
|--4
|--8
|--9
If the above picture does not give a correct 'tree' visualization, then perhaps the following figure may clarify it:
1
/|\
/ | \
/ | \
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";
++it;
}
Explanation
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);
it++;
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:
3
2
0
0
0
1
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.
