Newsgroup: it.comp.lang.c
Titolo: Visita

Scusate se rompo sempre con questi alberi, ma rappresentano un vero problema
per me: sono disperatamente alla ricerca di un algoritmo per una visita per
livelli di un albero binario di ricerca e uno per il calcolo di tutte le
foglie che non hanno figli, in altre parole un algoritmo che mi fornisca il
perimetro del cammino dell'albero!!!!
Grazie per l'attenzione!!!!!!
                            Marc

perimetro del cammino dell'albero!!!!
Sii piu' preciso su cosa intendi per visita per livelli.
Nel frattempo ti posto il programma per il calcolo delle foglie che non hanno
figli :
#include <stdio.h>
#include <string.h>
const int TRUE  = 1 ;
const int FALSE = 0 ;
typedef struct foglia {
	       int num ;
	       struct foglia * sotto_albero_sinistro;
	       struct foglia * sotto_albero_destro;
	       } * ptr_foglia;
void inserisci_numero( int num, ptr_foglia * radice )
{
     ptr_foglia  nodo_temp ;
     nodo_temp = (ptr_foglia) malloc( sizeof( struct foglia ) );
     nodo_temp->num = num;
     nodo_temp->sotto_albero_sinistro = NULL;
     nodo_temp->sotto_albero_destro = NULL;
     if (*radice == NULL)
	*radice = nodo_temp;
     else
     if (num <= (*radice)->num)
	inserisci_numero( num, &(*radice)->sotto_albero_sinistro );
     else
	inserisci_numero( num, &(*radice)->sotto_albero_destro );
}
void conta_foglie_senza_figli ( ptr_foglia radice, unsigned * counter )
{
    if ( radice->sotto_albero_sinistro )
       conta_foglie_senza_figli ( radice->sotto_albero_sinistro, counter ) ;
    if ( radice->sotto_albero_destro )
       conta_foglie_senza_figli ( radice->sotto_albero_destro, counter ) ;
    if ( radice->sotto_albero_sinistro == NULL  &&
         radice->sotto_albero_destro == NULL ) ++*counter ;
}
int main()
{
    ptr_foglia radice_albero = NULL ;
    unsigned num_nodi_term = 0 ;
    struct foglia foglia_trovata ;
    inserisci_numero( 10, &radice_albero );
    inserisci_numero( 5, &radice_albero );
    inserisci_numero( 15, &radice_albero );
    inserisci_numero( 3, &radice_albero );
    inserisci_numero( 13, &radice_albero );
    inserisci_numero( 7, &radice_albero );
    inserisci_numero( 14, &radice_albero );
    inserisci_numero( 6, &radice_albero );
    inserisci_numero( 8, &radice_albero );
    inserisci_numero( 20, &radice_albero );
    inserisci_numero( 30, &radice_albero );
    inserisci_numero( 19, &radice_albero );
    conta_foglie_senza_figli ( radice_albero, &num_nodi_term ) ;
    printf("numero di nodi terminali : %u\n", num_nodi_term ) ;
    return 0;
}
Skyscraper (apprezzatelo adesso : eviterete la coda)
----------------------------------------------------
 
andrea_...@bigfoot.com
----------------------------------------------------
--
Posted from 
itaca.ulysse.it
 [195.223.254.1]
via Mailgate.ORG Server - 
http://www.mailgate.org

#include <string.h>
^^^ ops ! string ? forse e' megli "stdlib.h" :))


perimetro del cammino dell'albero!!!!
Penso che, dato che dovrai fare spesso ricerca dei nodi di uno stesso
livello, potrebbe essere  conveniente una rappresentazione tramata, dove,
oltre al puntatore al figlio dx e sx, hai anche un puntatore ad un elemento
di uno stesso livello. Sarebbe però molto complicato inserire nuovi elementi
nell'albero: direi che è una soluzione per un albero in cui gli inserimenti
sono sporadici.
Potresti appoggiarti ad una lista i cui elementi sono ancora delle liste in
cui vengono inseriti tutti i nodi dello stesso livello, riempirla tramite un
classico algoritmo di visita e poi stamparla. Penso che questa soluzione,
nonostante sia meno efficiente, nonché più complessa, sia però più facile da
mantenere.
--
Francesco Trotta
http://space.tin.it/computer/ftrotta
Elimina "x_" dal mio indirizzo per mandarmi
un messaggio direttamente

