13,800,880 members
Tip/Trick
alternative version

#### Stats

23K views
16 bookmarked
Posted 26 Mar 2015
Licenced MPL

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

, 26 Mar 2015
This tip describes a n ary tree structure.

## 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 ) {
}

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;
ValueRef operator[]( const std::size_t aIndex );
std::size_t numberOfChildren( ) const;
//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 :
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.

## History

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

## Share

 Architect India
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

## You may also be interested in...

 First Prev Next
 Change History BrainlessLabs.com3-Apr-15 9:38 BrainlessLabs.com 3-Apr-15 9:38
 Nice! Volynsky Alex1-Apr-15 14:26 Volynsky Alex 1-Apr-15 14:26
 Re: Nice! BrainlessLabs.com1-Apr-15 21:04 BrainlessLabs.com 1-Apr-15 21:04
 Re: Nice! Volynsky Alex2-Apr-15 22:58 Volynsky Alex 2-Apr-15 22:58
 The tree iterators are complete BrainlessLabs.com31-Mar-15 19:18 BrainlessLabs.com 31-Mar-15 19:18
 Good Demonstration of Template Programming Jon Summers30-Mar-15 5:26 Jon Summers 30-Mar-15 5:26
 Re: Good Demonstration of Template Programming BrainlessLabs.com30-Mar-15 5:32 BrainlessLabs.com 30-Mar-15 5:32
 Last Visit: 16-Dec-18 8:15     Last Update: 16-Dec-18 8:15 Refresh 1