Alberi binari con PHP

[mark2x]

Buongiorno.

Mi chiedevo: è possibile creare alberi binari ed - in generale - strutture di dati dinamiche con PHP?

Grazie sin d'ora.

[mark2x]

appo

[Insaponata]

ma tu intendi coi puntatori? non so se ci sono ...

Per fare un albero binario potresti fare così: lo salvi in un array. Se hai un libro di algoritmi e strutture dati puoi andare a vedere come si fa leggendo il capitolo dell'heap sort... oppure cerchi nel web.

Per altre soluzioni ci dovrei pensare con calma.

[mark2x]

Sì, in sostanza volevo sapere se è possibile "simulare" le strutture a puntatori col PHP...

[Insaponata]

AZZ!
http://www.phpday.it/talks/talk_base_04.php

Guarda di cosa si occupa questo certo "Giuseppe"...

Mi sa che dobbiamo arrangiarci con gli oggetti e gli array associativi

[daniele_dll]

beh ... in realtà si possono utilizzare i riferimenti

dovrebbe essere fattibile +/-

[Insaponata]

Forse dico una grossa cretinaggine, ma si potrebbe fare con gli oggetti?

Proviamoci un po':

<?

//classe dei nodi dell'albero:
class nodo
{
  var $figlio_sx;
  var $figlio_dx;
  var $chiave;
  
  function nodo($chiave)
  {
    $this->figlio_sx = NULL;
    $this->figlio_dx = NULL;
    $this->chiave = $chiave;
  }
}

//proviamo a costruire un albero di esempio:
$radice = new nodo(35);
$radice->figlio_sx = new nodo(20);
$radice->figlio_dx = new nodo(51);
$radice->figlio_dx->figlio_dx = new nodo(68);


/* dovrebbe essere così:
                35
              /    \
             20    51
            /  \  /  \
                     68
                    /  \
*/

?>

Non l'ho provata quindi non so se va oppure no

[Insaponata]

mi sa che il problema principale sarà quello di percorrere l'albero... chissà, forse una bella funzione ricorsiva risolve il problema!

[daniele_dll]

te lo sconsiglio grandemente

uccideresti tutto

ti conviene fare una cosa del tipo

$elenco_nodi = array(array($parent_primo_nodo, $primo_nodo));
while(list(, $nodo_corrente) = each($elenco_nodi))
{
  // fai quello che devi fare col nodo corrente
  // e se devi percorrere altri nodi li inserisci
  // nella lista
  //
  // Per acquisire il nodo vero e proprio fai 
  // $nodo_corrente[1] per leggere il parent $nodo_corrente[0]
}

se ti serve aggiungere altre informazioni le aggiungi a quest'elenco

[mark2x]

ALCUNE NOTE

1. Sui riferimenti, da PHP.net:

"I riferimenti in PHP sono il mezzo per accedere ad uno stesso contenuto di variabile utilizzando diversi nomi. Non si sta parlando di puntatori come in C, ma di alias nella tabella dei simboli."

2. E' ardita l'idea di Insaponata, ma credo che il PHP non lo sopporterebbe.

3. Non so, cercavo qualcosa di più simile ai puntatori di quanto esposto. Chiaro, vi ringrazio molto, è cmq solo un'idea la mia, così da poter realizzare strutture dati più veloci (a volte servono) di quelle "php-izzate" nel futuro.



Altri contributi?