Skyscraper (
s...@scraper.com
) wrote:
[ snip ]
: void inserisci_numero( int num, ptr_foglia * radice )
: {
:      ptr_foglia  nodo_temp ;
:      nodo_temp = (ptr_foglia) malloc( sizeof( struct foglia ) );
In C, questo cast non serve.
:      nodo_temp->num = num;
:      nodo_temp->sotto_albero_sinistro = NULL;
:      nodo_temp->sotto_albero_destro = NULL;
:      if (*radice == NULL)
: 	*radice = nodo_temp;
:      else
:      if (num <= (*radice)->num)
: 	inserisci_numero( num, &(*radice)->sotto_albero_sinistro );
:      else
: 	inserisci_numero( num, &(*radice)->sotto_albero_destro );
: }
Attenzione: se (*radice) e' diverso da NULL, qui si fa una malloc() 
inutile e per la quale non viene mai chiamata la free().
Ciao ciao,
Andrea
-- 
"...Unix, MS-DOS, and Windows NT (also known as the Good, the Bad, and 
 the Ugly)."
(by Matt Welsh)

inutile e per la quale non viene mai chiamata la free().
Va spostata l'allocazione all'interno dell' "if"
if (*radice == NULL) 
{
   nodo_temp = ..... malloc( .... ) ;
   nodo_temp -> .... = ....
   *radice = nodo_temp;
}
else ...
Skyscraper (apprezzatelo adesso : eviterete la coda)
----------------------------------------------------
 
andrea_...@bigfoot.com
----------------------------------------------------
--


 Evita warning in fase di compilazione.
Veramente in questo caso il compilatore non dovrebbe dare warnings dato
che in C esiste la promozione automatica da void * a qualsiasi altro
tipo puntatore. Mettere il cast invece può nascondere errori che
altrimenti il compilatore avrebbe regolarmente segnalato.
EMG

Skyscraper (
s...@scraper.com
) wrote:
: Un bel giorno, tutt'a un tratto Andrea Foco si mise a scrivere :
: >
: >In C, questo cast non serve.
: Evita warning in fase di compilazione.
Per niente. Non dovrebbero esserci warning, a meno che tu non
abbia dimenticato di includere <stdlib.h>.


altrimenti il compilatore avrebbe regolarmente segnalato.
In generale si'.
In *questo* caso e' assolutamente innocuo.


                             Marc
