Albero binario di ricerca

[sicula83]

Ciao ragazzi, gentilmente potete dare un'occhiata a questo codice?L' ho creato io per memorizzare ed esercitarmi sui vari metodi di un albero. Di funzionare, funziona...però magari sbaglio qualcosa che a runtime non dà nessun problema. Non mi convince molto il delete, che dite?
Grazie mille

import java.util.*;
import java.io.*;

interface BSTInterface<E> //extends Iterable<E>
{
	//ritorna il numero di nodi dell'albero
	public int size();
	//ritorna l'altezza dell'albero
	public int height();
	//ritorna l'etichetta del nodo v
	public E getLabel(BSTNode<E> v);
	//ritorna il nodo contenente l'etichetta label
	public BSTNode<E> search(E label);
	//aggiungi all'albero un nuovo nodo avente come etichetta label
	public void insert(BSTNode<E> node);
	//ritorna la radice dell'albero
	public BSTNode<E> getRoot();
	//ritorna il valore più piccolo
	public BSTNode <E> minimo();
	//ritorna il valore più grande
	public BSTNode<E> massimo();
	//ritorna un array dell'albero con le chiavi dell'albero in ordine postorder
	public BSTNode<E>[]postorder();
	//ritorna un array dell'albero con le chiavi dell'albero in ordine inorder
	public BSTNode<E>[]inorder();
	//ritorna un array dell'albero con le chiavi dell'albero in ordine preorder
	public BSTNode<E>[]preorder();
	//ritorna un iteratore
	//public Iterator<E> iterator();
	//ritorna una stringa con la visita per livelli dell'albero
	public String BFSVisit();
}

class BSTNode<E>
{
	protected BSTNode<E> parent, left, right;
	protected E label;
	protected BSTNode<E>next;//mi serve solo nel caso in cui ho la cancellazione
	
	public BSTNode()
	{
		parent=null;
		left=null;
		right=null;
		label=null;
		next=null;
	}
	
	public E getLabel()
	{
		return label;
	}
	
	public BSTNode<E> getParent()
	{
		return parent;
	}
	
	public BSTNode<E> getLeft()
	{
		return left;
	}
	
	public BSTNode<E> getRight()
	{
		return right;
	}
	
	public BSTNode<E> getNext()
	{
		return next;
	}
	
	public void setLabel(E label)
	{
		this.label=label;
	}
	
	public void setParent(BSTNode<E> parent)
	{
		this.parent=parent;
	}
	
	public void setLeft(BSTNode<E> left)
	{
		this.left=left;
	}
	
	public void setRight(BSTNode<E> right)
	{
		this.right=right;
	}
}


class Tree<E extends Comparable> implements BSTInterface<E>
{
	protected int size;
	private int pos;//mi serve per le visite
	private int height;
	private BSTNode<E> root;
	
	public Tree()
	{
		size=0;
		pos=0;
		height=0;
		root=null;
	}
	
	//ritorna il numero di nodi dell'albero
	public int size()
	{
		return size;
	}
	
	//ritorna l'altezza dell'albero
	public int height()
	{
		return height;
	}
	
	//ritorna l'etichetta di un dato nodo v
	public E getLabel(BSTNode<E> v)
	{
		return v.getLabel();
	}
	
	//ritorna il nodo contenente l'etichetta label
	public BSTNode<E> search(E label)
	{
		BSTNode<E> aux=root;
		while(aux!=null && aux.getLabel().compareTo(label)!=0)
		{
			if(aux.getLabel().compareTo(label)>0)
				aux=aux.getLeft();
			else
			aux=aux.getRight();
			return aux;
		}
		return aux;
	}
	
