truttura dati complessa e ricorsione

[pyotrex]

Avrei bisogno di una mano per creare una funzione ricorsiva e volevo sapere se qualcuno ha già fatto una cosa del genere:

io ho una struttura dati di questo tipo:

             A            B             C

             |                          |
             |                          |
                                        |
             D                          |
                                      -----
             |                        |   |
             |                        |   |
            
             G                        E   F

supponendo che ogni lettera sia una categoria, quindi D è sottocategoria di A e così via.
Avrei bisogno di tradurre il tutto in una serie di stringhe
di questo tipo:

1
1_1
1_1_1
2
3
3_1
3_2

dove:
1 è A,
1_1 è D,
1_1_1 è G,
2 è B,
3 è C,
3_1 è E,
3_2 è F


Sto facendo tutto questo per rendere dinamico questo menu:
http://www.dynamicdrive.com/dynamici...menu/index.htm

ma se ne esiste uno di più semplice

[kuarl]

è un semplice algoritmo per percorrere un albero.

non ricordo bene l'algoritmo ma spero che questo possa essere una base per te:

/* struttura albero:
  value = valore del nodo
  child1 = puntatore al primo figlio
  child2 = puntatore al secondo figlio
*/
function percorri($tree) {
   print $tree['value'];
   if(isset($tree['child1']))
      percorri($tree['child1']);
   if(isset($tree['child1']))
      percorri($tree['child2']);
}

se un nodo può avere più figli fai un ciclo

[pyotrex]

Niente, non riesco a darne fuori

[kuarl]

Originariamente inviato da pyotrex
Niente, non riesco a darne fuori

perchè? posta maggiori dettagli e magari un po' di codice

[pyotrex]

Intanto grazie per l'attenzione.
Il menù ha profondità illimitata e un nodo può avere n figli.

Nessun problema nello scorrere il db in maniera ricorsiva, il problema stà "solo" nel tradurre le categorie in stringhe, come indicato nel primo messaggio.

La tabella che contiene i dati è di tipo

  id | id_padre | nome
  --------------------
   1      0        A
   2      0        B
   3      0        C
   4      1        D
   5      3        E
   6      3        F
   7      4        G

[kuarl]

se prendi il tutto da un database, ti serve un algoritmo per popolare l'albero, che se ben ricordo è un po' più complesso, dipende anche se vuoi che gli elementi siano ordinati o meno. In ogni caso se hai già l'albero popolato il codice diventa:

/* struttura albero:
  nome = nome del nodo
  1 = il primo figlio
  2 = il secondo figlio
  3 = .....
  ....
*/
function percorri($tree) {
   print $tree['nome'];
   $i = 1;
   while(isset($tree[$i]))
      percorri($tree[$i++]);
}

Dove $tree è strutturato al seguente modo:

 // primo albero
$tree['nome'] = 'A';
$tree[1]['nome'] = 'D';
$tree[1][1] = 'G';
// secondo albero
$tree1['nome'] = 'B';
// terzo albero
$tree2['nome'] = 'C';
$tree2[1]['nome'] = 'E';
$tree2[2]['nome'] = 'F';

se richiami la mia funzione su tutti e tre gli alberi ottieni esattamente quello che ti serve.
Secondo me dovresti concentrarti di più nel caricare l'albero dai dati che ti arrivano dal database, inoltre dovresti essere in grado di capire quali elementi non hanno padri e quindi sono la radice di un albero a se stante.
Se ti serve questo posso provare a buttare giù un paio di righe

[pyotrex]

In tutta onestà ho capito poco, ma sicuramente se butti giù altre righe non può che essermi utile. Grazie

[pyotrex]

Comincio a capirci adesso qualcosa, onestamente questo approccio non mi era minimamente passato per la testa, prova a postarmi il codice per creare l'albero, tieni conto che gli alberi potrebbero essere n e non 3 come nell'esempio, probabilmente la precisazione potrebbe essere inutile ma è meglio abbondare nelle informazioni.

[pyotrex]

Qui tu hai scritto così:

// primo albero
$tree['nome'] = 'A';
$tree[1]['nome'] = 'D';
$tree[1][1] = 'G';

non dovrebbe essere?

// primo albero
$tree['nome'] = 'A';
$tree[1]['nome'] = 'D';
$tree[1][1]['nome'] = 'G';

Poi ho un'altra domanda, i risultati che io voglio ottenere sono
1
1_1
1_1_1
2
3
3_1
3_2

come fa la funzione percorri a produrre qualcosa del genere? Spero di non fare supposizioni assurde data l'ora

[kuarl]

function inserisci(&$albero, $id, $id_padre, $nome) {
  $ris = false; 
  if($albero['id'] == $id_padre) {
      // trovato, aggiungi figlio
      $albero[] = array('id' => $id, 'nome' => $nome);
      $ris = true;
   else {
      // non trovato, cerca nei figli
      $i = 0;
      while(isset($albero[$i]))
         ris = inserisci($albero[$i++], $id, $id_padre, $nome);
   }
   return $ris;
}

$insiemeAlberi = array();
$query = mysql_query("SELECT * FROM menu ORDER BY ID");
while($rs = mysql_fetch_assoc($query))
   if($rs['id_padre'] == 0) // radice, crea un nuovo albero
      $insiemeAlberi[] = array('id' => $rs['id'], 'nome' => $rs['nome']);
   else {
      // è figlio di qualcuno, trovalo
      $trovato = false;
      for($i = 0; $i < count($insiemeAlberi) && !$trovato; $i++) // scorri tutti gli alberi
         $trovato = inserisci($insiemeAlberi[$i], $rs['id'], $rs['id_padre'], $rs['nome']);
   }

in questo modo dovremmo popolare tutti gli alberi, dico dovremmo perché non posso provarlo, è probabile che ci siano degli errori

per stamparlo basta richiamare la mia funzione di prima, con una leggera modifica:

function percorri($tree) {
   print $tree['nome'];
   $i = 0;
   while(isset($tree[$i]))
      percorri($tree[$i++]);
}

for($i = 0; $i < count($insiemeAlberi); $i++)
   percorri($insiemeAlberi[$i]);