Alberi

Sono strutture dati organizzate in modo gerarchico

Esempio di struttura gerarchica: l'organizzazione dei file: ogni cartella contiene dei file più altre cartelle

A sua volta, ogni cartella può contenere altre cartelle, ecc.

Gli alberi che vediamo noi sono più semplici, ma il principio è lo stesso

Liste-alberi

In una lista, ho una sequenza di elementi:

Per ogni elemento, ho un solo elemento successivo
(oppure zero: l'ultimo elemento non ha un successore)

Nel caso degli alberi, per ogni elementi ci possono essere due elementi successivi:

A sua volta, ognuno dei due elementi successivi può avere fino a due elementi successivi, ecc.

Esercizio

Scrivere la definizione della classe degli oggetti qui sotto

Basta la definizione delle componenti (senza metodi)

Struttura non lineare: definizione di tipo

Si parte dalle variabili di istanza.

Ogni oggetto contiene: un intero, e due riferimenti a oggetti dello stesso tipo.

Come nome della classe scelgo Albero.

Le variabili di istanza sono: un intero e due alberi.

class Albero {
  int info;
  Albero sinistro, destro;
}

È analogo alla lista:

class Nodo {
  int info;
  Nodo next;
}

Solo che ho due riferimenti a oggetti dello stesso tipo invece di uno.

Incapsulamento di Albero

Metto i metodi soliti: costruttore, trova gli elementi

class Albero {
  private int dato;
  private Albero sinistro, destro;

  public Albero(int dato, Albero sinistro, Albero destro) {
    this.dato=dato;
    this.sinistro=sinistro;
    this.destro=destro;
  }

  public int getDato() {
    return this.dato;
  }

  public Albero getSinistro() {
    return this.sinistro;
  }

  public Albero getDestro() {
    return this.destro;
  }
}

Rappresentazione grafica semplificata

Metto il primo nodo in alto, e quelli collegati sotto.

Per questo le variabili si chiamano "sinistro" e "destro"

Questa non è solo una rappresentazione grafica comoda: è una rappresentazione del concetto (ho un dato, e due dati collegati ad esso, i quali possono avere altri due dati collegati, ecc)

Alberi: nome e tipo

Questi oggetti si si chiamano alberi binari

Binari=ogni oggetto è collegato ad altri due (al massimo).

Vediamo solo alberi binari

Esercizio

Scrivere il programma che crea l'albero della figura

Si tratta di creare gli oggetti in memoria

Creazione di un albero: soluzione

Devo creare il primo oggetto, e dentro ci devo mettere 4 e i riferimenti agli altri due oggetti.

Per avere i riferimenti a questi due oggetti, li devo prima creare

Quindi, devo prima creare gli altri due oggetti (quelli con 12 e 3 dentro):

class CreaSemplice {
  public static void main(String arg[]) {
    Albero a=new Albero(12, null, null);
    Albero b=new Albero(3, null, null);

    ...
  }
}

Ora i riferimenti ai due oggetti creati si trovano in a e b, e vanno messi in un nuovo oggetto che contiene il valore 4.

class CreaSemplice {
  public static void main(String arg[]) {
    Albero a=new Albero(12, null, null);
    Albero b=new Albero(3, null, null);

    Albero c=new Albero(4, a, b);
  }
}

Stampa di tutti i nodi dell'albero

Esercizio: scrivere un metodo che stampa l'intero contenuto nell'oggetto e nei due oggetti collegati

Non serve (per ora) andare a vedere cosa c'è oltre i due oggetti collegati

Soluzione

Stampo quello che c'è nel primo oggetto, poi nei due collegati:

System.out.println(a.getDato());
System.out.println(a.getSinistro().getDato());
System.out.println(a.getDestro().getDato());

Soluzione alternativa

Uso una variabile temporanea per memorizzare il riferimento all'oggetto:

System.out.println(a.getDato());
Albero s=a.getSinistro();
System.out.println(s.getDato());
Albero d=a.getDestro();
System.out.println(d.getDato());

Esercizio

Scrivere un metodo che stampa tutti gli elementi collegati

Quindi, se i due oggetti collegati hanno altri elementi collegati a loro, vanno stampati anche quelli, ecc.

Stampa di tutti gli elementi

Il metodo è fatto in questo modo:

static void stampaTutti(Albero a) {
  ...
}

Cosa deve fare?

Deve stampare l'intero nell'oggetto a, e poi in tutti gli oggetti associati

Primo passo

Se l'oggetto è null, non stampo niente

Altrimenti, stampo quello l'intero che c'è dentro

  static void stampaTutti(Albero a) {
    if(a==null)
      return;

    System.out.println(a.getDato());

    ...
  }

Cosa manca da fare?

Passi mancanti

Devo stampare l'intero che sta in a.getSinistro(), e tutti quelli collegati

Devo stampare l'intero che sta in a.getDestro(), e tutti quelli collegati

Sia a.getSinistro() che a.getDestro() danno come risultato dei puntatori a oggetti Albero

Quindi?

Assunzione ricorsiva

Il metodo stampaTutti(Albero a) stampa tutti gli interi, a partire dal riferimento al primo

Assunzione ricorsiva: il metodo funziona

Dentro il corpo del metodo, posso invocare ancora stampaTutti, e funziona!

Semplificazione del problema

Non posso fare:

static void stampaTutti(Albero a) {
  ...
  stampaTutti(a);
  ...
}

Non posso perchè il problema non è stato semplificato

Posso fare stampaTutti(a.getSinistro()): sono meno interi da stampare

Algoritmo risolutivo

Versione ricorsiva del problema: stampare tutti gli interi significa:

• stampare l'intero nel primo oggetto
• stampare tutti gli interi di a.getSinistro()
• stampare tutti gli interi di a.getDestro()

Stampa dei nodi: programma

È un metodo ricorsivo: stampo il dato, e poi ripeto sui due riferimenti

  static void stampaTutti(Albero a) {
    if(a==null)
      return;

    System.out.println(a.getDato());
    stampaTutti(a.getSinistro());
    stampaTutti(a.getDestro());
  }

Non mi interessa cosa succede quando si invoca stampaTutti(a.getSinistro()) oppure stampaTutti(a.getDestro())

L'assunzione ricorsiva mi dice che sono corretti
(stampano l'intero nell'oggetto e in tutti quelli collegati)

Caso base della stampa

Quando a vale null, non c'è niente da stampare

Questo è anche il caso base della ricorsione:
dato che invoco il metodo su alberi sempre più piccoli, alla fine arrivo a quello vuoto

  static void stampaTutti(Albero a) {
    if(a==null)
      return;

    System.out.println(a.getDato());
    stampaTutti(a.getSinistro());
    stampaTutti(a.getDestro());
  }

Terminologia

nodi dell'albero

gli oggetti che sono collegati

radice

il primo oggetto

figli di un nodo

i due oggetti che sono collegati al nodo

foglie

nodi senza figli (due null)

sottoalbero di un albero

l'albero formato da tutti i nodi collegati a uno dei due figli

I sottoalberi

Albero=insieme dei nodi collegati a un oggetto

Il riferimento all'oggetto numero uno identifica l'albero fatto da tutti e tre i nodi

Il riferimento all'oggetto numero due identifica l'albero fatto da questo nodo e basta, dato che non ce ne sono altri collegati

Verificare se un albero contiene un valore

Esercizio: scrivere un metodo (di programma) che ritorna true se un intero sta in un albero.

Si tratta sempre di esaminare tutti i nodi dell'albero.

static boolean contiene(Albero a, int val) {
  ...
}

Presenza: algoritmo

Si guarda il primo oggetto, se non contiene il valore si guardano i sottoalberi.

Caso base: l'albero è vuoto.

• se l'albero è vuoto, ritorna false
• se il valore coincide con quello scritto nel primo oggetto, ritorna true
• altrimenti, guarda i due sottoalberi

Differenza tra figlio e sottoalbero:

figlio

il nodo che è collegato

sottoalbero

il nodo collegato (=il figlio) più tutti quelli che sono collegati ad esso

Presenza: programma

Implementa l'algoritmo

  static boolean contiene(Albero a, int val) {
    if(a==null)
      return false;

    if(a.getDato()==val)
      return true;

    return contiene(a.getDestro(), val) ||
           contiene(a.getSinistro(), val);
  }

L'ultima istruzione fa le due chiamate ricorsive, e ritorna true se almeno una delle due ritorna true.

Esercizio: costruzione di un albero

Costruire un albero che ha profondità n, e tutti i valori coincidono con 10,

Livello x=tutti i nodi a distanza x dalla radice

Profondità=massimo livello

Definizione alternativa: la profondità è il massimo numero di nodi che si possono attraversare a partire dalla radice e andando sempre avanti.

  static Albero creaUguali(int livelli) {
    ...
  }

Creazione: algoritmo

Creo il primo nodo e ci metto 10.

Devo però prima dire quali sono i suoi figli.

Quindi, i figli vanno creati per primi.

Creazione dei sottoalberi

Se faccio la chiamata ricorsiva come creaUguali(livelli), non ho semplificato il problema.

I sottoalberi sono più semplici dell'albero da generare, perchè hanno un livello di meno.

Quindi, i sottoalberi si generano con creaUguali(livello-1), poi si crea la radice.

Creazione: implementazione

Mancava il passo base: l'albero di profondità zero è l'albero vuoto.

  static Albero creaUguali(int livelli) {
    if(livelli==0)
      return null;

    Albero s=creaUguali(livelli-1);
    Albero d=creaUguali(livelli-1);

    return new Albero(10, s, d);
  }

Generazione di un albero casuale

Può essere utile per fare i test.

Generazione casuale: Math.random() genera un reale fra 0 e 1

• Stabilisco un numero massimo di livelli
• per evitare di avere sempre l'albero completo (tutti i livelli pieni), prima di creare l'albero faccio un test casuale
• i valori che metto nei nodi sono casuali

static Albero alberoCasuale(int livelli) {
  if(livelli==0)
    return null;

  if(Math.random()<0.3)
    return null;

  int r=(int) (Math.random()*21-10);
  Albero s=alberoCasuale(livelli-1);
  Albero d=alberoCasuale(livelli-1);

  return new Albero(r, s, d);
}

Come fare il test dei metodi sugli alberi

Un modo possibile:

• generare un albero casuale
• disegnare l'albero
• eseguire il metodo e stampare il risultato

Disegno di un albero

Servono queste due classi: DrawTree e DrawCanvas

Metterle nella directory dove stanno anche il programma scritto da voi

Quando si vuole disegnare un albero, basta fare:

    DrawTree.draw(a);

Viene visualizzata una finestra di questo tipo:

Disegno: note

La classe Albero deve avere le tre componenti pubbliche, altrimenti DrawTree.tree(...) non funziona:

class Albero {
  public int dato;
  public Albero sinistro, destro;

  // costruttore
  // metodi get
}

Esempio di programma completo

Vogliamo provare il metodo di presenza di un nodo in un albero

Nel programma, ci metto anche il metodo alberoCausale che abbiamo visto prima:

class Presente {
  static Albero alberoCasuale(int livelli) {
    // copiare il metodo visto prima
  }

  static boolean contiene(Albero a, int val) {
    if(a==null)
      return false;

    if(a.getDato()==val)
      return true;

    return contiene(a.getDestro(), val) ||
           contiene(a.getSinistro(), val);
  }

  public static void main(String arg[]) {
    // qui?
  }
}

Cosa fa il programma?

Genera un albero, lo visualizza, e poi invoca il metodo da provare

  public static void main(String arg[]) {
    Albero a=alberoCasuale(4);

    DrawTree.draw(a);

    System.out.print("Contiene il valore 3? ");
    System.out.println(contiene(a, 3));
  }

Attenzione! Il metodo alberoCasuale può anche generare un albero vuoto

Somma dei nodi di un albero

Esercizio: scrivere un metodo che ritorna la somma dei valore interi che stanno scritti nei nodi di un albero.

Somma dei nodi: soluzione

Se l'albero è vuoto, la somma vale zero.

Altrimenti, calcolo la somma del sottoalbero sinistro, quella del destro, ci sommo la radice.

Somma dei nodi: implementazione

Il caso base è quello dell'albero vuoto

  static int sommaAlbero(Albero a) {
    if(a==null)
      return 0;

    int i=sommaAlbero(a.getSinistro());
    int j=sommaAlbero(a.getDestro());

    return i+j+a.getDato();
  }

Programma di prova

Metto dentro anche il metodo di generazione di un albero casuale

class SommaAlbero {
  static Albero alberoCasuale(int livelli) {
    // solito metodo
  }

  static int sommaAlbero(Albero a) {
    // metodo di somma (visto prima)
  }

  public static void main(String arg[]) {
    Albero a=alberoCasuale(3);

    DrawTree.draw(a);

    System.out.println(
      "La somma dei nodi e' "
      +sommaAlbero(a));
  }
}

Il programma genera un albero casuale, lo visualizza, e poi calcola la somma

Ricorsione su alberi: principio generale

Se ho un albero a come parametro, allora le chiamate ricorsive fatte su a.getSinistro() e a.getDestro() sono corrette.

Attenzione: se il metodo ritorna un valore, questo va usato in qualche modo:

     // errore, codice inutile

  sommaAlbero(a.getSinistro());
  sommaAlbero(a.getDestro());

In Java, è anche possibile invocare un metodo che ha un valore di ritorno senza usare il valore di ritorno:

  int x=12;
  Math.sqrt(x);

Un programma con queste istruzioni non dà nessun errore

Significa: invoca il metodo, e butta via il valore di ritorno.

Ricorsione su alberi: cosa succede

Per capire cosa succede, occorre simulare il programma usando i record di attivazione.

Usiamo questo albero:

Prima chiamata

Viene creato il primo record di attivazione.

Qui a è il riferimento al primo oggetto dell'albero.

Chiamata ricorsiva

Nella seconda chiamata ricorsiva, il parametro è null:

Chiamata sull'altro sottoalbero

Ora a è il riferimento all'altro sottoalbero:

Chiamate ricorsive sui sottoalberi

La prima chiamata viene fatta sul nodo che contiene 7.

Chiamate con null

Le due chiamate vengono fatte con null, per cui ritornano 0.

Valore di ritorno

Il valore di ritorno andava messo in i, che quindi contiene 7+0+0

Nuova chiamata ricorsiva

Viene fatta la chiamata ricorsiva passando il riferimento all'altra foglia (quella che contiene il valore 4).

Due chiamate ricorsive con null

Le due chiamate ricorsive ritornano 0

Valore di ritorno

Si ritorna 4+0+0, che viene messo in j.

Valore di ritorno

Si ritorna 4+7+2, ossia 13

Il valore di ritorno dell'ultima chiamata è 13+0+1, quindi 14.

Ricorsione su alberi: riassunto

• quando si scrive il metodo, si assume che le invocazioni ricorsive sui sottoalberi funzionino.
• se una invocazione ritorna un valore, questo va usato nel modo appropriato (quindi sommaAlbero(a.getDestro()); è sbagliato;
• quando il metodo viene eseguito, si costruiscono i record di attivazione

Quando si scrive il metodo, non si deve pensare ai record di attivazione.

Rappresentazione parentetica di un albero

Se stampo i nodi di un albero in ordine, e ottengo

1 2 3

non so come è fatto l'albero.

Stampare i nodi di uno di questi tre genera comunque 1 2 3

Serve un modo per stampare l'albero in modo che si capisca come è fatto.

Rappresentazione parentetica

Si può usare per stampare un albero:

• se l'albero è vuoto, stampo ()
• altrimenti, stampo (, poi il valore della radice, i sottoalberi, e poi )

L'ordine di stampa è lo stesso (prima stampo la radice, poi i figli).

Però ci sono le parentesi, che fanno capire la struttura

Stampa parentetica: esempio

Per oguno dei tre alberi di sopra, dire come viene stampato in forma parentetica.

Stampa parentetica: terzo albero

È il più semplice: prima la radice, poi il sottoalbero sinistro e poi il destro.

(1 sott_sinistro sott_destro)

Il sottoalbero sinistro ha 2 nella radice:

(1 (2 sott_sx sott_dx) sott_destro)

Il 2 non ha figli, quindi ha due sottoalberi vuoti:

(1 (2 () ()) sott_destro)

Il sottoalbero destro ha 3 nella radice, e non ha figli, quindi ho:

(1 (2 () ()) (3 () ()))

Rappresentazione parentetica: note

• l'albero vuoto è ()
• quando un nodo non ha figli, si scrive (nodo () ())
• quando un nodo ha un solo figlio, al posto dell'altro si scrive comunque ()

Rappresentazione parentetica del primo albero

Non è vuoto, stampo ( e la radice, poi i sottoalberi, poi ).

(1 sott_sinistro sott_destro )

Il sottoalbero sinistro è composto da una radice che contiene 2, da un sottoalbero sinistro che contiene 3, e un sottoalbero destro vuoto:

(1 (2 (3 () ()) ()) sott_destro)

Il sottoalbero destro è vuoto:

(1 (2 (3 () ()) ()) ())

Stampa parentetica: implementazione

Se l'albero è vuoto, stampo ()

Altrimenti, stampo (, la radice, i sottoalberi, e poi )

  public static void stampa(Albero a) {
    if(a==null) {
      System.out.print("()");
      return;
    }

    System.out.print(" ( "+a.dato);
    stampa(a.sinistro);
    stampa(a.destro);
    System.out.print(") ");
  }

Si può anche mettere come metodo statico nella classe Albero

Non si può mettere come metodo dinamico: perchè?

Metodi statici e dinamici

Un metodo dinamico è quasi come un metodo statico in cui l'oggetto viene passato come argomento

Ci sono però delle differenze (es. sull'ereditarietà)

Una differenza è:

• al metodo statico posso passare null come argomento
• non posso invocare un metodo dinamico su null

Nel caso degli alberi, null indica l'albero vuoto

A me serve anche poter stampare l'albero vuoto

Quindi, non posso fare un metodo dinamico

Stampa e rappresentazione

Si può stampare un albero in rappresentazione parentetica

Si può anche produrre una stringa che rappresenta l'albero senza stamparla

static String parentetica(Albero a) {
  if(a==null)
    return "()";

  return "("+a.getDato()+
    parentetica(a.getSinistro())+
    parentetica(a.getDestro())+")";
}

Esercizio: dalla rappresentazione all'albero

Come è fatto l'albero che ha questa rappresentazione parentetica?

(1 () (2 (7 ()()) (4 ()()) ) ) 

Soluzione

Intanto, la radice è 1, e poi ho i due sottoalberi rappresentati da () e da ( 2 (7()()) (4()()) ):

Sottoalbero sinistro

È l'albero vuoto, per cui ci va null

Sottoalbero destro

Ha radice 2, e i sottoalberi sono (7 ()()) e (4 ()())

Ultimi sottoalberi

Il sottoalbero (7 ()()) ha radice 7 e nessun figlio.

Il sottoalbero (4 ()()) ha radice 4 e nessun figlio.

Rappresentazione parentetica: uso

Se ho un albero in memoria, lo posso stampare in rappresentazione parentetica.

Se ho la rappresentazione parentetica, so come è fatto l'albero.

Quindi, posso usare la rappresentazione parentetica per salvare un albero su file.

Esercizio

Scrivere un metodo che verifica se ogni nodo di un albero di interi è maggiore dei due figli

Soluzione

Per ogni nodo, devo fare il controllo

Controllo su un nodo:

if(a.getSinistro().getDato()>=a.getDato())
  return false;

if(a.getDestro().getDato()>=a.getDato())
  return false;

return true;

Non va bene!

Controllo sui figli

Anche se a è diverso da null, i due sottoalberi a.getSinistro() e a.getDestro() potrebbero valere null

In questo caso, a.getSinistro().getDato() è un errore!

Controllo aggiuntivo: quando vado a vedere i figli, devo sempre verificare che ci siano

if(a.getSinistro()!=null)
  if(a.getSinistro().getDato()>=a.getDato())
    return false;

if(a.getDestro()!=null)
  if(a.getDestro().getDato()>=a.getDato())
    return false;

return true;

Questo fa la verifica solo sulla radice

Metodo completo

Se l'albero è vuoto, allora la condizione è vera

Altrimenti, si fa la verifica se la radice è maggiore dei figli che esistono

Se la radice è maggiore, devo verificare la stessa cosa per gli altri nodi: faccio la invocazione ricorsiva

Codice completo del metodo

  static boolean verificaMaggiore(Albero a) {
    if(a==null)
      return true;

    if(a.getSinistro()!=null)
      if(a.getSinistro().getDato()>=a.getDato())
        return false;

    if(a.getDestro()!=null)
      if(a.getDestro().getDato()>=a.getDato())
        return false;

    return
      verificaMaggiore(a.getSinistro()) &&
      verificaMaggiore(a.getDestro());
  }

Nota: la condizione è vera se lo è in tutti e due i sottoalberi

Quindi: verifico nel primo e nel secondo, e torno true solo se tutti e due i valori di ritorno valgono true

Rappresentazione con vettori

Gli alberi si possono anche rappresentare usando i vettori (un vettore rappresenta un albero).

• la radice va in posizione 0
• se un nodo sta in posizione i, i suoi figli sono in posizione 2*i+1 e 2*i+2
• il vettore si sovradimensiona; si usa un booleano per indicare che il nodo non c'è

Esempio

Come si rappresenta con un vettore questo albero?

(1 () (2 (7 ()()) (4 ()()) ) )

La radice contiene 1, quindi in posizione 0 si mette l'oggetto con 1 e true.

Il figlio sinistro non c'è, quindi in posizione 0*2+1=1 mette il nodo con false.

Il figlio destro c'è, quindi in posizione 0*2+2 va messo un nodo, che contiene 2 e true.

Dato che in posizione 2 ho un elemento, i figli vanno messi in posizione 2*2+1 e 2*2+2.

Rappresentazione con alberi: nodo

Ogni nodo contiene due informazioni: il valore (intero) e il booleano.

class Nodo {
  int dato;
  boolean esiste;

  public Nodo(int d, boolean e) {
    dato=d;
    esiste=e;
  }

  public int getDato() {
    return dato;
  }

  public boolean getEsiste() {
    return esiste;
  }
}

Rappresentazione con alberi: il vettore

Faccio un vettore di nodi.

  public static void main(String arg[]) {
    Nodo x[]=new Nodo[100];

Poi devo riempire il vettore.

Esempio: stampa di un albero

Nella invocazione ricorsiva, passo anche la posizione da cui devo iniziare la stampa.

  static void stampa(Nodo a[], int pos) {
    if(a[pos].getEsiste() == false)
      return;

     System.out.print("( "+a[pos].getDato());
     stampa(a, pos*2+1);
     stampa(a, pos*2+2);
     System.out.print(" )");
  }

Esercizio

Fare la somma dei nodi su un albero rappresentato con un vettore.