Retired Documentation

You are using the documentation for version 2.11.9. Go here for the latest version or check here for your available upgrades to the latest version.

Tree Datastructure¶

Uses and anatomy of a tree
Creating a tree structure
Moving between tree nodes
Attaching and modifying node data
Traversing the tree
Method Reference

Uses and anatomy of a tree ¶

A lot of data in ExpressionEngine can be described with parents and children. This includes nested categories, template groups and their templates, channels and their fields, relationships, and a lot of others. When it comes to dealing with multiple levels of these sorts of connections, it can be useful to model them as a tree.

The best way to imagine one of these trees is to think of them as a typical tree as you might find in a forest. Upside-down:

     root
    /    \
child   child
       /     \
   child    child

Creating a tree structure ¶

As with most of ExpressionEngine’s libraries, we need to load it before we can start using it:

ee()->load->library('datastructures/tree');

There are two ways to create a tree. The first is to create and connect the nodes manually. This tends to give you a little more flexibility in how you build your tree. The class we need for this is EE_TreeNode. It takes a node name as a parameter and some optional data to attach to this node.

$root = new EE_TreeNode('root');
$child1 = new EE_TreeNode('child1');
$child2 = new EE_TreeNode('child2');
$subchild = new EE_TreeNode('subchild');

$root->add($child1);
$root->add($child2);
$child2->add($subchild);

add()¶

Here we have created a tree that looks like this:

      root
     /    \
child1   child2
              \
            subchild

The other option is to use the tree library’s factory method. Frequently you tree will come from a database as a list of entries with ids and parent ids. The above data might look like this:

$data = array(
    array('id' => 'root', 'parent_id' => ''),
    array('id' => 'child1', 'parent_id' => 'root'),
    array('id' => 'child2', 'parent_id' => 'root'),
    array('id' => 'subchild', 'parent_id' => 'child2'),
);

In order to turn this into a tree, we simply pass it to the from_list method:

$root = ee()->tree->from_list($data);

By default, id and parent_id will be used to resolve the tree structure. The id is also used as the name, and by default the tree is constructed from EE_TreeNode objects. If you need to change any of these, you can do so with a second parameter:

$root = ee()->tree->from_list($data, array(
    'id'          => 'category_id',
    'parent'      => 'parent_category_id',
    'class_name'  => 'MyCatTreeNode',
    'name_key'    => 'title'
));

It will return the root node of the tree for us. Watch out: Since the database result can frequently contain more than one relative root it will always return a blank root node with the actual tree as its children. If you know you only have one root, you can use the first_child convenience method to move to your real root:

if ( ! $root->is_leaf())
{
    $root = $root->first_child();
}

If you want to disconnect the single parent completely, you should also call the subtree method so that your new node responds correctly to is_root:

if ( ! $root->is_leaf())
{
    $root = $root->first_child()->subtree();
}

Otherwise you will need to exclude the root in your iterations:

foreach ($it as $node)
{
    if ($node->is_root())
    {
        continue;
    }

    // process node
}

Moving between tree nodes ¶

All nodes contain the information about their neighbors so that you can easily move between nodes to travel along your tree. The simplest movement is between a node and its parent:

$parent = $node->parent();

We can also get access to the children. There can be more than one so they come in an array:

$children = $node->children();
$child1 = $children[0];
$child2 = $children[1];

If your node names are unique you can also jump to direct child using its name:

$child1 = $node->get('child1');

If you get lost in the tree you can always jump back up to the root:

$root = $node->root();

To stop from going past the edges of the tree, you should always check if the current node is a leaf (going down) or the root (going up):

$node->is_leaf();
$node->is_root();

Attaching and modifying node data ¶

When you create a node you give it a name and you can also give it any payload data that you want it to have:

$node = new EE_TreeNode('Lennie', array('friend' => 'George'));

The name can be accessed with the name function:

echo $node->name(); // prints "Lennie"

If your payload data is an array, then you can read its keys directly from the node:

echo $node->friend; // prints "George"

The full data is available through the data method:

$data = $node->data();
echo $data['friend']; // prints "George"

Note

The default tree’s node data is immutable.

Traversing the tree ¶

