Introduction
In the previous post, we saw how to implement and traverse a tree node. In this tip, we will see how to implement various traversal mechanisms for a general n ary tree structure.
By the end of this tip, we should be able to compile and run the following functions:
#include "containers/tree/NTree.hpp"
#include <iostream>
typedef blib::container::tree::Node<int> Node;
typedef blib::container::tree::Tree<Node> Tree;
void createTree( Tree& t ) {
Node l11, l12, l21, l22, l31, l32;
l11.data( 11 ); l12.data( 12 ); l21.data( 21 ); l22.data( 22 ); l31.data( 31 ); l32.data( 32 );
Node l1, l2, l3;
l1.data( 1 ); l2.data( 2 ); l3.data( 3 );
l1.addChild( l11 ); l1.addChild( l12 );
l2.addChild( l21 ); l2.addChild( l22 );
l3.addChild( l31 ); l3.addChild( l32 );
Node r;
r.data( 0 );
r.addChild( l1 ); r.addChild( l2 ); r.addChild( l3 );
t.root( r );
}
void preOrderTest( Tree& t ) {
std::cout << "preOrderTest start" << std::endl;
for ( auto it = t.pre_order_begin( );
it != t.pre_order_end( );
++it ) {
auto n = *it;
if ( n ) {
std::cout << n.data( ) << " ";
}
}
std::cout << "\npreOrderTest end" << std::endl;
}
void postOrderTest( Tree& t ) {
std::cout << "postOrderTest start" << std::endl;
for ( auto it = t.post_order_begin( );
it != t.post_order_end( );
++it ) {
auto n = *it;
if ( n ) {
std::cout << n.data( ) << " ";
}
}
std::cout << "\npostOrderTest end" << std::endl;
}
void levelOrderTest( Tree& t ) {
std::cout << "levelOrderTest start" << std::endl;
for ( auto it = t.level_order_begin( );
it != t.level_order_begin( );
++it ) {
auto n = *it;
if ( n ) {
std::cout << n.data( ) << " ";
}
}
std::cout << "\nlevelOrderTest end" << std::endl;
}
int main( int, char ** ) {
Tree t;
createTree( t );
preOrderTest(t );
postOrderTest( t );
levelOrderTest( t );
}
Different Kind of Traversals
For a general tree, we have depth first traversal and breadth first traversal.
Depth First Traversal
Pre Order Traversal
- Display the data part of root element (or current element).
- Traverse the left subtree by recursively calling the pre-order function.
- Traverse the right subtree by recursively calling the pre-order function.
Below is the implementation:
template<typename NodeType>
class pre_order_iterator :
public boost::iterator_facade
< pre_order_iterator<NodeType>, NodeType, boost::forward_traversal_tag > {
private:
typedef NodeType Node;
typedef typename Node::ValueType ValueType;
typedef typename Node::ValueRef ValueRef;
typedef typename Node::ConstValueRef ConstValueRef;
typedef typename Node::NodeRef NodeRef;
typedef typename Node::ConstNodeRef ConstNodeRef;
typedef typename Node::NodeHandle NodeHandle;
typedef typename Node::NodeAllocator NodeAllocator;
typedef typename Node::DataAllocator DataAllocator;
typedef typename Node::child_node_ltor_iterator child_node_ltor_iterator;
typedef std::reference_wrapper<Node> NodeRefWrapper;
typedef std::stack<NodeRefWrapper, std::vector<NodeRefWrapper>> Stack;
typedef pre_order_iterator<Node> SelfType;
private:
friend class boost::iterator_core_access;
std::shared_ptr<Stack> _stack;
std::shared_ptr<Node> _cur;
public:
pre_order_iterator( ) {}
pre_order_iterator( NodeRef aRoot ) {
_stack = std::make_shared<Stack>( );
_cur = std::make_shared<Node>( aRoot );
stack( ).push( aRoot );
}
pre_order_iterator( pre_order_iterator const& aOther ) {
_stack = aOther._stack;
_cur = aOther._cur;
}
private:
NodeRef dereference( ) const {
return cur( );
}
bool equal( SelfType const& aOther ) const {
bool ret = false;
if ( aOther._cur == _cur ) {
ret = true;
}
return ret;
}
void increment( ) {
if ( stack( ).empty( ) ) {
_cur.reset( );
return;
}
stack( ).pop( );
for ( auto it = cur( ).child_node_rtol_begin( );
it != cur( ).child_node_rtol_end( );
++it ) {
stack( ).push( *it );
}
if ( !stack( ).empty( ) ) {
cur( top( ) );
}
else {
_cur.reset( );
}
}
NodeRef top( ) {
return stack( ).top( );
}
Stack& stack( ) {
return *_stack;
}
NodeRef cur( ) const {
return *_cur;
}
void cur( ConstNodeRef aNode ) const {
*_cur = aNode;
}
};
In Order Traversal
We do not have this for unordered n ary trees. So this is not implemented.
Post Order Traversal
- Traverse the left subtree by recursively calling the post-order function.
- Traverse the right subtree by recursively calling the post-order function.
- Display the data part of root element (or current element).
Below is the sample implementation using 2 stacks. There is a 1 stack implementation too. I will update it in future. I am using it because it is relatively simpler.
template<typename NodeType>
class post_order_2stack_iterator :
public boost::iterator_facade < post_order_2stack_iterator<NodeType>,
NodeType, boost::forward_traversal_tag > {
private:
typedef NodeType Node;
typedef typename Node::ValueType ValueType;
typedef typename Node::ValueRef ValueRef;
typedef typename Node::ConstValueRef ConstValueRef;
typedef typename Node::NodeRef NodeRef;
typedef typename Node::ConstNodeRef ConstNodeRef;
typedef typename Node::NodeHandle NodeHandle;
typedef typename Node::NodeAllocator NodeAllocator;
typedef typename Node::DataAllocator DataAllocator;
typedef typename Node::child_node_ltor_iterator child_node_ltor_iterator;
typedef std::reference_wrapper<Node> NodeRefWrapper;
typedef std::stack<NodeRefWrapper, std::vector<NodeRefWrapper>> Stack;
typedef post_order_2stack_iterator<Node> SelfType;
private:
friend class boost::iterator_core_access;
std::shared_ptr<Stack> _stack1;
std::shared_ptr<Stack> _stack2;
std::shared_ptr<Node> _cur;
public:
post_order_2stack_iterator( ) {}
post_order_2stack_iterator( NodeRef aRoot ) {
_stack1 = std::make_shared<Stack>( );
_stack2 = std::make_shared<Stack>( );
_cur = std::make_shared<Node>( aRoot );
stack1( ).push( aRoot );
createSecondStack( );
}
post_order_2stack_iterator( post_order_2stack_iterator const& aOther ) {
_stack1 = aOther._stack1;
_stack2 = aOther._stack2;
_cur = aOther._cur;
}
private:
NodeRef dereference( ) const {
return cur( );
}
bool equal( SelfType const& aOther ) const {
bool ret = false;
if ( aOther._cur == _cur ) {
ret = true;
}
return ret;
}
void increment( ) {
if ( stack2( ).empty( ) ) {
_cur.reset( );
}
else {
cur( top( ) );
stack2( ).pop( );
}
}
void createSecondStack( ) {
while ( !stack1( ).empty( ) ) {
NodeRef node = stack1( ).top( );
stack1( ).pop( );
for ( auto& n : node ) {
stack1( ).push( n );
}
stack2( ).push( node );
}
_stack1.reset( );
if ( !stack2( ).empty( ) ) {
cur( top( ) );
stack2( ).pop( );
}
}
NodeRef top( ) {
return stack2( ).top( );
}
Stack& stack1( ) {
return *_stack1;
}
Stack& stack2( ) {
return *_stack2;
}
NodeRef cur( ) const {
return *_cur;
}
void cur( NodeRef aNode ) const {
*_cur = aNode;
}
};
Breadth First Iteration
This is called level order traversal.
In this, we visit all nodes in Nth level before visiting the nodes in the N+1th level.
template<typename NodeType>
class level_order_iterator :
public boost::iterator_facade < level_order_iterator<NodeType>,
NodeType, boost::forward_traversal_tag > {
private:
typedef NodeType Node;
typedef typename Node::ValueType ValueType;
typedef typename Node::ValueRef ValueRef;
typedef typename Node::ConstValueRef ConstValueRef;
typedef typename Node::NodeRef NodeRef;
typedef typename Node::ConstNodeRef ConstNodeRef;
typedef typename Node::NodeHandle NodeHandle;
typedef typename Node::NodeAllocator NodeAllocator;
typedef typename Node::DataAllocator DataAllocator;
typedef typename Node::child_node_ltor_iterator child_node_ltor_iterator;
typedef std::reference_wrapper<Node> NodeRefWrapper;
typedef std::queue<NodeRefWrapper> Queue;
typedef level_order_iterator<Node> SelfType;
private:
friend class boost::iterator_core_access;
std::shared_ptr<Queue> _queue;
std::shared_ptr<Node> _cur;
public:
level_order_iterator( ) {}
level_order_iterator( NodeRef aRoot ) {
_queue = std::make_shared<Queue>( );
_cur = std::make_shared<Node>( aRoot );
queue( ).push( aRoot );
}
level_order_iterator( level_order_iterator const& aOther ) {
_queue = aOther._queue;
_cur = aOther._cur;
}
private:
NodeRef dereference( ) const {
return cur( );
}
bool equal( SelfType const& aOther ) const {
bool ret = false;
if ( aOther._cur == _cur ) {
ret = true;
}
return ret;
}
void increment( ) {
if ( !_cur ) {
return;
}
if ( queue( ).empty( ) ) {
_cur.reset( );
}
else {
queue( ).pop( );
for ( auto& n : cur( ) ) {
queue( ).push( n );
}
if ( !queue( ).empty( ) ) {
cur( queue( ).front( ) );
}
else {
_cur.reset( );
}
}
}
Queue& queue( ) {
return *_queue;
}
NodeRef cur( ) const {
return *_cur;
}
void cur( ConstNodeRef aNode ) const {
*_cur = aNode;
}
};
References
History
- 31st March, 2015: Initial version
I like to explore different aspects of technology. Try new things, and get delighted. My interests are programming language, and Imaging. But its not hard to work on other things also. Algorithms delight me over a coffee break.
I basically code in C++, but JAVA is not so alien for me. I know few scripting languages also. Basically I feel that knowing a programing language is just a matter of getting introduced to it.
For my other articles check my blog on homepage:
http://brainlesslabs.com/
https://github.com/BrainlessLabsInc
http://www.luxrender.net/en_GB/authors_contributors - SMISRA