	//aggiunge un nuovo nodo all'albero
	public void insert(BSTNode<E> node)
	{
		if(root==null)
		{
			root=node;
			node.setParent(null);
		}
		
		else
			insertRic(root, node);
		size++;
	}
	
	
	public void insertRic(BSTNode<E> x, BSTNode<E> node)
	{
		if(x.getLabel().compareTo(node.getLabel())>0)//se l'elemento chge ho è maggiore di quello che devo aggiungere, mi sposto a sx
		{
			//ma prima devo vedere se esiste il sottoalbero sx
			if(x.getLeft()!=null)//se esiste,...
			insertRic(x.getLeft(), node);
			//se invece non esiste
			else
			{
				x.left=node;
				node.setParent(x);
			}
		}
		
		//se invece l'elemento che ho è <dell'elemento che devo inserire,, allora mi sposto a dx
		else
		{
			if(x.getRight()!=null)//se esiste...
				insertRic(x.getRight(),node);//...inserisco
			else
			{
				//se invece non esiste,il nuovo nodo sarà il primo elemento del sottoalbero dx
				x.right=node;
				node.setParent(x);
			}
		}
	}
	
	//ritorna la radice
	public BSTNode<E> getRoot()
	{
		return root;
	}
	
	//cerco il minimo
	public BSTNode<E> minimo()
	{
		if(root==null) return null;
		else return minimoRic(root);
	}
	
	public BSTNode<E> minimoRic(BSTNode<E> node)
	{
		if(node.getLeft()!=null)
			return minimoRic(node.getLeft());
		else
			return node;
	}
	
	//cerco il massimo
	public BSTNode<E> massimo()
	{
		if(root==null) return null;
		else return massimoRic(root);
	}
	
	public BSTNode<E> massimoRic(BSTNode<E> node)
	{
		if(node.getRight()!=null)
			return massimoRic(node.getRight());
		else
			return node;
	}
	
	public BSTNode<E>[]postorder()
	{
		BSTNode<E>[]visit=(BSTNode<E>[]) new BSTNode[size];
		pos=0;
		ricPostorder(root,visit);
		return visit;
	}
	
	public void ricPostorder(BSTNode<E> node, BSTNode<E>[] visit)
	{
		if(node==null) return;
		ricPostorder(node.getLeft(),visit);
		ricPostorder(node.getRight(),visit);
		visit[pos++]=node;
	}
	
	public BSTNode<E>[]inorder()
	{
		BSTNode<E>[]visit=(BSTNode<E>[]) new BSTNode[size];
		pos=0;
		ricIn(root,visit);
		return visit;
	}
	
	public void ricIn(BSTNode<E> node, BSTNode<E>[]visit)
	{
		if(node==null) return;
		ricIn(node.getLeft(),visit);
		visit[pos++]=node;
		ricIn(node.getRight(),visit);
	}
	
	public BSTNode<E>[] preorder()
	{
		BSTNode<E>[]visit=(BSTNode<E>[]) new BSTNode[size];
		pos=0;
		ricPre(root,visit);
		return visit;
	}
	
	public void ricPre(BSTNode<E> node, BSTNode<E>[]visit)
	{
		if(node==null) return;
		visit[pos++]=node;
		ricPre(node.getLeft(),visit);
		ricPre(node.getRight(),visit);
	}
	
	//ritorna l'altezza dell'albero
	public int getHeight() throws EmptyTreeException
	{
		if(root==null) throw new EmptyTreeException("albero vuoto");
		return heightRic(root);
	}
	
	public int heightRic(BSTNode<E> node)
	{
		if(node==null) return 0;
		if(node.getLeft()==null && node.getRight()==null)//se node è foglia
			return 0;
		if(heightRic(node.getLeft())<heightRic(node.getRight()))
			return (1+heightRic(node.getRight()));
		else
			return (1+heightRic(node.getLeft()));
	}
	
	//visita per livelli
	public String BFSVisit()
	{
		String visit=" ";
		Queue<BSTNode<E>> Q=new Queue<BSTNode<E>>(size);
		Q.enqueue(root);
		while(!Q.isEmpty())
		{
			BSTNode<E> node=Q.dequeue();
			if(node==root) visit+=node.getLabel();
			else 
				visit+=" " +node.getLabel();
			if(node.getLeft()!=null) Q.enqueue(node.getLeft());
			if(node.getRight()!=null) Q.enqueue(node.getRight());
		}
		return visit;
	}
	
