Tree Container in C++ - n ary Tree - Part 2

• Download code
• Please refer to my blog(www.brainlesslabs.com) for recent and updated changes to the code.
• Table of Contents

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 );
  // Populate Tree
  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/* argc*/, char ** /*argv[]*/ ) {
    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;
  }

  //iterativePreorder( node )
  //  parentStack = empty stack
  //  while ( not parentStack.isEmpty( ) or node != null )
  //    if ( node != null )
  //      visit( node )
  //      if ( node.right != null ) parentStack.push( node.right )
  //        node = node.left
  //      else
  //      node = parentStack.pop( )
  void increment( ) {
    if ( stack( ).empty( ) ) {
      _cur.reset( );
      return;
    }

    // _cur already points to the top, so just pop it
    stack( ).pop( );
    // Right child is pushed before left child to make sure that left subtree is processed first.
    for ( auto it = cur( ).child_node_rtol_begin( );
          it != cur( ).child_node_rtol_end( );
          ++it ) {
      stack( ).push( *it );
    }

    // If the stack is not empty then only assign 
    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;
  }
};// PreOrder Tree Iterator End

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.

//=====================================================================
// PostOrder Tree Iterator 2Stacks
//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 ).
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;
  }

  // Browse the second stack
  void increment( ) {
    if ( stack2( ).empty( ) ) {
      _cur.reset( );
    }
    else {
      cur( top( ) );
      stack2( ).pop( );
    }
  }

  // http://www.geeksforgeeks.org/iterative-postorder-traversal-using-stack/
  //1. Push root to first stack.
  //2. Loop while first stack is not empty
  //  2.1 Pop a node from first stack and push it to second stack
  //  2.2 Push left and right children of the popped node to first stack
  //3. Print contents of second stack
  void createSecondStack( ) {
    // Populate the second stack
    while ( !stack1( ).empty( ) ) {
      NodeRef node = stack1( ).top( );
      stack1( ).pop( );
      for ( auto& n : node ) {
        stack1( ).push( n );
      }
      stack2( ).push( node );
    }

    //Free stack1, we dont need it further
    _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;
  }
};
// PostOrder Tree Iterator 2Stacks End

Breadth First Iteration

This is called level order traversal. 

In this, we visit all nodes in N^th level before visiting the nodes in the N+1^th level.

//=====================================================================
// LevelOrder Tree Iterator
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;
  }

  //1) Create an empty queue q
  //2) temp_node = root /*start from root*/
  //3) Loop while temp_node is not NULL
  //  a) print temp_node->data.
  //  b) Enqueue temp_node’s children( first left then right children ) to q
  //  c) Dequeue a node from q and assign it’s value to temp_node
  void increment( ) {
    if ( !_cur ) {
      return;
    }

    if ( queue( ).empty( ) ) {
      _cur.reset( );
    }
    else {
      // Pop it, _cur already contains it
      queue( ).pop( );
      for ( auto& n : cur( ) ) {
        queue( ).push( n );
      }
      // Push only if there is something in the queue
      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;
  }
};// LevelOrder Tree Iterator End

References

• Level Order Traversal 
• Post Order Traversal
• Pre Order Traversal
• Tree Traversals
• More Tree Algorithms

History

• 31^st March, 2015: Initial version