CiaoEcco un filetto allegato con qualcosa che fooorse potrebbe tornarti utile
(profondita e ampiezza).
Ragazzi, non mettetevi a fare le pulci perchč non me ne fotte niente.
Nel cut&paste qualcosa potrebbe essersi persa, sicuramente l'indentazione
Ciao
/* Programma per la creazione di una lista di liste DOPPIO LINKATA.
   Formato del file di acquisizione:      <nodo_padre>    <nodo_figlio>
*/
# include <stdio.h >
# include <stdlib.h>
# define ERROR 0
# define OK    1
struct nodo_figlio
{
 int nome_figlio;
 struct nodo_figlio* next_figlio;
 struct nodo_figlio* prev_figlio;
};
struct nodo_padre
{
  int nome_padre;
  int visit;
  struct nodo_padre* next_padre;
   struct nodo_padre* prev_padre;
  struct nodo_figlio* son;
};
/* Prototipi delle funzioni*/
int Leggi_Grafo ( FILE*, struct nodo_padre** );
int Insert (struct nodo_padre**, int, int );
struct nodo_padre* Scorre_Padri(struct nodo_padre*, int );
void Inserisce_Figlio_in_Testa ( struct nodo_padre*, int);
void Stampa_Grafo ( struct nodo_padre * );
struct nodo_padre* Cerca_Radice_per_Visita ( struct nodo_padre* , int );
void DFV ( struct nodo_padre*, struct nodo_padre* );
/* gestione coda  per BFV */
int Insert_Queue  ( int*, int, int*, int*, int );
int  Extract ( int*, int*,int*, int );
void BFV ( struct nodo_padre*, struct nodo_padre*, int );
/**/void Stampa_Coda(int*, int);
void main (void)                /*       M A I N       */
{
 FILE* fp;
 struct nodo_padre* LIST=NULL;
 int num_vert, new_root;
 struct nodo_padre* VRoot=NULL;  /*sorgente dalla quale effettuo le visite */
 fp = fopen ("a:grafo.txt","r");
 num_vert = Leggi_Grafo ( fp, &LIST );
 printf ("\nIl numero dei vertici che costituiscono il grafo č
-%d-\n",num_vert);
 printf ("Il grafo acquisito č rappresentato dalla seguente lista di
adiacenze:\n");
 Stampa_Grafo (LIST);
                             /*  DFV  */
 /*printf ("\nInserisci un nodo per effettuare una visita in  profonditą (DFV):
");
 scanf  ("%d",& new_root);
 VRoot = Cerca_Radice_per_Visita(LIST,new_root);
 //printf ("\nLa radice per la visita DFV č:-%d-\n",VRoot->nome_padre);
    DFV( LIST, VRoot );*/
                                /*  BFV  */
 printf ("\nInserisci un nodo per effettuare una visita in ampiezza(BFV): ");
 scanf  ("%d",& new_root);
 VRoot = Cerca_Radice_per_Visita(LIST,new_root);
 BFV(LIST, VRoot, num_vert);
}
/* Definizione delle funzioni */
int Leggi_Grafo ( FILE* fp, struct nodo_padre** List )
{
 int padre, figlio, num_vert=0 ;
 while ( fscanf (fp,"%d %d", &padre, &figlio) != EOF )
  num_vert += Insert(List,padre,figlio);
 return (num_vert);
}
/********************************************************************************/
int Insert (struct nodo_padre** List, int padre, int figlio)
{
 int n_vert = 0;
 struct nodo_padre* vert =  *List;
 struct nodo_padre* vert2=  *List;
 if ( (vert)==NULL )           /* LISTA VUOTA */
 {
  *List = vert =(struct nodo_padre*) malloc (sizeof(struct nodo_padre));
  vert->nome_padre = padre;
        vert->visit      = 0;
  vert->prev_padre = *List;
        vert->next_padre = *List;
  vert->son = NULL;
                        /* alloco anche il figlio come padre */
  vert->next_padre = (struct nodo_padre*) malloc (sizeof(struct nodo_padre));
        (vert->next_padre)->nome_padre = figlio;
  (vert->next_padre)->visit      = 0;
  (vert->next_padre)->prev_padre = vert;
  (vert->next_padre)->next_padre = vert;
  (vert->next_padre)->son = NULL;
  n_vert =2;
 }
 else
 {
  if (vert->nome_padre != padre )
  {
   vert = Scorre_Padri (*List,padre);  /* trova il padre successivamente al
quale inserisco ma potrebbe dirett dare quello giusto*/
      if ( vert->next_padre == *List )    /* padre non presente nella lista dei
padri */
   {
                vert->next_padre =(struct nodo_padre*) malloc (sizeof(struct
nodo_padre));
       (vert->next_padre)->prev_padre = vert;
    vert = vert->next_padre;
       vert->nome_padre = padre;
    vert->visit      = 0;
          vert->next_padre = *List;
          vert->son = NULL;
    n_vert = 1;
   }
      else
    vert = vert->next_padre;
  }
  /*controllo se il figlio č gia presente come padre e se non lo č lo inserisco
*/
     if (vert2->nome_padre != figlio )
  {
   vert2 = Scorre_Padri (*List, figlio);
         if ( vert2->next_padre == *List )  /* il figlio non č nella lista dei
padri */
   {
    vert2->next_padre =(struct nodo_padre*) malloc (sizeof(struct nodo_padre));
          (vert2->next_padre)->prev_padre = vert2;
    vert2 = vert2->next_padre;
          vert2->nome_padre = figlio;
    vert2->visit      = 0;
          vert2->next_padre = *List;
          vert2->son = NULL;
    n_vert += 1;
   }
  }
 }
                   /* adesso vert punta comunque al padre */
 Inserisce_Figlio_in_Testa (vert,figlio);
 return (n_vert);
}
/*********************************************************************************/
struct nodo_padre* Scorre_Padri(struct nodo_padre* vert, int padre )
{
 struct nodo_padre* fix = vert;
 for (; (vert->next_padre != fix)&&((vert->next_padre)->nome_padre!=padre);
                  vert=vert->next_padre                                   );
 return (vert);
}
/*********************************************************************************/
void Inserisce_Figlio_in_Testa ( struct nodo_padre* vert, int figlio)
{
 struct nodo_figlio* first_son;
 first_son = (struct nodo_figlio*) malloc (sizeof(struct nodo_figlio));
 first_son->nome_figlio = figlio;
 first_son->next_figlio = vert->son;
 first_son->prev_figlio = NULL;
    if ( (vert->son)!= NULL)
  (vert->son)->prev_figlio = first_son;
 vert->son = first_son;
}
/*********************************************************************************/
void Stampa_Grafo ( struct nodo_padre* List)
{
 struct nodo_padre* vert1 = List;
 struct nodo_figlio* orizz;
 printf ("\nLa lista delle adiacenze č la seguente:\n");
 do
 {
  printf ("\nNodo Padre:-%d-     ",vert1->nome_padre);
  for ( orizz=vert1->son;  orizz!=NULL; orizz= orizz->next_figlio )
   printf ("*%d***",orizz->nome_figlio);
  vert1 = vert1->next_padre;
 }
 while ( vert1 != List );
}
/**********************************************************************************/
struct nodo_padre* Cerca_Radice_per_Visita( struct nodo_padre* Root, int new_rad
)
{
    /* hp: la nuova radice richiesta esiste sempre  */
    struct nodo_padre* run;
 for ( run = Root; run->nome_padre != new_rad; run = run->next_padre );
    return(run);
}
/**********************************************************************************/
void DFV ( struct nodo_padre* List, struct nodo_padre* VRoot )
{
 struct nodo_figlio* scans_son;
 struct nodo_padre*  Sub_Rad;   /* nuova (sotto)radice da cui riparto per la DFV
*/
 VRoot->visit = 1;
 printf ("\n****%d****",VRoot->nome_padre);
 /* scandisco i figli */
    for( scans_son=VRoot->son; scans_son != NULL;
scans_son=scans_son->next_figlio )
 {
  Sub_Rad = Cerca_Radice_per_Visita(List,scans_son->nome_figlio);
  if (Sub_Rad->visit == 0 )
   DFV(List,Sub_Rad);
 }
}
/*ATTENZIONE: tale DFV mostra un solo albero, quello dato dai nodi raggiungibili
              dalla sorgente iniziale, mentre il risultato corretto dovrebbe
essere
     una foresta                                                         */
/**********************************************************************************/
int Insert_Queue ( int* vet, int nodo, int* testa, int* coda, int dim)
{
 /**/static int Ins_Q=0;
 /**/Ins_Q++;
 /**/printf("\nIns_Q=%d",Ins_Q);
 if ( (*testa) == ( (*coda)%dim +1) )
 {
  printf ("\nCoda piena:inserzione impossibile.\n");
  return (ERROR);
 }
    vet[*coda] = nodo;/****/printf ("\n*********: %d\n",vet[*coda]);
 (*coda)++;
 if ((*coda)== dim)
  (*coda) = 0;
 return (OK);
}
/**********************************************************************************/
int Extract ( int* vet, int* testa, int* coda, int dim)
{
 int nodo_del;
 /**/printf ("\nIn Extract testa=%d e coda=%d",*testa,*coda);
 if ( (*coda) == (*testa) )
 {
  printf ("\nCoda Vuota:eliminazione impossibile.\n");
  return (ERROR);
 }
 nodo_del = vet[*testa]; /* estraggo l'elemento in testa */
 (*testa)++;
 if ((*testa) == dim)
  (*testa) = 0;
 return (nodo_del);
}
/**********************************************************************************/
void BFV ( struct nodo_padre* List, struct nodo_padre* VRoot,int num_vert )
{
 int* FIFO,vertex;
 int testa=0;
    int coda =0;
 int i,nw,nf,x;   /* x č il risultato di inserz. ed estraz. dalla coda; in tal
caso
               non da mai problemi */
 struct nodo_figlio* scans_son;
 struct nodo_padre * run;
 struct nodo_padre * p;
 /**/char f;
 FIFO = (int*) malloc ((num_vert-1)* sizeof(int));
 for ( i=0; i<num_vert; i++)
  FIFO[i] = 0;
 vertex = VRoot->nome_padre;
 //x = Insert_Queue ( FIFO, vertex, & testa, &coda, num_vert);
 //printf ("\nDopo la 1 inserz coda=%d e testa=%d\n",coda,testa);
 /**/Stampa_Coda(FIFO, num_vert);scanf ("%c",&f);
 VRoot->visit = 1;
 /**/nw = 0;
 while ( vertex != ERROR )
 {
  /**/printf("\nEsamino i figli di %d",vertex);
  /**/scanf ("%c",&f);
  //printf ("\nWHILE\n");
  //nw++;
  //printf ("\n****%d****nw=%d",vertex,nw);
  //nf=0;
  /* scandisco la lista dei figli */
        /**/p = Cerca_Radice_per_Visita(VRoot,vertex);
     for( scans_son=p->son/*VRoot->son*/; scans_son != NULL;
scans_son=scans_son->next_figlio )
  {
   //nf++;
   /* cerco i figli nella lista dei padri e li metto in coda se non scoperti*/
   for ( run = VRoot; run->nome_padre != scans_son->nome_figlio;
run=run->next_padre ) ;
      /******/printf ("\nfiglio-%d-----nf=%d---",run->/*visit*/nome_padre,nf);
   if ( run->visit == 0 )   /*figlio non ancora scoperto */
   {
    /**/printf ("\nInserisco tale figlio nella coda");
    x = Insert_Queue ( FIFO,run->nome_padre,&testa,&coda,num_vert );
    /**/printf ("\nInserendo il figlio %d testa=%d e
coda=%d",run->nome_padre,testa,coda);
    //Stampa_Coda(FIFO, num_vert);scanf ("%c",&f);
    run->visit = 1;
    /**/printf ("\nMarco il figlio di %d cioe %d",vertex,run->nome_padre);
   }
  }
  /**/printf ("\nStampa della coda prima dell'estrazione:\n");
  /**/Stampa_Coda(FIFO, num_vert);
  vertex = Extract ( FIFO, &testa, &coda, num_vert);//next nodo di cui scoprirņ
i figli
  /**/printf ("\nEXTRACT fornisce vertex = %d",vertex);
  //p = Cerca_Radice_per_Visita(VRoot,vertex);
 }
 /**/printf ("\nrisultato della dfv:\n");
 /**/Stampa_Coda(FIFO, num_vert);
  /**/scanf ("%c",&f);
}
/**********************************************************************************/
void Stampa_Coda ( int* vet, int num_vert )
{
 int i;
 printf ("\nStampa della coda:\n");
 for (i=0; i<num_vert; i++)
  printf ("?-%d-?",vet[i]);
 printf ("\n");
}