JAVA: Alberi binari di ricerca e Heap

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;