How can I generate a tree structure from a table in a database?

Question

I'm trying to generate a tree structure from a table in a database. The table is stored flat, with each record either having a parent_id or 0. The ultimate goal is to have a select box generated, and an array of nodes.

The code I have so far is :

function init($table, $parent_id = 0) 
{

    $sql = "SELECT id, {$this->parent_id_field}, {$this->name_field} FROM $table WHERE {$this->parent_id_field}=$parent_id ORDER BY display_order";

    $result = mysql_query($sql);

    $this->get_tree($result, 0);

    print_r($this->nodes);
    print_r($this->select);
    exit;
}

function get_tree($query, $depth = 0, $parent_obj = null)
{   
    while($row = mysql_fetch_object($query))
    {   
        /* Get node */
        $this->nodes[$row->parent_category_id][$row->id] = $row;

        /* Get select item */
        $text = "";
        if($row->parent_category_id != 0) {
            $text .= "    ";
        }
        $text .= "$row->name";
        $this->select[$row->id] = $text;

        echo "$depth $text\n";

        $sql = "SELECT id, parent_category_id, name FROM product_categories WHERE parent_category_id=".$row->id." ORDER BY display_order";

        $nextQuery = mysql_query($sql);
        $rows = mysql_num_rows($nextQuery);

        if($rows > 0) {
            $this->get_tree($nextQuery, ++$depth, $row);
        }            
    }
}

It's almost working, but not quite. Can anybody help me finish it off?

Answer 1

    $this->nodes[$row->parent_category_id][$row->id] = $row;

This line is destroying your ORDER BY display_order. Change it to

    $this->nodes[$row->parent_category_id][] = $row;

My next issue is the $row->parent_category_id part of that. Shouldn't it just be $row->parent_id?

EDIT: Oh, I didn't read your source closely enough. Get rid of the WHERE clause. Read the whole table at once. You need to post process the tree a second time. First you read the database into a list of arrays. Then you process the array recursively to do your output.

Your array should look like this:

 Array(0 => Array(1 => $obj, 5 => $obj), 
       1 => Array(2 => $obj),
       2 => Array(3 => $obj, 4 => $obj),
       5 => Array(6 => $obj) );

 function display_tree() {
      // all the stuff above
      output_tree($this->nodes[0], 0); // pass all the parent_id = 0 arrays.
 }

 function output_tree($nodes, $depth = 0) {
     foreach($nodes as $k => $v) {
         echo str_repeat(' ', $depth*2) . $v->print_me();
         // print my sub trees
         output_tree($this->nodes[$k], $depth + 1);
     }
 }

 output:
 object 1
   object 2
     object 3
     object 4
 object 5
   object 6

Answer 2

I think it's this line here:

if($row->parent_category_id != 0) {
    $text .= "    ";
}

should be:

while ($depth-- > 0) {
    $text .= "    ";
}

You are only indenting it once, not the number of times it should be indented.

And this line:

$this->get_tree($nextQuery, ++$depth, $row);

should be:

$this->get_tree($nextQuery, $depth + 1, $row);

Note that you should probably follow the advice in the other answer though, and grab the entire table at once, and then process it at once, because in general you want to minimize round-trips to the database (there are a few use cases where the way you are doing it is more optimal, such as if you have a very large tree, and are selecting a small portion of it, but I doubt that is the case here)

Answer 3

You almost certainly, should not continue down your current path. The recursive method you are trying to use will almost certainly kill your performance if your tree ever gets even slightly larger. You probably should be looking at a nested set structure instead of an adjacency list if you plan on reading the tree frequently.

With a nested set, you can easily retrieve the entire tree nested properly with a single query.

Please see these questions for a a discussion of trees.

http://stackoverflow.com/questions/169817/is-it-possible-to-query-a-tree-structure-table-in-mysql-in-a-single-query-to-any

http://stackoverflow.com/questions/544632/implementing-a-hierarchical-data-structure-in-a-database

http://stackoverflow.com/questions/192220/what-is-the-most-efficient-elegant-way-to-parse-a-flat-table-into-a-tree