Soluzione Homework 8

Vedi anche: HomeWork8aa0203, DomandeHomework8aa0203, RisultatiHomework8aa0203.

Ecco la mia soluzione, volendo è possibile estendere il main per leggere il grafo in uno qualsiasi dei 3 formati (la funzione di lettura è generale)

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef 
   struct nodo {
      int val;
      struct nodo * sx;
      struct nodo * dx;
   } Nodo;

enum ordine {PREORDINE, INORDINE, POSTORDINE};

Nodo * leggiAlbero(enum ordine tipolettura);
void stampaAlbero(Nodo * albero, enum ordine tiposcrittura);
void disallocaAlbero(Nodo * albero);

int main(int argc, char *argv[]) {

   Nodo * albero = NULL;

   /* per default leggo in preordine e stampo in postordine */
   enum ordine tipolettura = PREORDINE;
   enum ordine tiposcrittura = POSTORDINE;

   /* se ho un argomento setto il tipo di scrittura */
   if (2 == argc && argv[1]) {
      if (0 == strcmp(argv[1],"pre"))
         tiposcrittura = PREORDINE;
      else if (0 == strcmp(argv[1],"in"))
         tiposcrittura = INORDINE;
      else if (0 == strcmp(argv[1],"post"))
         tiposcrittura = POSTORDINE;
      /* qui gestire l'errore */
   }

   albero = leggiAlbero(tipolettura);
   stampaAlbero(albero,tiposcrittura);

   /* disallocazione dell'albero */
   disallocaAlbero(albero);

   return 1;
}

Nodo * leggiAlbero(enum ordine tipolettura)
{
   int esisteSx = 0;
   int esisteDx = 0;
   Nodo * radice = (Nodo *)malloc(sizeof(Nodo));
   radice->val = 0;
   radice->sx  = NULL;
   radice->dx  = NULL;

   /* se siamo in preordine leggo la radice PRIMA dei sottoalberi */
   if (PREORDINE == tipolettura)
      scanf("%d",&(radice->val));

   /* leggo i flag che indicano se esistono i sottoalberi SX e DX */
   scanf("%d%d",&esisteSx,&esisteDx);

   /* se esiste il sottoalbero SX lo leggo */
   if (esisteSx)
      radice->sx = leggiAlbero(tipolettura);

   /* se siamo in inordine leggo la radice TRA i sottoalberi */
   if (INORDINE == tipolettura)
      scanf("%d",&(radice->val));

   /* se esiste il sottoalbero DX lo leggo */
   if (esisteDx)
      radice->dx = leggiAlbero(tipolettura);

   /* se siamo in postordine leggo la radice DOPO i sottoalberi */
   if (POSTORDINE == tipolettura)
      scanf("%d",&(radice->val));

   return radice;
}

void stampaAlbero(Nodo * albero, enum ordine tiposcrittura)
{
   /* non faccio nulla se l'albero è vuoto */
   if (!albero) return;

   /* se siamo in preordine stampo la radice PRIMA dei sottoalberi */
   if (PREORDINE == tiposcrittura)
      printf("%d\n",albero->val);

   /* stampo i flag */
   printf("%d %d\n", (albero->sx ? 1 : 0), (albero->dx ? 1 : 0) );

   /* stampo il sottoalbero sinistro */
   stampaAlbero(albero->sx, tiposcrittura);

   /* se siamo in inordine stampo la radice TRA i sottoalberi */
   if (INORDINE == tiposcrittura)
      printf("%d\n",albero->val);

   /* stampo il sottoalbero destro */
   stampaAlbero(albero->dx, tiposcrittura);

   /* se siamo in postordine stampo la radice DOPO i sottoalberi */
   if (POSTORDINE == tiposcrittura)
      printf("%d\n",albero->val);
}

/* libero ricorsivamente tutti i nodi dell'albero */
void disallocaAlbero(Nodo * albero)
{
   if (!albero) return;
   disallocaAlbero(albero->sx);
   disallocaAlbero(albero->dx);
   free(albero);
}

-- AndreaSterbini - 17 Dec 2002

• Set ALLOWTOPICCHANGE = DocentiProg1Group