[JAVA] Alberi binari di ricerca e Heap

[DoctorZ]

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

Codice: Seleziona tutto
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;

[DoctorZ]

Proprio nessuno è in grado di svolgere il primo esercizio?

[astorcas]

Proprio nessuno è in grado di svolgere il primo esercizio?

Oltre il fatto che questo commento potrebbe apparire un po' offensivo e provocante, non credi che dovresti proporre tu un'idea su cui ragionare insieme ad altri?
Lo scopo di questo forum non è quello di fare esercizi agli altri ma di aiutarli a portarli a termine. ;)

[DoctorZ]

Pronti :)


class Albero {

Albero left,right; int val;

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


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);
}
}
}


Ora, un paio di precisazioni.

Questo che segue è la rappresentazione grafica dell'albero che abbiamo sviluppato (scusate la qualità ma ho usato paint :) )

http://img521.imageshack.us/img521/3153/alberock6.jpg


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 ho dato in pasto all'esercizio un albero con profondità 2, di conseguenza automaticamente sappiamo che il nodo superiore di uno è 1.

1 glielo do io con: static int livelloDaStampare = 1;
ovvero stamperà il livello 1, ma 1 è una costante perchè glielìho voluta passare io, "n" invece 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"

Quindi, se non fossimo a conoscenza del numero dei nodi dell'albero in input come facciamo a calcolarne la profondità..??

Il problema è attraversare un albero del quale non si conosce il numero di nodi di cui è formato..

[wingman87]

n è un parametro della funzione, non devi calcolarlo tu. Detto questo mi chiedo perché il vostro prof ha aggiunto quella nota : "n è al massimo di uno superiore alla profondità dell'albero" che secondo me significa che n è al massimo profondità+1, ma non vedo perché mettere questa restrizione (insensata) perché tanto se ad esempio con un albero come quello che hai disegnato passassi un n maggiore della profondità (ad esempio 5) basterebbe non stampare nulla, non è necessario specificarlo nel testo (oltretutto secondo me il prof ha fatto un errore, n dovrebbe essere al massimo =profondità, non =profondità+1 se proprio vogliamo specificarlo)...
Ad ogni modo quello che devi fare è scrivere un metodo generale per un qualsiasi n. Quando poi richiamerai il metodo passerai un n <= profondità (secondo me).

[DoctorZ]

Intanto ti ringrazio per l'intervento.
Non credo sia come dici tu, però mi hai messo la pulce.

Ti riporto di nuovo il testo qui sotto (che effettivamente non è affatto chiaro):

"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"

per come lo interpreto io, lui vuole che stampi tutti i nodi di un certo livello, quindi che so per esempio: 1 e 2 (guarda l'immagine) fanno entrambi parte del livello 1.

http://img521.imageshack.us/img521/3153/alberock6.jpg

Però non mi dice che devo stampare il livello 1 (che era un esempio), ma il livello n.
Il livello n, dove n è al massimo di uno superiore alla profondità dell'albero.
La profondità totale dell'albero è la profondità dell'ultimo nodo non nullo?
Se è così, credo voglia farmi stampare il penultimo nodo dell'albero, ovvero profondità meno 1.
Quindi il livello 1, comprendente i nodi 1 e 2.

[wingman87]

Secondo me non intende un n preciso, altrimenti avrebbe detto: "dove n è di uno superiore alla profondità dell'albero" e non "dove n è al massimo di uno superiore alla profondità dell'albero". E siccome n non è precisato sarà un parametro della funzione (credo)

[DoctorZ]

La mia domanda è: esiste un modo per calcolare la profondità di un albero del quale non si conosce il numero di nodi di cui è formato?

Pensavo di calcolare la profondità de un albero in input con n nodi
incrementando un contatore, che aumenta fino a quando non trovo un nodo che ha due foglie..

consigli e pareri?

[wingman87]

E' semplice con un metodo ricorsivo:

private int profonditaInternal(){
if(left==null && right==null)
return 0;
int max=0;
if(left!=null)
max=1+left.profonditaInternal();
if(right!=null){
int b=1+right.profonditaInternal();
if(b>max)
max=b;
}
return max;
}
Va messo nella classe dei nodi e lo richiami sulla root.

[DoctorZ]

esatto, più o meno come lo avevo fatto io
con due variabile per il confronto maggiore/minore

e testando il tuo codice mi stampa due volte
proprio come faceva il mio

in pratica, ti stampa la profondità del sottoalbero sinistro
e poi quella del sottoalbero destro

io invece avrei bisogno di stamparne una sola ovvero quella dell'intero albero

prova, vedrai che stampa ad esempio

1
2

[wingman87]

E' impossibile, per due motivi:
1- Il metodo che ho scritto non stampa niente, ritorna solo
2- Va richiamato solo sulla root, quindi ritornerà un solo valore

[DoctorZ]

Mi spiego meglio:

il tuo metodo non stampa, ma io l'ho fatto stampare
proprio come avevo fatto con il mio
ed effettivamente stampa la profondità, ma ne stampa 2 ovvero, quella dell'albero sx e dell'albero dx.

Il discorso di richiamarlo sulla radice se l'ho compreso bene avevo provato
passando al tuo metodo solo la root, invece dei soli due sottoalberi, ma poi la somma di 1 non credo sarebbe permessa tra un intero ed un oggetto albero, qui intendo

max=1+left.profonditaInternal();

un errore me lo dava, simile a quello che ti ho descritto

[wingman87]

Mi spiego meglio:

il tuo metodo non stampa, ma io l'ho fatto stampare
proprio come avevo fatto con il mio
ed effettivamente stampa la profondità, ma ne stampa 2 ovvero, quella dell'albero sx e dell'albero dx.
Ma così non è più il mio metodo :mbe:

Il discorso di richiamarlo sulla radice se l'ho compreso bene avevo provato
passando al tuo metodo solo la root, invece dei soli due sottoalberi,
Non è che devi passare qualcosa al metodo, devi invocarlo tramite la root, non so bene come hai definito l'albero ma ci sarà un altro metodo nell'albero con qualcosa di questo tipo:

public int profondita(){
if(root==null)
return -1;
return root.profonditaInternal();
}
ma poi la somma di 1 non credo sarebbe permessa tra un intero ed un oggetto albero, qui intendo

max=1+left.profonditaInternal();

un errore me lo dava, simile a quello che ti ho descritto
left.profonditaInternal() non è un oggetto albero, è una chiamata a funzione che ritorna un intero, quindi la somma la puoi fare tranquillamente