	//cancellazione di un nodo
	public void delete(BSTNode<E> x)
	{
		if(x==null) return;
		//mi dichiaro un nuovo nodo, padre del nodo da eliminare
		BSTNode<E> z=x.getParent();
		//caso foglia
		if(x.getLeft()==null && x.getRight()==null)
		{
			if(z==null) //se non ha genitore, allora sto cancellando una radice
				root=null;
			if(x==z.getLeft()) z.setLeft(null);//ho cancellato il figlio sx
			else z.setRight(null);//ho cancellato il figlio dx
			x.setParent(null);//isolo il nodo cancellato
			size--;
			return;
		}
		
		//se invece ha un solo figlio sx
		if(x.getLeft()!=null && x.getRight()==null)
		{
			if(z==null)//se il genitore non esiste
			{
				root=x.getLeft();//allora il figlio sx sarà sicuramente la radice
				root.setParent(null);
			}
			
			else
			{
				// se cancello x, suo figlio avrà come genitore, il genitore di x
				x.getLeft().setParent(z);
				if(x==z.getLeft()) z.setLeft(x.getLeft());//se x era il figliosx di z, allora z avrà come figlio sx, il figlio sx di x
			}
			size--;
			return;
		}
		
		//ha solo figlio dx
		if(x.getLeft()==null && x.getRight()!=null)
		{
			if(z==null)
			{
				root=x.getRight();
				root.setParent(null);
			}
			else
			{
				x.getRight().setParent(z);
				if(x==z.getRight()) z.setRight(x.getRight());
			}
			size--;
			return;
		}
		//se invece devo cancellare un nodo interno
		if(x.getLeft()!=null && x.getRight()!=null)
		{
			BSTNode<E> v=x.getNext();
			x.setLabel(v.getLabel());
			delete(v);
			return;
		}
	}
}

	class EmptyTreeException extends RuntimeException
{
	public EmptyTreeException(String err)
	{
		super(err);
	}
}

class Queue<E>
{
	E[]Q;
	int size,head,tail;
	public Queue(int capacity)
	{
		size=0;head=tail=0;
		Q=(E[]) new Object[capacity];
	}
	
	public boolean isEmpty()
	{
		return(size==0);
	}
	
	public void enqueue(E elem)
	{
		Q[tail++]=elem;
		size++;
	}
	
	public E dequeue()
	{
		size--;
		return Q[head++];
	}
}


 class Prova
{
	public static void main(String[]args) throws FileNotFoundException,EmptyTreeException
	{
		Tree<Integer> mioAlbero=new Tree<Integer>();
		Scanner input=new Scanner(new File("input.txt"));
		PrintWriter output=new PrintWriter("output.txt");
		while(input.hasNextInt())
		{
			BSTNode<Integer> node=new BSTNode<Integer>();
			node.setLabel(input.nextInt());//ciò che leggo dall'input, viene impostato come elemento del nodo dell'albero
			mioAlbero.insert(node);
		}
		
		output.write("numero di nodi: " + mioAlbero.size());
		output.write("\n");
		output.write("altezza dell'albero: " + mioAlbero.getHeight());
		output.write("\n");
		output.write("La radice dell'albero è: " + mioAlbero.getRoot().getLabel());
		output.write("\n");
		output.write("Il valore più piccolo è: " +mioAlbero.minimo().getLabel());
		output.write("\n");
		output.write("Il valore più grande è: " +mioAlbero.massimo().getLabel());
		output.write("\n");
		BSTNode<Integer>[] vettore=mioAlbero.preorder();
		output.write("VISITA PREORDER: " + vettore[0].getLabel());//si parte dal primo
		for(int i=1;i<mioAlbero.size;i++)
		output.write(" " + vettore[i].getLabel());
		output.write("\n");
		BSTNode<Integer> []vettore1=mioAlbero.postorder();
		output.write("VISITA POSTORDER: " + vettore1[0].getLabel());
		for(int i=1;i<mioAlbero.size;i++)
		output.write(" " + vettore1[i].getLabel());
		output.write("\n");
		BSTNode<Integer>[] vettore2=mioAlbero.inorder();
		output.write("VISITA INORDER: " + vettore2[0].getLabel());
		for(int i=1; i< mioAlbero.size; i++)
		output.write(" " + vettore2[i].getLabel());
		output.write("\n");
		output.write("VISITA BFS: " + mioAlbero.BFSVisit() + "\n");
		output.close();
		input.close();
	}
}