PHP tree structure for categories and sub categories without looping a query

I'm trying to create a list of categories with any number of sub categories, where sub categories can also has their own sub categories.

I have selected all categories from the Mysql db, the cats are in a standard associate array list, each category has an id, name, parentid where the parentid is 0 if it's top level.

I basically want to be able to take the single level array of cats and turn it into a multidimensional array structure where each category can have an element which will contain an array of subcats.

Now, I can easily achieve this by looping a query for each category but this is far from ideal, I'm trying to do it without any extra hits on the db.

I understand I need a recursive function for this. Can anyone point me i开发者_StackOverflow社区n the right direction for this tree style structure?

Cheers

---

This does the job:

$items = array(
        (object) array('id' => 42, 'parent_id' => 1),
        (object) array('id' => 43, 'parent_id' => 42),
        (object) array('id' => 1,  'parent_id' => 0),
);

$childs = array();

foreach($items as $item)
    $childs[$item->parent_id][] = $item;

foreach($items as $item) if (isset($childs[$item->id]))
    $item->childs = $childs[$item->id];

$tree = $childs[0];

print_r($tree);

This works by first indexing categories by parent_id. Then for each category, we just have to set category->childs to childs[category->id], and the tree is built !

So, now $tree is the categories tree. It contains an array of items with parent_id=0, which themselves contain an array of their childs, which themselves ...

Output of print_r($tree):

stdClass Object
(
    [id] => 1
    [parent_id] => 0
    [childs] => Array
        (
            [0] => stdClass Object
                (
                    [id] => 42
                    [parent_id] => 1
                    [childs] => Array
                        (
                            [0] => stdClass Object
                                (
                                    [id] => 43
                                    [parent_id] => 42
                                )

                        )

                )

        )

)

So here is the final function:

function buildTree($items) {

    $childs = array();

    foreach($items as $item)
        $childs[$item->parent_id][] = $item;

    foreach($items as $item) if (isset($childs[$item->id]))
        $item->childs = $childs[$item->id];

    return $childs[0];
}

$tree = buildTree($items);

---

Here is the same version, with arrays, which is a little tricky as we need to play with references (but works equally well):

$items = array(
        array('id' => 42, 'parent_id' => 1),
        array('id' => 43, 'parent_id' => 42),
        array('id' => 1,  'parent_id' => 0),
);

$childs = array();
foreach($items as &$item) $childs[$item['parent_id']][] = &$item;
unset($item);

foreach($items as &$item) if (isset($childs[$item['id']]))
        $item['childs'] = $childs[$item['id']];
unset($item);

$tree = $childs[0];

So the array version of the final function:

function buildTree($items) {
    $childs = array();

    foreach($items as &$item) $childs[(int)$item['parent_id']][] = &$item;

    foreach($items as &$item) if (isset($childs[$item['id']]))
            $item['childs'] = $childs[$item['id']];
   
    return $childs[0]; // Root only.
}

$tree = buildTree($items);

---

You can fetch all categories at once.

Suppose you have a flat result from the database, like this:

$categories = array(
    array('id' => 1,  'parent' => 0, 'name' => 'Category A'),
    array('id' => 2,  'parent' => 0, 'name' => 'Category B'),
    array('id' => 3,  'parent' => 0, 'name' => 'Category C'),
    array('id' => 4,  'parent' => 0, 'name' => 'Category D'),
    array('id' => 5,  'parent' => 0, 'name' => 'Category E'),
    array('id' => 6,  'parent' => 2, 'name' => 'Subcategory F'),
    array('id' => 7,  'parent' => 2, 'name' => 'Subcategory G'),
    array('id' => 8,  'parent' => 3, 'name' => 'Subcategory H'),
    array('id' => 9,  'parent' => 4, 'name' => 'Subcategory I'),
    array('id' => 10, 'parent' => 9, 'name' => 'Subcategory J'),
);

You can create a simple function that turns that flat list into a structure, preferably inside a function. I use pass-by-reference so that there are only one array per category and not multiple copies of the array for one category.

