Working with trees

Tree is a templated container class that stores objects in a hierarchical structure.

This example constructs a tree of strings. This tree is identical to that of example Point search with a quadtree.

The tree is afterwards traversed in depth-first order.

Involved classes: Tree TreeNode TreeIterator

Constructing the tree

Tree

                0-0
                0-1
                0-2
        0 ----- 0-3
        1
root -- 2       
        3 ----- 3-0
                3-1
                3-2
                3-3 --- 3-3-0 
                        3-3-1
                        3-3-2
                        3-3-3

C++

#include <spatium/Tree.h>
#include <string> // std::string

using namespace spatium;

idx::Tree<std::string> tree("root");
std::shared_ptr<idx::TreeNode<std::string>> root = tree.root();

// Add children to root node
auto root_0 = root->addChild(root, "root-0");
root->addChild(root, "root-1");
root->addChild(root, "root-2");
auto root_3 = root->addChild(root, "root-3");

// Add children to root-0
root_0->addChild(root_0, "root-0-0");
root_0->addChild(root_0, "root-0-1");
root_0->addChild(root_0, "root-0-2");
root_0->addChild(root_0, "root-0-3");

// Add children to root-3
root_3->addChild(root_3, "root-3-0");
root_3->addChild(root_3, "root-3-1");
root_3->addChild(root_3, "root-3-2");
auto root_3_3 = root_3->addChild(root_3, "root-3-3");

// Add children to root-3-3
root_3_3->addChild(root_3_3, "root-3-3-0");
root_3_3->addChild(root_3_3, "root-3-3-1");
root_3_3->addChild(root_3_3, "root-3-3-2");
root_3_3->addChild(root_3_3, "root-3-3-3");

Iterating the tree

C++

#include <spatium/TreeIterator.h>
#include <iostream> // std::cout

for (idx::TreeIterator<std::string> it = tree.begin(); it != tree.end(); ++it)
{
  std::shared_ptr<idx::TreeNode<std::string>> node = *it;

  std::cout << node->object() << std::endl;;
}

Output

root
root-0
root-0-0
root-0-1
root-0-2
root-0-3
root-1
root-2
root-3
root-3-0
root-3-1
root-3-2
root-3-3
root-3-3-0
root-3-3-1
root-3-3-2
root-3-3-3