Newsgroup: it.comp.lang.c
Titolo: alberi n-ari

Ho bisogno di leggere da tastiera un albero n-ario etichettato con interi,
ma non ho idee per iniziare. Qualcuno mi puo' mostrare una
implementazione?
Inoltre potreste suggerirmi un libro che parla di alberi n-ari e algoritmi
ad essi relativi (ad esempio calcolo della profondita' e simili)?
Grazie,
Dario
--
Inviato il gio 20 giu 2002 07:05:03 CEST da
ppp-62-123-16-246.dial.ipervia.it
 [62.123.16.246]
http://www.neuromante.net/

 ad essi relativi (ad esempio calcolo della profondita' e simili)?
Idea base:
void proc(nodo*nodotesta){
leggi nfigli;
nodotesta.p=alloca spazio per nfigli puntatori;
nodotesta.nfigli=nfigli;
introduci nodotesta.dati;
for i da 0 a nfigli-1{
nodotesta.p[i]=malloc di 1 nodo;
proc(nodotesta.p[i]);
}
}
così hai n figli; se n è fisso, lo passi come parametro a proc e nelle varie
chiamate ricorsive, e inoltre non devi allocare a run-time l'array di
puntatori, ma avrai il campo p come nodo*p[N]; dove N è la costante che
indica il numero di figli.
Per il libro, non ti so dire. Per il calcolo della profondità, ritengo che
non esista di meglio di una visita ricorsiva con una variabile globale(o
meglio static per la procedura) che indica il livello massimo e un'altra
static per la procedura che indica la profondità corrente(non ho studiato
algoritmi quindi non ti so dire esattamente). Ciao!
--
Paolo Giarrusso
Per rispondere togliere solo "TOGLIMI" dall'indirizzo, non _spam.

ad essi relativi (ad esempio calcolo della profondita' e simili)?
non mi è mai capitato sottomano un libro del genere. Comunque anch'io
sono interessato, se qualcuno trova qualcosa posti il titolo.
-- 
Ciao, Giuseppe

 ):
/* inizio codice */
int profondita(TREENODEPTR t) {
  int i, ris, temp;
  if (t == NULL) return 0;
  else {
    ris = 0;
    for (i = 0; i < t->numFigli; i++) {
      temp = profondita(t->figli[i]);
      if (temp > ris) ris = temp;
    }
    return 1 + ris;
  }
}
/* fine codice */
se invece l'implementazione dell'albero n-ario è con la lista di figli
(vedi ancora mio post precedente) la funzione della profondità diventa
semplicemente:
/* inizio codice */
int profondita(TREENODEPTR t) {
  if (t == NULL) return 0;
  else return max(1 + profondita(t->figlio), profondita(t->fratello));
}
int max(int a, int b) {
  return ((a > b) ? a : b);
}
-- 
Ciao, Giuseppe

 
Penso che in the art of computer programming ci sia
tutto quello che vi serve, cmq...
* Il sito di Luc Devroyee (Non mi ricordo, cercate con google)
  Ha delle dimostrazioni sull'altezza degli alberi. (Non ricordo bene)
* Sulla mia pagina, c'e' una relazione che ho fatto per un'esame.
  Nella bibliografia, c'e' un link al computer journal, 
  di un articolo di R. Sprugnoli, Properties of binary trees
  related to position. E' interessantissimo, e ci sono link a alberi
  non binari. E sulla teoria dei grafi ho anche un libro bellissimo, 
  sempre nei link della bibliografia sulle componenti connesse. 
-- 
Massimiliano Masi - m...@MasCanc.NET
Anger is a gift ... - 
http://www.mascanc.net/~max

sistra verso destra.
piccola errata corrige: ovviamente volevo dire che è ispirata al
pre-order perché visita il nodo corrente, e poi i sottoalberi da
sinistra verso destra. Mi era sfuggito "il nodo corrente" :)
-- 
Ciao, Giuseppe