Ciao ragazzi stavo svolgendo questo esercizio; ecco qui il testo:
http://www.dmi.unict.it/~faro/prog2/...8/zg8rfct2.pdf
Non so implementare solamente il metodo selfBallace(); in pratica a ricevimento il professore mi ha consigliato di non implementare right rotate e left rotate, bensì utilizzare una coda e poi richiamare una preorder per creare l'albero riempendo i nodi da sx a dx, così da averlo bilanciato.
Ecco il codice che ho fatto finora:
codice:/* * To change this template, choose Tools | Templates * and open the template in the editor. */ /** * */ //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); } }
Rispondi quotando