function categoriesToTree(&$categories) {

A map is used to lookup categories quickly. Here, I also created a dummy array for the "root" level.

    $map = array(
        0 => array('subcategories' => array())
    );

I added another field, subcategories, to each category array, and add it to the map.

    foreach ($categories as &$category) {
        $category['subcategories'] = array();
        $map[$category['id']] = &$category;
    }

Looping through each categories again, adding itself to its parent's subcategory list. The reference is important here, otherwise the categories already added will not be updated when there are more subcategories.

    foreach ($categories as &$category) {
        $map[$category['parent']]['subcategories'][] = &$category;
    }

Finally, return the subcategories of that dummy category which refer to all top level categories._

    return $map[0]['subcategories'];

}

Usage:

$tree = categoriesToTree($categories);

And here is the code in action on Codepad.

---

See the method :

function buildTree(array &$elements, $parentId = 0) {

    $branch = array();    
    foreach ($elements as $element) {
        if ($element['parent_id'] == $parentId) {
            $children = buildTree($elements, $element['id']);
            if ($children) {
                $element['children'] = $children;
            }
            $branch[$element['id']] = $element;
        }
    }
    return $branch;
}

---

I had the same problem and solved it this way: fetch cat rows from DB and for each root categories, build tree, starting with level (depth) 0. May not be the most efficient solution, but works for me.

$globalTree = array();
$fp = fopen("/tmp/taxonomy.csv", "w");

// I get categories from command line, but if you want all, you can fetch from table
$categories = $db->fetchCol("SELECT id FROM categories WHERE parentid = '0'");

foreach ($categories as $category) {
    buildTree($category, 0);
    printTree($category);
    $globalTree = array();
}

fclose($file);

function buildTree($categoryId, $level)
{
    global $db, $globalTree;
    $rootNode = $db->fetchRow("SELECT id, name FROM categories WHERE id=?", $categoryId);
    $childNodes = $db->fetchAll("SELECT * FROM categories WHERE parentid = ? AND id <> ? ORDER BY id", array($rootNode['id'], $rootNode['id']));
    if(count($childNodes) < 1) {
        return 0;
    } else {
        $childLvl = $level + 1;
        foreach ($childNodes as $childNode) {
            $id = $childNode['id'];
            $childLevel = isset($globalTree[$id])? max($globalTree[$id]['depth'], $level): $level;
            $globalTree[$id] = array_merge($childNode, array('depth' => $childLevel));
            buildTree($id, $childLvl);
        }
    }
}

function printTree($categoryId) {
    global $globalTree, $fp, $db;
    $rootNode = $db->fetchRow("SELECT id, name FROM categories WHERE id=?", $categoryId);
    fwrite($fp, $rootNode['id'] . " : " . $rootNode['name'] . "\n");
    foreach ($globalTree as $node) {
        for ($i=0; $i <= $node['depth']; $i++) {
            fwrite($fp, ",");
        }
        fwrite($fp, $node['id'] " : " . $node['name'] . "\n");
    }
}

ps. I am aware that OP is looking for a solution without DB queries, but this one involves recursion and will help anybody who stumbled across this question searching for recursive solution for this type of question and does not mind DB queries.

---

If the parent key is not passed from the class object then my code will create a root category and if the parent value is passed then child will create under the parent root.

    class CategoryTree {

    public $categories = array();

    public function addCategory(string $category, string $parent=null) : void
    {

        if( $parent ) {
            if ( array_key_exists($parent , $this->categories ) ) { 
                $this->categories[$parent][] = $category;
            }
            else {
                $this->categories[$parent] = array(); 
                $this->categories[$parent][] = $category; 
            }
        }
        else {
            if ( ! array_key_exists($category , $this->categories ) ) { 
                $this->categories[$category] = array(); 
            }
        }
        
    }

    public function getChildren(string $parent = null) : array 
    {
        $data = [];

        if ( array_key_exists($parent , $this->categories ) ) { 
            $data = $this->categories[$parent];
        }

        return $data;
        
    }
}

$c = new CategoryTree;
$c->addCategory('A', null);
$c->addCategory('B', 'A');
$c->addCategory('C', 'A');
$c->addCategory('C', 'E');
$c->addCategory('D', 'E');
$c->addCategory('D', null);
$c->addCategory('N', 'D');
$c->addCategory('A', null);
$c->addCategory('G', 'A');

echo implode(',', $c->getChildren('A'));