Recursivite - Creation d'un arbre dans un array

[CrazyCat]

Bonjour,

j'essaye de stocker un arbre extrait d'une base de données dans un
tableau de données.
La structure de la base est simple:
id -> l'id de l'élément
parent_id -> l'id du parent (0 si on est à la racine)
name -> le nom de l'objet

J'ai donc une requete: SELECT * FROM table ORDER BY parent_id ASC, id ASC

J'ai fait une petite fonction qui arrive à me créer l'arbre jusqu'au
niveau -2 mais impossible de trouver comment la rendre récursive pour
atteindre le niveau -n

Ma fonction actuelle:

function addChild($id, $parent, $name) {
if ($parent == 0) {
$tree[$id] = Array('id' => $id, 'titre' => $name);
} else {
if (array_key_exists($parent, $this->tree)) {
$tree[$parent][$id] = Array('id' => $id, 'titre' => $name);
} else {
foreach($this->tree as $cpid => $row) {
if (array_key_exists($parent, $row)) {
$tree[$cpid][$parent][$id] = Array('id' => $id,
'titre' => $name);
}
}
}
}
}

Merci à ceux qui pourront me donner un petit coup de main.

[Olivier Miakinen]

Post by CrazyCat
j'essaye de stocker un arbre extrait d'une base de données dans un
tableau de données.

Plus exactement, j'ai l'impression que tu essayes de recréer un arbre.

Post by CrazyCat
id -> l'id de l'élément
parent_id -> l'id du parent (0 si on est à la racine)
name -> le nom de l'objet

Je vais supposer que tu as déjà mis tout ça dans un bête tableau plat,
par exemple :

$liste = Array():
$liste[] = Array('id' => 4, 'parent' => 2, 'name' => 'quatre');
$liste[] = Array('id' => 3, 'parent' => 0, 'name' => 'trois');
$liste[] = Array('id' => 5, 'parent' => 0, 'name' => 'cinq');
$liste[] = Array('id' => 2, 'parent' => 5, 'name' => 'deux');
$liste[] = Array('id' => 1, 'parent' => 5, 'name' => 'un');

Tu peux bien sûr remplacer ça par le résultat de ta requête SQL, mais
j'ai préféré ne pas m'aventurer là-dedans vu que je ne connais pas les
fonctions d'accès aux SGBD.

Post by CrazyCat
function addChild($id, $parent, $name) {
if ($parent == 0) {
$tree[$id] = Array('id' => $id, 'titre' => $name);
} else {
if (array_key_exists($parent, $this->tree)) {
$tree[$parent][$id] = Array('id' => $id, 'titre' => $name);
} else {
foreach($this->tree as $cpid => $row) {
if (array_key_exists($parent, $row)) {
$tree[$cpid][$parent][$id] = Array('id' => $id,
'titre' => $name);
}
}
}
}
}

Voici un essai, non testé. Si cela fonctionne comme je le crois,
n'importe quelle valeur devrait être accessible directement sous
la forme $tree[$id], mais en outre tu devrais avoir la structure
d'arbre à partir de $tree[0].

$tree = Array();
foreach ($liste as $item) {
$id = $liste['id'];
if (!isset($tree[$id])) {
/* Il a pu être déjà créé par un de ses enfants,
* sinon on le crée ici */
$tree[$id] = Array();
}

$tree[$id]['id'] = $id;
$tree[$id]['titre'] = $liste['name'];

$parent = $liste['parent'];
if (!isset($tree[$parent])) {
/* Il a pu être déjà créé pour lui-même, ou par un
* autre de ses enfants, sinon on le crée ici */
$tree[$parent] = Array();
}

$tree[$parent][$id] =& $tree[$id];
}

En principe ça devrait fonctionner même si un enfant est trouvé avant
son parent, comme dans mon exemple l'id 4 avant l'id 2.

[CrazyCat]

Post by Olivier Miakinen
Voici un essai, non testé. Si cela fonctionne comme je le crois,
n'importe quelle valeur devrait être accessible directement sous
la forme $tree[$id], mais en outre tu devrais avoir la structure
d'arbre à partir de $tree[0].

Je vais tester ça, et analyser très en détail pour comprendre le principe.

[Thief13]

Je n'ais qu'une seule chose à dire :
A mort les fonctions récursive dans la gestion d'arbre SQL !

C'est lourd est innadapté. pour gérer des arbre à partire de données
linéères, il y a une technique spéciale : les intervallaires.

http://sqlpro.developpez.com/cours/arborescence/

C'est un peut dure de s'y mettre, mais apres, c'est vraiment le pied !
une seul requette à la place d'une série de requette récursives
compliqué pour récupérer l'arbre, le pied quoi.

[Bobe]

Post by Thief13
http://sqlpro.developpez.com/cours/arborescence/
C'est un peut dure de s'y mettre, mais apres, c'est vraiment le pied !
une seul requette à la place d'une série de requette récursives
compliqué pour récupérer l'arbre, le pied quoi.

En revanche, trois requêtes pour ajouter ou supprimer un noeud de
l'arbre. Et il est plus que conseillé dans ce cas d'utiliser un moteur
sql supportant les transactions.

[Thief13]

Post by Bobe
En revanche, trois requêtes pour ajouter ou supprimer un noeud de
l'arbre. Et il est plus que conseillé dans ce cas d'utiliser un moteur
sql supportant les transactions.

Si tu fait plus d'insertion dans ton site qu'il est consulté, met le
hors ligne XD

Par contre, transactionnel obligatoire en effet. Mais bon, SQL supporte
les tables innodb, donc pas de probleme.

[CrazyCat]

Post by Thief13
A mort les fonctions récursive dans la gestion d'arbre SQL !
C'est lourd est innadapté. pour gérer des arbre à partire de données
linéères, il y a une technique spéciale : les intervallaires.
http://sqlpro.developpez.com/cours/arborescence/

Je connais ce principe, malheureusement je n'ai pas la main sur les
données entrées en base, je ne peux pas gérer l'arborescence. Je suis
donc obligé de faire avec ce qui existe.

PAr contre, merci pour le lien qui me servira lorsque j'aurais à créer
des systèmes d'arborescence (et non pas à simplement les utiliser).