|
|||||||
|
|
|
 |
|
|
Strumenti |
31-03-2011, 10:06
|
#1 |
|
Junior Member
Iscritto dal: Mar 2011
Messaggi: 4
|
[JAVA] Alberi AutoBilanciati
Salve a tutti, mi presento qui e nel frattempo posto un esercizio in cui ho avuto una difficoltà.
L'esercizio è il seguente: http://www.dmi.unict.it/~faro/prog2/...8/zg8rfct2.pdf Posto la mia soluzione e vi dico quale è il metodo in cui ho difficoltà: Codice:
/**
*
* @author Vincenzo
*/
//import java.lang.RuntimeException;
//import java.util.Queue;
import java.util.LinkedList;
public class Main {
/**
* @param args the command line arguments
*/
public static void main(String[] args) throws Exception {
// TODO code application logic here
AlberoBilanciato a=new AlberoBilanciato();
a.insert("C");
a.insert("D");
a.insert("B");
a.insert("A");
a.preorder();
System.out.println("Altezza albero "+a.height());
System.out.println("Size albero "+a.size());
System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
System.out.println("Size del nodo B "+a.size(a.root.left));
System.out.println("Cancellazione di un elemento");
a.delete("C");
a.preorder();
System.out.println(a.Left(a.root()).info);
System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
a.selfBallance();
System.out.println("L'albero è bilanciato? "+a.isBallanced(a.root));
}
}
interface SelfBallancedTree
{
public int size();
public BTNode root() throws EmptyTreeException;
public BTNode left(BTNode x) throws InvalidArgumentException;
public BTNode right(BTNode x) throws InvalidArgumentException;
public BTNode parent(BTNode x) throws InvalidArgumentException;
public int size(BTNode x) throws InvalidArgumentException;
public void insert(String s);
public BTNode delete(String s);
public boolean isBallanced(BTNode x);
public void selfBallance(); //Mi manca questo solamente
}
class BTNode
{
protected String info; //info nodo
protected BTNode parent,left,right;
public BTNode()
{
info=null;
parent=left=right=null;
}
public BTNode(String in)
{
info=in;
parent=left=right=null;
}
public void visit()
{
System.out.println(" "+info);
}
}
class AlberoBilanciato implements SelfBallancedTree
{
protected BTNode root;
protected int size,height;
public AlberoBilanciato()
{
root=null;
size=0;
height=0;
}
public int size(){return size;}
public int height(){return getAltezzaNodo(root);}
public BTNode root(){return root;}
public boolean isBallanced(BTNode x)
{
int bf=getAltezzaNodo(x.left)-getAltezzaNodo(x.right);
return ((bf>=-1)&& (bf<=1));
}
public BTNode left(BTNode x) throws InvalidArgumentException
{
BTNode tmp=Search(x.info);
BTNode te=tmp.left;
if(te==null)
throw new InvalidArgumentException("Left non presente");
return te;
}
public BTNode Left(BTNode x) throws InvalidArgumentException
{
if(x==null)
throw new InvalidArgumentException("");
return x.left;
}
public BTNode right(BTNode x) throws InvalidArgumentException
{
BTNode tmp=Search(x.info);
BTNode te=tmp.right;
if(te==null)
throw new InvalidArgumentException("Right non presente");
return te;
}
public BTNode parent(BTNode x) throws InvalidArgumentException
{
BTNode tmp=Search(x.info);
BTNode te=tmp.parent;
if(te==null)
throw new InvalidArgumentException("Right non presente");
return te;
}
public BTNode Search(String info)
{
BTNode p=root;
while(p!=null)
{
int res=((Comparable)info).compareTo(p.info);
if(res==0)
return p;
else if(res>0)
p=p.right;
else
p=p.left;
}
return null;
}
public void insert(String s)
{
BTNode d=new BTNode(s);
if(root==null)
root=d;
else
{
BTNode p=root,pred=null;
while(p!=null)
{
if(s.equals(p.info))
return;
pred=p;
if(s.compareTo(p.info)<0)
p=p.left;
else
p=p.right;
}
if(s.compareTo(pred.info)<0)
{
pred.left=d;
d.parent=pred;
}
else
{
pred.right=d;
d.parent=pred;
}
}
size++;
}
public void inorder()
{
inorder(root);
}
public void inorder(BTNode p)
{
if(p!=null)
{
inorder(p.left);
p.visit();
inorder(p.right);
}
}
public void preorder()
{
preorder(root);
}
public void preorder(BTNode p)
{
if(p!=null)
{
p.visit();
preorder(p.left);
preorder(p.right);
}
}
public int getAltezzaNodo(BTNode p)
{
return getAltezzaNodo(p,0);
}
public int getAltezzaNodo(BTNode p,int altezza)
{
if(p!=null)
{
if(p.left==null && p.right==null)
return altezza;
else
{
int a=getAltezzaNodo(p.left,altezza+1);
int b=getAltezzaNodo(p.right,altezza+1);
if(a>b)
return a;
else
return b;
}
}
return altezza-1;
}
public int size(BTNode x) throws InvalidArgumentException
{
if(x==null)
{
return 0;
}
else
{
int nodisx=size(x.left);
int nodidx=size(x.right);
return 1+nodisx+nodidx;
}
}
public BTNode min(BTNode y)
{
BTNode x=Search(y.info);
while(x.left!=null)
x=x.left;
return x;
}
public BTNode successore(BTNode y)
{
BTNode x=Search(y.info);
if(x.right!=null)
return min(x.right);
y=x.parent;
while(x!=null && x==y.right)
{
x=y;
y=y.parent;
}
return y;
}
public BTNode delete(String s)
{
BTNode x=new BTNode(s);
BTNode z=Search(x.info);
BTNode y;
if(z.left==null || z.right==null)
{
y=z;
}
else
y=successore(z);
if(y.left!=null)
x=y.left;
else
x=y.right;
if(x!=null)
x.parent=y.parent;
if(y.parent==null)
root=x;
else
if(y.parent.left==y)
y.parent.left=x;
else
y.parent.right=x;
if(y!=z)
z.info=y.info;
return y;
}
public void selfBallance()
{
if(this.isBallanced(root))
System.out.println("Non è necessario il bilanciamento");
else
//System.out.println("Applicarlo");
{
BTNode p=root;
preordercrea(p);
}
}
public void preordercrea(BTNode p)
{
if(p!=null)
{
Coda c=new Coda();
c.enQueue(p.info);
while(p.left!=null || p.right!=null)
{
c.enQueue(p.left);
c.enQueue(p.right);
}
size++;
}
}
}
class Coda{
protected NodoL head;
protected NodoL tail;
public Coda(){
head=tail=null;
}
public boolean isEmpty(){
return head==null;
}
public void enQueue(Object info){
NodoL x = new NodoL(info);
if(isEmpty())
head=tail=x;
else{
tail.setNext(x);
tail=x;
}
}
public Object deQueue() {
try{
if(isEmpty())
throw new InvalidArgumentException("ERRORE: la coda e' vuota. Impossibile estrarre elementi");
else{
Object ret = head.getInfo();
head=head.getNext();
return ret;
}
}catch(Exception e){ System.out.println(e.getMessage());
return null;}
}
public Object readHead(){
try{
if(isEmpty())
throw new InvalidArgumentException("ERRORE: la coda e' vuota. Impossibile leggere elementi");
else
return head.getInfo();
}catch(Exception e){ System.out.println(e.getMessage());
return null;}
}
public void makeEmpty(){
head=tail=null;
}
public String toString(){
String str="";
if(isEmpty())
str+="La coda e' vuota...";
else{
str+="<- ";
NodoL aux=head;
for(; aux!=null; aux=aux.getNext())
str+=aux.getInfo()+" ";
str+=" <-";
}
return str;
}
}
class NodoL{
private Object info;
private NodoL next;
public NodoL(Object info){
this(info,null);
}
public NodoL(Object info, NodoL next){
this.info=info;
this.next=next;
}
public void setInfo(Object info){
this.info=info;
}
public Object getInfo(){
return info;
}
public void setNext(NodoL next){
this.next=next;
}
public NodoL getNext(){
return next;
}
public String toString(){
return ""+info;
}
}
class InvalidArgumentException extends Exception
{
public InvalidArgumentException() {
}
/**
* Constructs an instance of <code>InvalidArgumentException</code> with the specified detail message.
* @param msg the detail message.
*/
public InvalidArgumentException(String msg) {
super(msg);
}
}
class EmptyTreeException extends Exception
{
public EmptyTreeException(){
}
public EmptyTreeException(String msg){
super(msg);
}
}
Qualcuno mi sa dare una mano? Grazie |
|
|
|
17-04-2011, 09:19
|
#2 | |
|
Junior Member
Iscritto dal: Mar 2011
Messaggi: 4
|
Quote:
|
|
|
|
|
|
|
| Strumenti | |
|
|
Tutti gli orari sono GMT +1. Ora sono le: 00:50.
