public class IntBST {
protected IntBSTNodo root; //nodo radice
//costruttore
public IntBST() {
root = null;
}
public boolean IsEmpty() {
return (root == null);
}
/* metodi per attraversamento: preorder, inorder, postorder
ricerca, inserimento e cancellazione
*/
// *********ATTRAVERSAMENTO*******************
//attraversamento in profondità: PREorder (VLR)
protected void preorder(IntBSTNodo p, Lista l) {
if (p != null) {
l.InsertTail(p.visit());
preorder(p.left, l);
preorder(p.right, l);
}
}
//attraversamento in profondità: INorder (LVR)
protected void inorder(IntBSTNodo p, Lista l) {
if (p != null) {
inorder(p.left, l);
l.InsertTail(p.visit());
inorder(p.right, l);
}
}
//attraversamento in profondità: POSTorder (LRV)
protected void postorder(IntBSTNodo p, Lista l) {
if (p != null) {
postorder(p.left, l);
postorder(p.right, l);
l.InsertTail(p.visit());
}
}
//Metodi pubblici di attraversamento dalla radice
public Lista preorder() {
Lista lsttmp = new Lista();
preorder(root, lsttmp);
return lsttmp;
}
public Lista inorder() {
Lista lsttmp = new Lista();
inorder(root, lsttmp);
return lsttmp;
}
public Lista postorder() {
Lista lsttmp = new Lista();
postorder(root, lsttmp);
return lsttmp;
}
//***********INSERIMENTO ITERATIVO**********************
public boolean inserisci(int val) {
if (root == null) //albero vuoto...
root = new IntBSTNodo(val); //...crea radice!
else {
IntBSTNodo aux = root, prev = null; //usa aux=nodo corrente e prev = nodo preced.
while (aux != null) { //scorre nodi fino a foglia
if (val == aux.key) //se la chiave è già nell'albero...
return false; //...non la inserire ed esci, segnala con "false"!
prev = aux; //copia nodo corrente in prev
if (val < aux.key) //chiave cercata minore del valore nel nodo corrente...
aux = aux.left; //...prendi il ramo sinistro!
else //altrimenti...
aux = aux.right; //...prendi il ramo destro!
} //continua fino ad arrivare ad una foglia
if (val < prev.key) //prev contiene l'ultimo nodo(foglia) esaminato
prev.left = new IntBSTNodo(val); //chiave minore: inserisci nel ramo sx
else //altrimenti...
prev.right = new IntBSTNodo(val); //inserisci nel ramo dx.
}
return true; //inserimento effettuato: segnalalo con "true"!
}
//***********INSERIMENTO RICORSIVO**********************
protected boolean recursiveins(int val, IntBSTNodo p, IntBSTNodo prev) {
if (root == null) //albero vuoto...
root = new IntBSTNodo(val); //...crea radice!
else if (p == null) { //FINE attraversamento albero:
if (val < prev.key) //chiave minore della foglia esaminata...
prev.left = new IntBSTNodo(val); //...inserisci nel ramo sinistro!
else //altrimenti...
prev.right = new IntBSTNodo(val); //inserisci nel ramo destro!
}
else //stiamo attraversando l'albero:
if (val == p.key) //se la chiave è già nell'albero...
return false; //...non la inserire ed esci; segnala con "false"
else {
prev = p; //copia nodo corrente in prev
if (val < p.key) //chiave cercata minore del valore nel nodo corrente...
recursiveins(val, p.left, prev); //...prova inserimento nel ramo sinistro!
else //altrimenti...
recursiveins(val, p.right, prev); //...prova inserimento nel ramo destro!
}
return true; //inserimento effettuato: segnalalo con "true"!
}
//Metodo pubblico di inserimento ricorsivo
public boolean recursiveins(int val) {
return recursiveins(val, root, null);
}
//************RICERCA ITERATIVA****************
protected IntBSTNodo ricerca(IntBSTNodo p, int val) {
while (p != null) //fino a quando incontri dei nodi...
if (val == p.key) return p; //se trovi la chiave allora esci e restituisci nodo!
else if (val < p.key) p = p.left; //chiave minore: prendi il ramo sinistro...
else p = p.right; //...altrimenti prendi il ramo destro
return null; //Nessuna chiave trovata!
}
public IntBSTNodo ricerca(int val) {
return ricerca(root, val);
}
//************RICERCA RICORSIVA****************
protected IntBSTNodo recursivesearch(IntBSTNodo p, int val) {
if (p == null || p.key == val) return p; //albero vuoto o fine albero? allora esci!
if (val < p.key) return recursivesearch(p.left, val); //chiave minore: prova ricerca nel ramo sx
else return recursivesearch(p.right, val); //altrimenti prova ricerca nel ramo destro
}
public IntBSTNodo recursivesearch(int val) {
return recursivesearch(root, val);
}
/* ****************************************************
****************METODI SU ESERCIZI******************
**************************************************** */
//*******PREDECESSORE di una chiave (iterativo)***************
public int predecessore(int val) {
IntBSTNodo p = root, prev = null; //cerca la chiave nell'albero...
while (p != null && p.key != val) {
prev = p;
if (val < p.key) p = p.left;
else p = p.right;
}
if (p != null && p.left != null) { //se esiste ed ha un sottoalbero sx non vuoto...
IntBSTNodo temp = p.left; //spostati nel ramo sx
while (temp.right != null) //finchè trovi nodi a dx da visitare...
temp = temp.right; //...vai nel ramo destro
return temp.key; //fine attraversamento: prev è la foglia più a dx!
}
else //se non esiste la chiave o non ha sottoalbero sx...
throw new NessunPredecessoreException(); //...lancia eccezione!
}
//*******SUCCESSORE di una chiave (iterativo)***************
public int successore(int val) {
IntBSTNodo p = root, prev = null; //cerca la chiave nell'albero...
while (p != null && p.key != val) {
prev = p;
if (val < p.key) p = p.left;
else p = p.right;
}
if (p != null && p.right != null) { //se esiste ed ha un sottoalbero dx non vuoto...
IntBSTNodo temp = p.right; //spostati nel ramo dx
while (temp.left != null) //finchè trovi nodi a sx da visitare...
temp = temp.left; //...vai nel ramo sinistro
return temp.key; //fine attraversamento: prev è la foglia più a dx!
}
else //se non esiste la chiave o non ha sottoalbero sx...
throw new NessunSuccessoreException(); //...lancia eccezione!
}
//**************CANCELLAZIONE PER FUSIONE***********************
public void cancellaPerFusione(int val) {
IntBSTNodo tmp, nodo, p = root, prev = null;
while (p != null && p.key != val) { //trova nodo p con elemento val
prev = p;
if (val < p.key) p = p.left;
else p = p.right;
}
nodo = p;
if (p != null && p.key == val) { //p è il nodo da cancellare (nodo==p)
if (nodo.right == null) nodo = nodo.left; //nodo sx (se esiste) sarà attaccato a genitore (prev)
else if (nodo.left == null) nodo = nodo.right;
else { //Inizio fusione:
tmp = nodo.left; //spostati a sx
while (tmp.right != null) //trova predecessore
tmp = tmp.right;
tmp.right = nodo.right; //connetti predec. a sottoalb. dx
nodo = nodo.left; //prepara nodo sx ad essere attaccato a genitore (prev)
} //fine algoritmo fusione
if (p == root) root = nodo; //se elem da eliminare era root allora nodo è root!
else if (prev.left == p) prev.left = nodo;//attacca nodo ex figlio di p a genitore di p
else prev.right = nodo;
}
else if (root != null) //chiave non presente
throw new ChiaveNonPresenteException();
else
throw new BSTVuotoException();
}
//**************CANCELLAZIONE PER SOSTITUZIONE***********************
public void cancellaPerSostituzione(int val) {
IntBSTNodo tmp, previous, nodo, p = root, prev = null;
while (p != null && p.key != val) { //trova nodo p con elemento val
prev = p;
if (val < p.key) p = p.left;
else p = p.right;
}
nodo = p;
if (p != null && p.key == val) { //p è il nodo da cancellare (nodo==p)
if (nodo.right == null) nodo = nodo.left; //nodo sx (se esiste) sarà attaccato a genitore (prev)
else if (nodo.left == null) nodo = nodo.right;
else { //Inizio sostituzione:
tmp = nodo.left;
previous = nodo;
while (tmp.right != null) { //trova predecessore di nodo
previous = tmp; //memorizza nodo padre di predec.
tmp = tmp.right;
}
nodo.key = tmp.key; //sostituisci valore nodo con valore predec.
if (previous == nodo)
previous.left = tmp.left;
else
previous.right = tmp.right;
} //fine algoritmo sostituzione
if (p == root) root = nodo; //se elem da eliminare era root allora nodo è root!
else if (prev.left == p) prev.left = nodo;//attacca nodo ex figlio di p a genitore di p
else prev.right = nodo;
}
else if (root != null) //chiave non presente
throw new ChiaveNonPresenteException();
else
throw new BSTVuotoException();
}
//***************MASSIMO E MINIMO (iterativo)************************
public int max() {
if (root == null)
throw new BSTVuotoException();
IntBSTNodo p = root;
while (p.right != null) //segue sempre il ramo dx
p = p.right;
return p.key;
}
public int min() {
if (root == null)
throw new BSTVuotoException();
IntBSTNodo p = root;
while (p.left != null) //segue sempre il ramo sx
p = p.left;
return p.key;
}
//***************MASSIMO E MINIMO (ricorsivo)************************
protected int recursiveMax(IntBSTNodo p, IntBSTNodo prev) {
if (p == null) return prev.key;
else return recursiveMax(p.right, p);
}
public int recursiveMax() {
if (root == null)
throw new BSTVuotoException();
return recursiveMax(root, null);
}
protected int recursiveMin(IntBSTNodo p, IntBSTNodo prev) {
if (p == null) return prev.key;
else return recursiveMin(p.left, p);
}
public int recursiveMin() {
if (root == null)
throw new BSTVuotoException();
return recursiveMin(root, null);
}
//**************ALTEZZA DI UN NODO (ricorsivo)************************
protected int altezza(IntBSTNodo p) {
if (p == null) return 0; //albero vuoto? allora restituisci 0!
int a = altezza(p.left); //metti in a altezza ramo sx
int b = altezza(p.right); //metti in b altezza ramo dx
if (a > b) return a + 1; //restituisci ramo più lungo (+1)
else return b + 1;
}
//metodo sovraccaricato per l'altezza dell'albero
public int altezza() {
return altezza(root)-1;
}
//************NUMERO DEI NODI DI UN SOTTOALBERO (ricorsivo)*****************
protected int nodi(IntBSTNodo p) {
if (p == null) return 0; //albero vuoto? allora restituisci 0!
int a = nodi(p.left);
int b = nodi(p.right);
return a + b + 1;
}
//metodo sovraccaricato per i nodi dell'albero
public int nodi() {
return nodi(root);
}
//************NUMERO DI FOGLIE DI UN SOTTOALBERO (ricorsivo)*****************
protected int foglie(IntBSTNodo p) {
if (p == null) return 0; //albero vuoto? allora restituisci 0!
else if (p.left==null && p.right==null) return 1;
else return foglie(p.left) + foglie(p.right);
}
//metodo sovraccaricato per le foglie dell'albero
public int foglie() {
return foglie(root);
}
//************RESTITUZIONE DEL "FRATELLO" DI UN NODO*************************
public IntBSTNodo fratello(IntBSTNodo p) {
IntBSTNodo aux = root, prev = null;
int val = p.key;
while (aux != null) {
if (p == aux) { //chiave trovata
if (prev != null) { //ha un padre
if (prev.left == p) return prev.right; //restituisce fratello
else return prev.left;
}
else return null; //è la radice!
}
else {
prev = aux;
if (val < aux.key) aux = aux.left; //continua ricerca BST
else aux = aux.right;
}
}
return null;
}
//***********STAMPA PSEUDO-GRAFICA DELL'ALBERO (ricorsivo)********************
protected void stampa(int b, IntBSTNodo p) {
//Attraversamento in-order RVL (da destra a sinistra)
if (p == null) return;
stampa(b + 1, p.right);
for (int k = 0; k < b; k++) System.out.print("\t\t");
System.out.println(p.key);
stampa(b + 1, p.left);
}
public void stampa() {
if (root == null)
throw new BSTVuotoException();
stampa(0, root);
}
}
class NessunPredecessoreException extends RuntimeException {
public NessunPredecessoreException() {
super("Nessun predecessore trovato");
}
}
class NessunSuccessoreException extends RuntimeException {
public NessunSuccessoreException() {
super("Nessun successore trovato");
}
}
class ChiaveNonPresenteException extends RuntimeException {
public ChiaveNonPresenteException() {
super("Chiave non presente");
}
}
class BSTVuotoException extends RuntimeException {
public BSTVuotoException() {
super("Albero vuoto!");
}
}
public class IntBSTNodo {
protected int key; //chiave a numeri interi
protected IntBSTNodo left, right; //riferimento nodo sx e dx
//costruttori
public IntBSTNodo() {
left = right = null;
}
public IntBSTNodo(int val) {
this(val, null, null);
}
public IntBSTNodo(int val, IntBSTNodo lt, IntBSTNodo rt) {
key = val;
left = lt;
right = rt;
}
//metodi pubblici
public int visit() {
return key;
}
}