With the help of a program explain the depth first traversal of a tree?
Refer to the following code and example output below.
#include<iostream>
#include<time.h>
#include<queue>
#include<stack>
class tree
{
private:
struct node
{
static unsigned s_id; // static id
unsigned id; // instance id
unsigned data; // instance data
unsigned depth; // depth of node
node* left; // pointer to left node (may be NULL)
node* right; // pointer to right node (may be NULL)
node (unsigned num, unsigned depth): data (num), left (NULL),
right (NULL), id (s_id++), depth (depth) {}
~node () { delete (left); delete (right); }
void insert (unsigned num)
{
if (num < data)
{
if (!left)
left = new node (num, depth+1);
else
left->insert (num);
}
else
{
if (!right)
right = new node (num, depth+1);
else
right->insert (num);
}
}
void print ()
{
std::cout<<"ID: "<<id<<" Depth:
"<<depth<<" Data: "<<data<<std::endl;
}
void print_sorted ()
{
if (left)
left->print_sorted ();
print();
if (right)
right->print_sorted ();
}
};
node* m_root;
public:
tree (): m_root (NULL) {}
~tree (){ delete (m_root); }
void insert (unsigned num)
{
if (!m_root)
m_root = new node (num, 0);
else
m_root->insert (num);
}
void print_sorted ()
{
std::cout<<"Sorted-order
traversal\n"<<std::endl;
if (m_root)
{
m_root->print_sorted ();
std::cout<<std::endl;
}
}
void print_breadth_first ()
{
std::cout<<"Breadth-first
traversal\n"<<std::endl;
std::queue<node*> q;
if (m_root)
{
// enque the root
q.push (m_root);
// repeat while the queue is not empty
while (!q.empty ())
{
// dequeue the first node
node* n = q.front ();
q.pop ();
// report the node
n->print ();
// enqueue left and right nodes
if (n->left)
q.push (n->left);
if (n->right)
q.push (n->right);
}
std::cout<<std::endl;
}
else
std::cout<<"The tree is empty!\n"<<std::endl;
}
void print_depth_first ()
{
std::cout<<"Depth-first traversal\n"<<std::endl;
std::stack<node*> s;
if (m_root)
{
// stack the root
s.push (m_root);
// repeat while the stack is not empty
while (!s.empty())
{
// unstack the top node
node* n = s.top ();
s.pop ();
// report the node
n->print ();
// stack left and right nodes
if (n->right)
s.push (n->right);
if (n->left)
s.push (n->left);
}
std::cout<<std::endl;
}
else
std::cout<<"The tree is empty!\n"<<std::endl;
}
};
// initialise static data
unsigned tree::node::s_id = 0;
int main()
{
srand((unsigned) time(NULL));
// create tree with 10 random numbers
tree t;
for(unsigned i=0; i<10; ++i)
t.insert (rand ());
t.print_sorted ();
t.print_breadth_first ();
t.print_depth_first ();
}
Example output:
Sorted-order traversal
ID: 6 Depth: 2 Data: 334
ID: 4 Depth: 1 Data: 2335
ID: 0 Depth: 0 Data: 12490
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
ID: 3 Depth: 3 Data: 23160
ID: 2 Depth: 2 Data: 23786
ID: 8 Depth: 3 Data: 24171
ID: 1 Depth: 1 Data: 24598
ID: 7 Depth: 2 Data: 30731
Breadth-first traversal
ID: 0 Depth: 0 Data: 12490
ID: 4 Depth: 1 Data: 2335
ID: 1 Depth: 1 Data: 24598
ID: 6 Depth: 2 Data: 334
ID: 2 Depth: 2 Data: 23786
ID: 7 Depth: 2 Data: 30731
ID: 3 Depth: 3 Data: 23160
ID: 8 Depth: 3 Data: 24171
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
Depth-first traversal
ID: 0 Depth: 0 Data: 12490
ID: 4 Depth: 1 Data: 2335
ID: 6 Depth: 2 Data: 334
ID: 1 Depth: 1 Data: 24598
ID: 2 Depth: 2 Data: 23786
ID: 3 Depth: 3 Data: 23160
ID: 5 Depth: 4 Data: 15590
ID: 9 Depth: 5 Data: 18484
ID: 8 Depth: 3 Data: 24171
ID: 7 Depth: 2 Data: 30731
Each node reports its ID, depth and data. The ID tells us the
sequence the nodes were created, where the node with ID 0 is always
the root. The depth tells us the level within the tree where the
node exists, such that the root is on level 0. With this
information it is possible to draw a graph of the tree and thus
better understand the order in which nodes are processed.
The first listing shows the nodes in ascending order by data.
With binary search trees this is the normal method of
traversal.
The second listing shows a breadth-first traversal, where each
level is processed in turn, from left to right.
The final listing shows a depth-first traversal where we follow
left nodes before right nodes.
You will notice that the implementation of breadth-first and
depth-first are fairly similar, the only real difference being that
breadth-first employs a queue while depth-first employs a stack.
The nature of a stack also means we must push right nodes before
left nodes to ensure left nodes are processed before right
nodes.
At first glance there doesn't appear to be much merit in either
breadth-first or depth-first traversal. However, the example merely
serves to show the difference between all the methods of traversal.
When considering more complex graphs or maps, it may be
advantageous to search through all the vertices that form an edge
with a particular vertex (breadth-first) or to examine all the
edges between one vertex and another vertex, where several routes
might be available (depth-first). Both depth-first and
breadth-first have practical applications in network routing and
satellite navigation, where maps and charts must be graphed and
traversed in a more logical manner than would otherwise be possible
with sorted-order traversal.
