Getting Modified Preorder Tree Traversal Data into an Array

Question

What is an efficient way to put the tree data into an array?

I followed the sitepoint tutorial to retrieve the tree data.

However, the tutorial only shows how to output the tree, not how to make a multidementional array.

I used

SELECT title, lft, rgt FROM tree_structure WHERE lft BETWEEN $parentLft  AND $parentRgt ORDER BY lft ASC

So for each item, I have its title, left and right values.

I am stuck on making the array look like this

Array
(
 Title: Main Topic
 Children => Array
             (
              => Title: subTopic
                     Leaf:  true
              => Title: Another subtopic
                     Children =>  Array
                               (
                                => Title: subtopic child
                                  Leaf: true
                               )
              ) 

)

If you could help, I would really appreciate it.

PS. The sql output looks like this (except I have title, not name and don't use category_id ):

+-------------+----------------------+-----+-----+
| category_id | name                 | lft | rgt |
+-------------+----------------------+-----+-----+
|           1 | ELECTRONICS          |   1 |  20 |
|           2 | TELEVISIONS          |   2 |   9 |
|           3 | TUBE                 |   3 |   4 |
|           4 | LCD                  |   5 |   6 |
|           5 | PLASMA               |   7 |   8 |
|           6 | PORTABLE ELECTRONICS |  10 |  19 |
|           7 | MP3 PLAYERS          |  11 |  14 |
|           8 | FLASH                |  12 |  13 |
|           9 | CD PLAYERS           |  15 |  16 |
|          10 | 2 WAY RADIOS         |  17 |  18 |

@Gumbo, I use the data from another article for my example. The main thing is that this algorithm uses left and right values to order data. — Alex L
– Alex L, Commented Sep 24, 2009 at 19:04

Travis · Accepted Answer · 2009-09-24 22:34:54Z

6

+250

Give this code a shot. $results is the database results. $tree is the array you're getting back.

function create_tree ($results) {

    $return = $results[0];
    array_shift($results);

    if ($return['lft'] + 1 == $return['rgt'])
        $return['leaf'] = true;
    else {
        foreach ($results as $key => $result) {
            if ($result['lft'] > $return['rgt']) //not a child
                break;
            if ($rgt > $result['lft']) //not a top-level child
                continue;
            $return['children'][] = create_tree(array_values($results));
            foreach ($results as $child_key => $child) {
                if ($child['rgt'] < $result['rgt'])
                    unset($results[$child_key]);
            }
            $rgt = $result['rgt'];
            unset($results[$key]);
        }
    }

    unset($return['lft'],$return['rgt']);
    return $return;

}
$tree = create_tree($results);

answered Sep 24, 2009 at 22:34

Travis

4,0887 gold badges40 silver badges52 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Alex L Over a year ago

thanks for your help but the array it made wasn't all right i will try to post the output once i have figure this out

Alex L Over a year ago

The array returned this this function is not correct and some rows repeat.

Alex L Over a year ago

This worked, thanks a lot. At first, I had a diff query and got bad results but when I fixed the query, it worked. Thanks!

Lukasz Lysik · Accepted Answer · 2009-10-01 22:51:45Z

4

I would start from rewriting the SQL query to this:

SELECT title, (SELECT TOP 1 title 
               FROM tree t2 
               WHERE t2.lft < t1.lft AND t2.rgt > t1.rgt    
               ORDER BY t2.rgt-t1.rgt ASC) AS parent
FROM tree t1
ORDER BY rgt-lft DESC

This will give you result like this:

title                | parent
----------------------------------------------
ELECTRONICS          | NULL
PORTABLE ELECTRONICS | ELECTRONICS
TELEVISIONS          | ELECTRONICS
MP3 PLAYERS          | PORTABLE ELECTRONICS
FLASH                | MP3 PLAYERS
CD PLAYERS           | PORTABLE ELECTRONICS
2 WAY RADIOS         | PORTABLE ELECTRONICS
TUBE                 | TELEVISIONS
LCD                  | TELEVISIONS
PLASMA               | TELEVISIONS

With this, it is much easier.

answered Oct 1, 2009 at 22:51

Lukasz Lysik

10.7k4 gold badges53 silver badges73 bronze badges

1 Comment

Das123 Over a year ago

Thanks for posting this. I've been looking for an SQL script to add a particular ancestor ID (not parent in my case) and it was very easy to solve using your code as a starting point.

mr c · Accepted Answer · 2009-12-23 11:03:35Z

0

using the create_tree i got an error at this point:

if ($rgt > $result['lft']) //not a top-level child  continue;

The error it return says: Undefined variable: rgt

Also it did not return the correct number of array..... I am using the same database structure in

http://articles.sitepoint.com/article/hierarchical-data-database/2

answered Dec 23, 2009 at 11:03

mr c

1

Collectives™ on Stack Overflow

Getting Modified Preorder Tree Traversal Data into an Array

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related