Traverse array as tree in php

Question

I have a db table that describes a hierarchy. Here is the structure

 id | pid | uid 
  1    5     2
  2    2     3
  3    2     4
  4    2     6
  5    3     7

In tree structure it would look this way. This is just an example, their could be many more nodes.

         2 
      /  |  \
     3   4   6
    /      
   7 

So in php and mysql I fetch all that data and save it to an array.

I want to traverse that array to determine e.g. the number of id's in a particular level and I want to be able to retrieve all nodes from one level.

How can I do that in php?

EDIT

This is how I create my array:

foreach ( $resultSet as $row ) {
    $entry = array();
    $entry['id'] = $row->id;
    $entry['uid'] = $row->uid;
    $entry['rid'] = $row->rid;
    $entry['date'] = $row->date;
    $entries [] = $entry;
}

And this is how I create the tree now using the answer

$tree = array();
foreach($entries as $key){
   $this->adj_tree($tree, $key);
}
return $tree;

But I get some strange output when I print $tree

Array ( [24] => Array ( [id] => 6 [uid] => 24 [rid] => 83 [date] => 2011-06-15
17:54:14 ) [] => Array ( [_children] => Array ( [0] => Array ( [id] => 6 [uid] => 24 
[rid] => 83 [date] => 2011-06-15 17:54:14 ) [1] => Array ( [id] => 6 [uid] => 24 [rid] =>
83 [date] => 2011-06-15 17:54:14 ) ) ) ) 

But actually there should be one parent with the uid of 24 with two childs with rid 82 and 83

Answer 1

You didn't say how you're using your table, but I guess it's for a store category tree, or something similar, i.e. a small dataset that doesn't need any sophisticated storage. You can read the whole table at once and build a tree structure on the fly with php. It goes like this

function adj_tree(&$tree, $item) {
    $i = $item['uid'];
    $p = $item['pid'];
    $tree[$i] = isset($tree[$i]) ? $item + $tree[$i] : $item;
    $tree[$p]['_children'][] = &$tree[$i];
}

Example:

$tree = array();
$rs = my_query("SELECT * FROM categories");
while($row = my_fetch($rs))
    adj_tree($tree, $row);

At the end, you get an array of items with each item containing the '_children' subarray, which, in turn, contains references to other items (or is empty).

Complete example, with the data from the question

$entries = array(
  array('id' => 1, 'pid' => 5, 'uid' => 2),
  array('id' => 2, 'pid' => 2, 'uid' => 3),
  array('id' => 3, 'pid' => 2, 'uid' => 4),
  array('id' => 4, 'pid' => 2, 'uid' => 6),
  array('id' => 5, 'pid' => 3, 'uid' => 7),
);

$tree = array();
foreach($entries as $row)
    adj_tree($tree, $row);

function print_tree($node, $indent) {
    echo str_repeat('...', $indent) . $node['uid'], "<br>\n";
    if(isset($node['_children']))
        foreach($node['_children'] as $child)
            print_tree($child, $indent + 1);
}

print_tree($tree[2], 0);

Answer 2

Same as in any other object oriented language - create your own Tree and Node classes which would suite your needs.

Another approach is to create tree by using arrays (in PHP arrays are associative and can be nested)

And I agree with Vinicius Kamakura - if data set is noticeably big you shouldn't load data to PHP.

Answer 3

I've built a class based on user187291 answer.

class Tree
{
    protected $tree;
    protected $rootid;

    public function __construct($entries)
    {
        $this->tree = array();
        $this->rootid = PHP_INT_MAX;

        /* Build tree under each node */
        foreach($entries as $node)
            $this->buildTree($this->tree, $node);
    }


    /* Build tree */
    protected function buildTree(&$tree, $node) 
    {
        $i = $node['id'];
        $p = $node['pid'];
        $this->rootid = min($this->rootid, $p);
        $tree[$i] = isset($tree[$i]) ? $node + $tree[$i] : $node;
        $tree[$p]['_children'][] = &$tree[$i];
    }


    /* Print tree */
    public function printTree() 
    {
        $this->printSubtree($this->tree[$this->rootid]);
    }


    /* Print subtree under given node */
    protected function printSubtree($node, $depth=0) 
    {
        /* Root node doesn't have id */
        if(isset($node['id']))
        {
            echo str_repeat('...', $depth) . $node['id'], "<br>\n";
        }

        /* Explore children */
        if(isset($node['_children']))
        {
            foreach($node['_children'] as $child)
                $this->printSubtree($child, $depth + 1);
        }
    }


    /* Destroy instance data */
    public function __destruct() 
    {
        $this->tree = null;
    }
}

Usage example

$entries = array(
  array('pid' => 2, 'id' => 3),
  array('pid' => 0, 'id' => 2),
  array('pid' => 3, 'id' => 7),
  array('pid' => 2, 'id' => 4),
  array('pid' => 2, 'id' => 6),
  array('pid' => 3, 'id' => 8),
  array('pid' => 0, 'id' => 9),
);

$tree = new Tree($entries);
$tree->printTree();

Hope it helps someone. Of course, you can add fields to "entries" elements, just remember to change "printSubtree" method if you want to print them.

Notes: This class assumes that nodes have numeric values for "id" and "pid", and parent node has lower "id" than its children (which is common in tree structures).