Structure arborescente PHP pour les catégories et sous-catégories sans boucler une requête

Question

J'essaie de créer une liste de catégories avec un nombre quelconque de sous-catégories, où les sous-catégories peuvent également avoir leurs propres sous-catégories.

J'ai sélectionné toutes les catégories dans la base de données Mysql, les chats sont dans une liste de tableaux associés standard, chaque catégorie a un id, un nom, un parentid où le parentid est 0 si c'est un niveau supérieur.

Je veux essentiellement pouvoir prendre le tableau de chats à un seul niveau et le transformer en une structure de tableau multidimensionnelle où chaque catégorie peut avoir un élément qui contiendra un tableau de sous-chats.

Maintenant, je peux facilement réaliser ceci en bouclant une requête pour chaque catégorie mais c'est loin d'être idéal, j'essaye de le faire sans aucune charge supplémentaire sur la base de données.

Je comprends que j'ai besoin d'une fonction récursive pour cela. Quelqu'un peut-il m'indiquer la bonne direction pour cette structure arborescente ?

Cheers

Answer 1

Cela fait l'affaire :

$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);

Cela fonctionne en indexant d'abord les catégories par parent_id. Ensuite, pour chaque catégorie, il suffit d'activer la fonction category->childs à childs[category->id] et l'arbre est construit !

Alors, maintenant $tree est l'arbre des catégories. Il contient un tableau d'éléments avec parent_id=0, qui eux-mêmes contiennent un tableau de leurs enfants, qui eux-mêmes ...

Sortie de 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
                                )

                        )

                )

        )

)

Voici donc la fonction finale :

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);

---

Voici la même version, avec des tableaux, ce qui est un peu plus délicat car nous devons jouer avec les références (mais fonctionne aussi bien) :

$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];

Donc la version tableau de la fonction finale :

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);

Answer 2

Vous pouvez récupérer toutes les catégories en même temps.

Supposons que vous ayez un résultat plat provenant de la base de données, comme ceci :

$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'),
);

Vous pouvez créer une fonction simple qui transforme cette liste plate en une structure, de préférence à l'intérieur d'une fonction. J'utilise la fonction pass-by-reference pour qu'il n'y ait qu'un seul tableau par catégorie et non plusieurs copies du tableau pour une catégorie.

function categoriesToTree(&$categories) {

Une carte permet de rechercher rapidement les catégories. Ici, j'ai également créé un tableau fictif pour le niveau "Root".

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

J'ai ajouté un autre champ, les sous-catégories, à chaque tableau de catégories, et je l'ai ajouté à la carte.

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

Boucle à nouveau dans chaque catégorie, en s'ajoutant à la liste des sous-catégories de son parent. La référence est importante ici, sinon les catégories déjà ajoutées ne seront pas mises à jour lorsqu'il y aura plus de sous-catégories.

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

Enfin, renvoyer les sous-catégories de cette catégorie fictive qui font référence à toutes les catégories de premier niveau._

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

}

Utilisation :

$tree = categoriesToTree($categories);

Et voici le code en action sur Codepad .

Answer 3

Voir la méthode :

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;
}

Answer 4

J'ai eu le même problème et je l'ai résolu de la façon suivante : récupérer des lignes de chat dans la base de données et pour chaque catégorie racine, construire un arbre, en commençant par le niveau (profondeur) 0. Ce n'est peut-être pas la solution la plus efficace, mais elle fonctionne pour moi.

$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. Je suis conscient que le PO cherche une solution sans requêtes DB, mais celle-ci implique une récursion et aidera toute personne qui est tombée sur cette question en cherchant une solution récursive pour ce type de question et qui n'a pas peur des requêtes DB.