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
codice: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(); } }
Rispondi quotando