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

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

Introduction

This series of articles will describe various types of trees and their implementation in C++. A tree is a hierarchical data structure. A tree data structure can be defined recursively as a collection of nodes. Each node in a tree is either a leaf or an internal node. An internal node has one or more children and is called the parent node of the child nodes. All nodes of the same parent are called sibling nodes.

So formally, we can say that a tree is:

• Empty, i.e., no nodes
• A root and 0 or more sub trees

There are no cycles (a node pointing to itself, directly or indirectly) in a tree.

In this first article, we will create a node class that can hold a pointer to data member, contain n children. We will also create iterators that will traverse nodes from left to right, right to left and range.

By the end of this tip, we should be able to do the following for a node:

#include "NTree.hpp"
#include <iostream>

int main(int, char**) {
  blib::container::tree::Node<int> n;

  // Assign data to the node
  n.data( 0 );
  // Only print if data is present
  if ( n ) {
    std::cout << "Node data populated to = " << n.data( ) << std::endl;
  }
  for ( int i = 1; i < 20; ++i ) {
    n.addChild( i );
  }

  for ( auto c : n ) {
    // Only print if data is present
    if ( c ) {
      std::cout << c.data( ) << " ";
    }
  }
  std::cout << std::endl;
  for ( auto it = n.begin( ); it != n.end( ); ++it ) {
    if ( *it ) {
      std::cout << it->data( ) << " ";
    }
  }
  std::cout << std::endl;

  auto it = n.begin( );
  n.removeChild( it );

  for ( auto c : n ) {
    if ( c ) {
      std::cout << c.data( ) << " ";
    }
  }
  std::cout << std::endl;

  for ( auto rit = n.child_node_rtol_begin( ); rit != n.child_node_rtol_end( ); ++rit ) {
    if ( *rit ) {
      std::cout << rit->data( ) << " ";
    }
  }
}

Note

This is not intended to be a C++ beginner tutorial. I assume people have usable knowledge of C++, particularly C++11.

Background

Currently, I am trying to create a 2D game engine, and write some article on game (novice to novice). While doing that, I had the need for a scene graph. During that, I had various options as mentioned in the reference section. Then, I thought if it's a novice to novice, why not create a tree container too. I want it to be simple and reasonably fast for now.

The Node Class

So the basic data structure for a tree is the node. The node should contain the following:

• Data
• Children nodes

We will want the data to be flexible, not hard coded. So we will use templates.

namespace blib{ namespace container{ namespace tree{
  template<typename NodeDataType>
  class Node{
     private:
        typedef NodeDataType ValueType;
        typedef ValueType& ValueRef;
        typedef ValueType const& ConstValueRef;
        typedef Node<NodeDataType> NodeType;
        typedef NodeType SelfType;
        typedef NodeType& NodeRef;
        typedef NodeType const& ConstNodeRef;
        typedef std::vector<NodeType> ChildrenContainerType;

      private:
        std::shared_ptr<ValueType> _data;
        NodeHandle _parent;
        std::shared_ptr<ChildrenContainerType> _children;
};
}}}

Here, as we see, we use vector to store the children. This vector is further stored in a shared pointer. This can help with a lightweight node, where assigning is easier. Shared pointer to store the data, and we also have a NodeHandle to the parent. NodeHandle class is below. It acts as an abstraction for the raw pointer to the parent node. This can help prevent people accidentally deleting the pointer. Default implementation is just hiding the raw pointer.

//=====================================================================
// Node Handle Implementation
template<class NodeType>
class NodeHandleImpl {
public:
  typedef NodeType Node;
  typedef NodeHandleImpl<Node> SelfType;

private:
  Node const* _handle;
  friend class NodeUtility;

private:
  Node const* const pointer( ) const {
    return const_cast< Node const* const >( _handle );
  }

public:
  NodeHandleImpl( Node const* const aPtr = nullptr );
  NodeHandleImpl( SelfType const& aNode );
  NodeHandleImpl( Node const& aNode );
  ~NodeHandleImpl( );
  bool operator==( SelfType const& aNode ) const;
  bool operator==( Node const& aNode ) const;
  SelfType& operator=( SelfType const& aNode );
  operator bool( ) const;
};

//=====================================================================
// Node Handle
template<class NodeType>
class NodeHandle :
  public _private::NodeHandleImpl < NodeType > {
private:
  typedef NodeHandleImpl<NodeType> BaseType;

public:
  NodeHandle( Node const* const aPtr = nullptr ) :
    BaseType( aPtr ) {}

  NodeHandle( SelfType const& aNode ) :
    BaseType( aNode ) {}

  NodeHandle( Node const& aNode ) :
    BaseType( aNode ) {}
};

Now let's continue to methods that will be useful.

namespace blib {
  namespace container {
    namespace tree {
      //=====================================================================

      // Tree Node
      template<typename NodeDataType,
      typename DataAlloc = std::allocator<NodeDataType>,
      template<typename>class NodeAlloc = std::allocator>
      class Node {
      public:
        typedef NodeDataType ValueType;
        typedef ValueType& ValueRef;
        typedef ValueType const& ConstValueRef;
        typedef Node<NodeDataType, DataAlloc, NodeAlloc> NodeType;
        typedef NodeType SelfType;
        typedef NodeType& NodeRef;
        typedef NodeType const& ConstNodeRef;
        typedef _private::child_node_ltor_iterator<Node<NodeDataType>> child_node_ltor_iterator;
        typedef _private::child_node_rtol_iterator<Node<NodeDataType>> child_node_rtol_iterator;
        typedef NodeHandle<SelfType> NodeHandle;
        typedef NodeAlloc<SelfType> NodeAllocator;
        typedef DataAlloc DataAllocator;

