[JAVA] Alberi binari di ricerca e Heap

[JDoc]

Buongiorno Dottori

Sto cercando di capire come sviluppare delle funzioni inerenti agli alberi binari di ricerca e come strutturarne il relativo codice. Vi ho riportato sotto alcuni esercizi, in ordine di importanza. Sono soprattutto i primi due che mi interesserebbe riuscire a svolgere, perchè sono esercizi presi dalle esercitazioni di laboratorio, alle quali purtroppo non ho la fortuna di poter partecipare per motivi di lavoro.
Riuscire a svolgere questi esercizi mi darebbe modo di poter avere una base sulla quale poter affrontare l'ultima parte che mi rimane da svolgere per l'intero esame, che sarà certamente più complesso, ma li esercizi che vedete riportati qui sotto ne sono le fondamenta. Se non sono in grado di svolgere questi, sono in alto mare.
La teoria sugli alberi la conosco, l'ho studiata. Ma vorrei svolgere in maniera corretta questi esercizi per avere una base pratica da cui partire.

Ringrazio vivamente chiunque mi possa dare una mano.


Esercizio 1

(1) Scrivere in java un algoritmo ricorsivo che scrive, da sinistra a destra, tutti
i nodi di livello n di un albero binario, dove n è al massimo di uno superiore alla
profondità dell'albero. Implementare l'algoritmo in Java, come metodo statico
all'interno del main, dove gli alberi siano implementati come istanze della classe

class Albero {
Albero left,right; int val;
Albero (int i, Albero a, Albero b) {
left = a;
right = b;
val = i;
}
}

(2) Determinare il numero di chiamate ricorsive del metodo come funzione della profondità dell'albero;



Esercizio 2

(1) Scrivere in java un algoritmo ricorsivo che scrive, da sinistra a destra, tutti i
nodi di livello n di uno heap, dove n e' al massimo di uno superiore alla profondita' dello heap;

(2) Determinare, mediante opportuna relazione di ricorrenza, il numero di
chiamate ricorsive del metodo come funzione della dimensione dello heap;



Esercizio 3

(1) Scrivere in java un algoritmo ricorsivo che determina se un albero binario di
interi e' un albero di ricerca;

(2) Determinarne il tempo di calcolo nel caso peggiore in funzione del
numero di nodi dell'albero;



Esercizio 4

(1) Scrivere in java un algoritmo iterativo ed uno ricorsivo
che determinano la profondita' di un elemento in un albero di ricerca,
assumendo che l'elemento sia presente;

(2) Determinarne il tempo di calcolo nel caso peggiore in funzione del
numero di nodi dell'albero;

[P.Congiusti]

Eheheh... bello "Algoritmi e strutture dati"... ci ho dovuto studicchiare un bel po', ma e' uno di quegli esami che ti ritorneranno utili x la tua carriera.

Visto che la teoria hai detto di conoscerla non dovrebbe esserti difficile strutturare dei semplici esercizi. Certo, ci vuole tempo, ma solo cosi' puoi imparare.

In bocca al lupo.

[JDoc]

Grazie per l'intervento P.Congiusti

il fatto di sapere la teoria aiuta, ma mi piacerebbe avere almeno il primo esercizio svolto, di modo da poter avere per lo meno uno straccio di esempio, visto che ai laboratorio non sono potuto andare e di soluzioni da cui poter partire a svolgere altri esercizi non ne ho.

Se mi date una mano col primo sarei grato insomma. Non è certo un esame questo..

[JDoc]

Proprio nessuno è in grado di svolgere il primo esercizio?

[non_pervenuto]

Ok, visto che sono a lavoro e non ho niente da fare ci provo io...

[non_pervenuto]

Esercizio 1.1

static int livelloDaStampare = 1;

public static void main(String[] argv) {
  Albero a = new Albero(5,null,null);
  Albero b = new Albero(4,null,null);
  Albero c = new Albero(3,null,null);
  Albero d = new Albero(2,a,null);
  Albero e = new Albero(1,c,b);
  Albero root = new Albero(0,e,d);
  stampaNodiDiLivello(1,root.left,root.right);
}
	
private static void stampaNodiDiLivello(int livello , Albero alberoLeft, Albero alberoRight) {
  if (alberoLeft == null) {
    return;
  }else {
    if (livelloDaStampare == livello) {
      System.out.println(alberoLeft.val);
    }
    stampaNodiDiLivello(livello + 1,alberoLeft.left,alberoLeft.right);
  }
  if (alberoRight == null) {
    return;
  }else {
    if (livelloDaStampare == livello) {
      System.out.println(alberoRight.val);
    }
    stampaNodiDiLivello(livello + 1,alberoRight.left,alberoRight.right);	
  }
}

Enjoy...

[JDoc]

Grande non_pervenuto, funziona!

Questo dovrebbe essere l'albero che abbiamo rappresentato:



Dall'enunciato in grassetto:

"Scrivere in java un algoritmo ricorsivo che scrive, da sinistra a destra, tutti
i nodi di livello n di un albero binario, dove n è al massimo di uno superiore alla
profondità dell'albero. Implementare l'algoritmo in Java, come metodo statico
all'interno del main, dove gli alberi siano implementati come istanze della classe"

Guardando l'albero rappresentato la profondità in questo caso è 2 giusto?

la root ha profondità 0
i suoi figli sinistro e destro hanno profondità 1,
e i nipoti profondità 2

Quindi quando dice "n è al massimo di 1 superiore alla profondità" vuol dire il nodo precedente al nodo 2, quindi il nodo 1. E fin qui ci siamo. Ma hai dato in pasto all'esercizio un albero con profondità 2, di conseguenza automaticamente sai che il nodo superiore di uno è 1.

Ma se non fossimo a conoscenza del numero dei nodi dell'albero in input?
Provo a farlo!

Grazie per l'aiuto non_pervenuto!

[non_pervenuto]

Il testo dell'esercizio non mi era molto chiaro così ho interpretato, pensando che "n" fosse un dato di input. Cioè: "Stampami tutti i nodi di livello n".

Il codice che ti ho postato funziona con qualsiasi profondità, non sono andato oltre i due livelli per non incasinarmi con la creazione dell'albero...

Pensa che nella prima prova avevo creato loop collegando un nodo figlio con un parente (non mi ricordo se il nonno o il bisnonno)...

[JDoc]

Originariamente inviato da non_pervenuto
Il testo dell'esercizio non mi era molto chiaro così ho interpretato, pensando che "n" fosse un dato di input. Cioè: "Stampami tutti i nodi di livello n".

Il codice che ti ho postato funziona con qualsiasi profondità, non sono andato oltre i due livelli per non incasinarmi con la creazione dell'albero...

Pensa che nella prima prova avevo creato loop collegando un nodo figlio con un parente (non mi ricordo se il nonno o il bisnonno)...

si funziona con qualsiasi profondità perchè gliela dai tu con:

static int livelloDaStampare = 1; //ovvero stamperà il livello 1, ma è una costante

"n" non è dato nel testo

"dove n è al massimo di uno superiore alla profondità dell'albero"

quindi presumo si debba calcolare prima la profondità dell'albero
e successivamente, conoscendo la profondità, fare "profondità meno 1"

Anche voi l'avete intesa così o sto vaneggiando? :berto:

[non_pervenuto]

Sarà che è venerdì ma il testo non mi è ancora chiaro...

Comunque io ti ho indicato la via... ora sta a te percorrerla...