Sometimes you simply need to walk the entire tree. This can quickly become a review of recursion and an exercise in frustration. To simplify this behavior, the tree can create Iterators for a few common types of traversal. For the below examples we will be using this simple loop that prints the tree with the children indented:

$it = $node->some_iterator_function();

foreach ($it as $node)
{
    $indent = str_repeat(' ', 4 * $it->getDepth()); // indent each level 4 spaces
    echo $indent.$node->name();
}

And this tree:

             root
            /    \
       child1   child2
       /    \
subchild1   subchild2

preorder_iterator()¶

Preorder iteration will visit the current node first and then each of the children. This is the most common iterator.

root
  child1
    subchild1
    subchild2
  child2

postorder_iterator()¶

Postorder iteration will visit the children first and then the current node.

    subchild1
    subchild2
  child1
  child2
root

breadth_first_iterator()¶

Breadth first iteration will visit the tree level-by-level. This requires a little more memory than other forms of iteration as the iterator needs to remember which nodes had children.

root
  child1
  child2
    subchild1
    subchild2

leaf_iterator()¶

This iterator only visits nodes that do not have children of their own.

|    subchild1
|    subchild2
|    child2

Method Reference ¶

EE_Tree ¶

class EE_Tree¶

EE_Tree::from_list($data[, array $conf = NULL])¶

Tree Factory

Takes an array of rows that each have an id and parent id (as you would get from the db) and returns a tree structure

Parameters:	$data (array) – array of `array('unique_id' => x, 'parent_id' => y, ...data)` $conf (array) – Optional array containing: `key`: data’s unique id key `parent_id`: data’s parent_id key
Returns:	Tree structure from a listing of data
Return type:	ImmutableTree

EE_Tree::to_list(EE_TreeNode $tree)¶

Flatten the tree to a list of data objects.

Parameters:	$tree (EE_TreeNode) – `EE_TreeNode` object
Returns:	Similar data structure to what was passed to `from_list`
Return type:	Array

EE_TreeNode ¶

class EE_TreeNode¶

EE_TreeNode::__get($key)¶

Retrieve the payload data.

If the payload is an array we treat the entire object as an accessor to the payload. Otherwise the key must be “data” to mimic regular object access.

Parameters:	$key (string) – The name of the property
Returns:	The value of the property
Return type:	Mixed

EE_TreeNode::__set($key, $value)¶

Retrieve the payload data.

If they payload is an array we treat the entire object as an accessor to the payload. Otherwise the key must be 'data' to mimic regular object access.

Parameters:	$key (string) – The name of the property $value (mixed) – The value of the property
Return type:	Void

EE_TreeNode::add(EE_TreeNode $child)¶

Add a child node to the current node.

Notifies the child of its parent and adds the child name to the child name array. Does not enforce unique names since it may be desirable to have non-unique named children. It’s on the developer to not rely on the get method in that case.

Parameters:	$child (EE_TreeNode) – EE_TreeNode to add as a child
Return type:	Void

EE_TreeNode::name()¶

Get the node’s name

Returns:	Node’s name
Return type:	String

EE_TreeNode::data()¶

Get the node’s payload

Returns:	Node’s payload
Return type:	Mixed

EE_TreeNode::depth()¶

Get the node’s depth relative to its root, where the root’s depth is 0.

Returns:	Node’s depth
Return type:	Integer

EE_TreeNode::root()¶

Get the tree’s root node

If the current node is not a root node, we move our way up until we have a root.

Returns:	The root EE_TreeNode
Return type:	EE_TreeNode

EE_TreeNode::children()¶

Get all of the node’s children

Returns:	All child nodes
Return type:	EE_TreeNode

EE_TreeNode::first_child()¶

Get the node’s first child

Returns:	First child node
Return type:	EE_TreeNode

EE_TreeNode::parent()¶

Get the node’s parent

Returns:	Node’s parent
Return type:	EE_TreeNode

EE_TreeNode::siblings()¶

Get all of a node’s siblings

Returns:	Node’s siblings
Return type:	EE_TreeNode

EE_TreeNode::is_root()¶

Check if the node has parents

Returns:	`TRUE` if the node has parents, `FALSE` otherwise
Return type:	Boolean

EE_TreeNode::is_leaf()¶