      private:
        friend class child_node_ltor_iterator;
        friend class child_node_rtol_iterator;
        typedef std::vector<NodeType, NodeAllocator> ChildrenContainerType;

      private:
        std::shared_ptr<ValueType> _data;
        NodeHandle _parent;
        std::shared_ptr<ChildrenContainerType> _children;

      public:
        Node( NodeHandle const& aParent = NodeHandle( ) );
        Node( ConstValueRef aData, NodeHandle const& aParent );
        NodeHandle& parent( );
        void parent( NodeHandle const& aParent );
        NodeHandle handle( ) const
        ValueRef data( );
        ConstValueRef data( ) const;
        void data( ConstValueRef aData );
        ValueRef operator[]( const std::size_t aIndex );
        std::size_t numberOfChildren( ) const;
        void addChild( ConstNodeRef aNode );
        void addChild( ConstValueRef aValue );
        //The iterator pos must be valid and dereferenceable.
        //Thus the end() iterator (which is valid, but is not dereferencable) 
        //cannot be used as a value for pos.
        void removeChild( child_node_ltor_iterator const& aItr );
        std::size_t size( ) const;
        // Return false when there is no data in the node. Else return true
        operator bool( ) const
        bool empty( ) const;
        void clear( );
        bool operator==( ConstNodeRef aOther ) const;
        NodeRef operator=( ConstNodeRef aOther );
        bool isLeaf( ) const;
        // To support range based for loop
        // Default iteration is left to right
        child_node_ltor_iterator begin( );
        child_node_ltor_iterator end( );
        child_node_ltor_iterator child_node_ltor_begin( );
        child_node_ltor_iterator child_node_ltor_end( );
        child_node_rtol_iterator child_node_rtol_begin( );
        child_node_rtol_iterator child_node_rtol_end( );
      };
    }
  }
}

To get the full implementations, please refer to the NTree.hpp.

Now, we are set with the node class. What we need to figure out is how to traverse the children from one direction to another. We need to implement iterators and support range based for loop.

Iterators

To easily implement iterators, we will use the boost library. We will take the help of the boost iterator adaptor library. It's very easy to implement using this library. We have to follow the tutorial that they have given in the library tutorial. Here is how:

namespace _private {
  // Left to right iterator for child nodes
  template<typename NodeType>
  class child_node_ltor_iterator :
    public boost::iterator_facade < child_node_ltor_iterator<NodeType>,
      NodeType, boost::forward_traversal_tag > {
  public:
    typedef NodeType Node;
    typedef Node& NodeRef;
    typedef Node const& ConstNodeRef;
    typedef child_node_ltor_iterator<NodeType> SelfType;

  private:
    typedef typename Node::ChildrenContainerType ChildrenContainerType;
    typedef typename ChildrenContainerType::iterator ItrType;

    friend class IteratorUtility;
  private:
    ItrType _it;
    ItrType _end;

  public:
    child_node_ltor_iterator( ) {
      _it = _end;
    }

    explicit child_node_ltor_iterator( ItrType& aBegin, ItrType& aEnd ) {
      _it = aBegin;
      _end = aEnd;
    }

  private:
    friend class boost::iterator_core_access;

    bool equal( SelfType const& aOther ) const {
      return aOther._it == _it;
    }

    NodeRef dereference( ) const {
      return *_it;
    }

    void increment( ) {
      ++_it;
    }

    ItrType itr( ) {
      return _it;
    }
  };
  } // _private

Here as we see, we have to implement the core functions and it will start working.

Here, to access the current iterator, we cannot make the itr() function as public, as this will expose the implementation to the casual use. So we need a helper class. The below class helps:

class IteratorUtility {
public:
  template<typename Iterator>
  static typename Iterator::ItrType itr( Iterator aItr ) {
    return aItr.itr( );
  }
};

This is particularly helpful in implementing the Node::removeChild() function.

To make this usable with range based for loop, we need to have a begin() and end() function in Node class. That is what we do in the following code.

child_node_ltor_iterator begin( ) {
  child_node_ltor_iterator it( _children.begin( ), _children.end( ) );
  return it;
}

child_node_ltor_iterator end( ) {
  child_node_ltor_iterator it( _children.end( ), _children.end( ) );
  return it;
}

After all these implementations, we are all set to run the given examples.

In the next article, we will talk about tree traversals.

Code

NTree.hpp

Please refer to my blog for recent and updated changes to the code.

References

• st_tree
• Tree Container Library
• tree.hh
• Tree Wikipedia
• Data Structures and Algorithms with Object-Oriented Design Patterns in Java, Tree Definition
• Hierarchical Data Structures and Related Concepts for the C++ Standard Library
• Boost Iterator Facade

History

• 26^th March, 2015: Initial version with children iterators
• 31^st March, 2015: Added NodeHandle class. Added Allocator for nodes and data value.