Recursivite - Creation d'un arbre dans un array

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.

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

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.

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

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.

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.

Thief13 nous a dit le 06.04.2007 00:48:

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.

--
Aurélien Maille

Olivier Miakinen wrote:

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.

--
Discussions et débats sur l'actualité: http://www.sujets-d-actu.eu
Réseau IRC Francophone: http://www.crazy-irc.net

Thief13 wrote:

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/

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

--
Discussions et débats sur l'actualité: http://www.sujets-d-actu.eu
Réseau IRC Francophone: http://www.crazy-irc.net

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.