Check if the node has children

Returns:	`TRUE` if the node has children, `FALSE` otherwise
Return type:	Boolean

EE_TreeNode::freeze()¶

Freeze the node

Prevents data and child manipulations. Cloning a frozen node will unfreeze it.

Return type:	Void

EE_TreeNode::get($name)¶

Get a child by name

You are responsible for adding children with unique names. If you do not, then this method will return the last child node of the given name.

Parameters:	$name (string) – Name of the child to get
Returns:	Child node
Return type:	EE_TreeNode

EE_TreeNode::subtree()¶

Create a subtree on this node.

Clones the current node to turn it into a root node off the original tree.

This is a shallow copy! The root node you receive is a clone, but its children remain on the tree. If you need a clone for anything other than traversal, consider using the subtree_copy method instead.

Returns:	A shallow copy of the tree starting at the current node
Return type:	EE_TreeNode

EE_TreeNode::subtree_copy()¶

Create a full subtree copy from this node down.

Clones the current node and all of its children. This is a deep copy, everything will be cloned. If all you need is a new root for traversal, consider using subtree instead.

Returns:	Full subtree copy from the current node
Return type:	EE_TreeNode

EE_TreeNode::preorder_iterator()¶

Preorder Tree Iterator

Creates a preorder tree iterator from the current node down.

Returns:	Preorder tree iterator from the current node down
Return type:	RecursiveIteratorIterator

EE_TreeNode::postorder_iterator()¶

Postorder Tree Iterator

Creates a postorder tree iterator from the current node down.

Returns:	Postorder tree iterator from the current node down
Return type:	RecursiveIteratorIterator

EE_TreeNode::leaf_iterator()¶

Leaf Iterator

Iterates across all the leaf nodes

Returns:	Iterator with leaf nodes only
Return type:	RecursiveIteratorIterator

EE_TreeNode::breadth_first_iterator()¶

Breadth First Iterator

Iterates across all nodes in a level-by-level fashion

Returns:	Iterator with all nodes in a level-by-level fashion
Return type:	RecursiveIteratorIterator

EE_TreeIterator ¶

class EE_TreeIterator¶: This class extends RecursiveArrayIterator.

EE_TreeIterator::hasChildren()¶

Override RecursiveArrayIterator’s child detection method. We really don’t want to count object properties as children.

Returns:	`TRUE` if there are children, `FALSE` otherwise``
Return type:	boolean

EE_TreeIterator::getChildren()¶

Override RecursiveArrayIterator’s get child method to skip ahead into the children array and not try to iterate over the over the public name property.

Returns:	Children of the EE_TreeIterator
Return type:	EE_TreeIterator

EE_BreadthFirstIterator ¶

class EE_BreadthFirstIterator¶: This class implements OuterIterator.

EE_BreadthFirstIterator::current()¶

Current Iterator Entry

Returns:	Entry of the current inner iterator
Return type:	Iterator

EE_BreadthFirstIterator::key()¶

Current Iterator Key

Returns:	Key of the current inner iterator
Return type:	Iterator

EE_BreadthFirstIterator::next()¶

Next Iterator Step

Standard level by level iterator using a queue to remember where the children are.

Return type:	Void

EE_BreadthFirstIterator::rewind()¶

Rewind the Iterator

All the subiterators are rewound when they’re exhausted so we only have to worry about the current one.

Return type:	Void

EE_BreadthFirstIterator::valid()¶

Find a valid iterator entry if it exists

If we have exhausted the current iterator then we need to move on to the next one on the queue. If they’re all exhausted we’re out of entries.

Returns:	`TRUE` if iterator is valid, `FALSE` otherwise
Return type:	Boolean

EE_BreadthFirstIterator::getInnerIterator()¶

Get internal iterator

To the user this iterator is supposed to be mostly transparent. This is here to satisfy the OuterIterator contract. I can’t think of a good reason you would want to use it.

Returns:	Current sub iterator
Return type:	RecursiveIterator

EE_BreadthFirstIterator::getDepth()¶

Get iteration depth

Retrieve the per level depth of the iterator. Using the same method contract as RecursiveIteratorIterator for consistency.

Returns:	Iteration depth
Return type:	Integer