/*
Scrivere un metodo Java che legga da uno stream di Input
una sequenza di interi e costruisca un albero binario bilanciato
(utilizzare eventualmente una struttura dinamica di supporto).
Definire e implementare tutte le classi accessorie utilizzate.
*/
import java.io.*;
public class Esame_18_06_2002 {
public static void main(String[] args) {
TreeFromStream();
}
public static IntBST TreeFromStream() {
//Preleva caratteri e li inserisce in una lista
MiniLista l = new MiniLista();
MiniConsoleReader r = new MiniConsoleReader();
int input;
System.out.println("Digita numeri da inserire nell'albero" +
"\n(digita '0' oppure <Invio> per finire la sequenza)");
while(true) {
try {
input = r.readInt();
} catch (ConsoleReaderException e) {input = 0;}
if (input == 0) break;
if (l.searchOrd(input) == null)
l.insertOrdered(input);
else
System.out.println("[Numero già presente]");
}
//Crea l'albero bilanciato
if (!l.isEmpty()) {
MiniBST tree = DividiEtImpera(l);
tree.print();
return null;
}
else
return null;
}
/*
Metodo ricorsivo che inserisce il contenuto di una lista ordinata
in un albero BST. Utilizza il metodo del "divide et impera" per inserire
i valori della lista partendo dal centro e progredendo ricorsivamente
nelle parti centrali delle sottoliste.
*/
public static void DividiEtImpera(MiniLista lst, MiniBST tree, int start, int end) {
if (start < end) {
int pivot = (end + start) / 2;
int cnt = 0;
Nodo n = lst.getHead();
for (; cnt < pivot - 1; n = n.getNext(), cnt++);
tree.insert(n.getInfo());
DividiEtImpera(lst, tree, pivot+1, end);
DividiEtImpera(lst, tree, start, pivot);
}
}
//Chiamata principale del metodo
public static MiniBST DividiEtImpera(MiniLista lst) {
if (!lst.isEmpty()) {
MiniBST tmp = new MiniBST();
int cnt = 0;
for (Nodo n = lst.getHead(); n != null; n = n.getNext(), cnt++);
DividiEtImpera(lst, tmp, 1, cnt+1);
return tmp;
}
return null;
}
/* inserisce un nuovo nodo all'interno dell'albero cercando di bilanciarlo
indipendentemente dalla sua chiave .
*/
public static void insertBalancedTree(MiniBST tree, int val) {
IntBSTNodo p = tree.root;
if (p == null)
p = new IntBSTNodo(val); //albero vuoto? Crea primo nodo!
else {
LLCodaObject c = new LLCodaObject();
c.enQueue(p);
while (!c.isEmpty()) {
MiniCoda liv = new MiniCoda();
while (!c.isEmpty()) {
IntBSTNodo n = (IntBSTNodo)c.deQueue();
if (n.left != null) liv.enQueue(n.left);
else {
n.left = new IntBSTNodo(val);
return;
}
if (n.right != null) liv.enQueue(n.right);
else {
n.right = new IntBSTNodo(val);
return;
}
}
c = liv;
}
}
}
}
//*******************CLASSI ACCESSORIE**************************
//Mini lista adatta all'esercizio
class MiniLista {
private Nodo head;
public MiniLista() {
head = null;
}
public Nodo getHead() {
return head;
}
public boolean isEmpty() {
return (head == null);
}
public void insertTail(int val) {
if (isEmpty())
head = new Nodo(val);
else {
Nodo aux = head;
for (; aux.getNext() != null; aux = aux.getNext());
aux.setNext(new Nodo(val));
}
}
public int deleteHead() {
if (isEmpty())
throw new EmptyListException();
else {
int val = head.getInfo();
head = head.getNext();
return val;
}
}
public Nodo searchOrd(int val) {
Nodo aux = head;
for (; aux != null && aux.getInfo() < val; aux = aux.getNext());
if (aux != null && aux.getInfo() == val)
return aux;
return null;
}
public void insertOrdered(int val) {
if (head == null)
head = new Nodo(val);
else {
if (head.getInfo() > val)
head = new Nodo(val, head);
else {
Nodo aux = head;
for (; aux.getNext() != null &&
aux.getNext().getInfo() < val;
aux = aux.getNext());
aux.setNext(new Nodo(val, aux.getNext()));
}
}
}
}
class Nodo {
private int info;
private Nodo next;
//costruttori
public Nodo(int val) {this(val, null);}
public Nodo(int val, Nodo n) {
info = val;
next = n;
}
//metodi pubblici
public void setInfo(int val) {info = val;}
public int getInfo() {return info;}
public void setNext(Nodo n) {next = n;}
public Nodo getNext() {return next;}
}
//Mini alberto BST adatto all'esercizio
class MiniBST {
protected IntBSTNodo root;
public MiniBST() {
root = null;
}
public boolean isEmpty() {
return (root == null);
}
public boolean insert(int val) {
if (isEmpty())
root = new IntBSTNodo(val);
else {
//cerca dove inserire
IntBSTNodo p = root, prev = null;
while (p != null) {
if (p.key == val) return false;
prev = p;
if (p.key < val) p = p.right;
else p = p.left;
}
if (prev.key < val)
prev.right = new IntBSTNodo(val);
else
prev.left = new IntBSTNodo(val);
}
return true;
}
public void print(IntBSTNodo p, int level) {
if (p != null) {
print(p.right, level + 1);
for (int k = 0; k < level; k++) System.out.print("\t\t");
System.out.println(p.key);
print(p.left, level + 1);
}
}
public void print() {
System.out.println("\nStruttura orizzontale dell'albero -->");
print(root, 0);
}
}
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;
}
}
class MiniCoda {
private MiniLista q;
public MiniCoda() {
q = new MiniLista();
}
public boolean isEmpty() {
return q.isEmpty();
}
public void enQueue(int val) {
q.insertTail(val);
}
public int deQueue() {
if (isEmpty())
throw new CodaEmptyException();
else
return q.deleteHead();
}
}
//Mini Lettore di valori numerici da tastiera
class MiniConsoleReader {
private BufferedReader reader;
//costruttore
public MiniConsoleReader() {
reader = new BufferedReader(new InputStreamReader(System.in));
}
public int readInt() {
int r;
try {
String inputString = reader.readLine();
r = Integer.parseInt(inputString);
} catch (NumberFormatException e) {
throw new ConsoleReaderException();
} catch (IOException e) {
throw new ConsoleReaderException();
}
return r;
}
}
//eccezione personalizzata
class ConsoleReaderException extends RuntimeException {
public ConsoleReaderException() {super("Errore Formato di lettura");}
public ConsoleReaderException(String msg) {super(msg);}
}