Recursivite - Creation d'un arbre dans un array

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


--
Discussions et débats sur l'actualité: http://www.sujets-d-actu.eu
Réseau IRC Francophone: http://www.crazy-irc.net
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
Olivier Miakinen
Le #66235

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.

Thief13
Le #65927
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
Le #65618
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

CrazyCat
Le #65614
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

CrazyCat
Le #65615
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

Thief13
Le #65326
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.

Publicité
Poster une réponse
Anonyme