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

BrainlessLabs.com

4.59/5 (5 votes)

Mar 31, 2015

MPL

1 min read

25114

This tip describes a n ary tree structure. We will see how traversal works.

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

History

31^st March, 2015: Initial version