Kaino906
06-07-2015, 10:39
Salve ragazzi. Allora il mio problema è il seguente. Ho questo esercizio:
Su un file di tipo testo (il cui nome va acquisito preliminarmente da tastiera) è memorizzato il contenuto linearizzato anticipato di un albero binario di nomi (stringhe di caratteri) con la convenzione che l’informazione di un nodo radice è seguita ricorsivamente da quella del figlio sinistro e quindi da quella del figlio destro. Simboli successivi sono separati dal carattere #. Un albero vuoto è specificato mediante la stringa NULL. Ad esempio la successione
NELLA#NULL#CASA#DEL#NULL#FABBRO#NULL#NULL#NULL
specifica l’albero:
NELLA
(freccia sinistra da Nella a Null ecc) (freccia destra da Nella a Casa ecc)
NULL CASA
DEL NULL
NULL FABBRO
Scrivere una classe AlberoBinario (nel package poo.albero) che ammetta un metodo build(String) che riceve una stringa col contenuto linearizzato anticipato dell’albero, verifica la correttezza della stringa e costruisce il corrispondente albero binario. Se la stringa non è corretta (condizione necessaria) allora il metodo solleva un’eccezione. La classe deve esportare altresì (almeno) i seguenti metodi: 1) String preOrder() che visita in ordine anticipato l’albero e crea e restituisce una stringa col contenuto dell’albero, secondo le stesse convenzioni della stringa ricevuta dal metodo build, 2) il metodo int altezza() che ritorna l’altezza dell’albero; 3) boolean bilanciato() che ritorna l’informazione logica se l’albero è o meno bilanciato, 4) AlberoBinario copia() che restituisce un nuovo albero, copia integrale dell’albero this.
Fornire un main di prova che legga da input il nome di un file testo, quindi costruisca il corrispondente albero binario ed invochi su di esso i metodi disponibili. Per le operazioni di visualizzazione, fare riferimento al metodo preOrder.
Io ho scritto il seguente codice:
package poo.albero;
import java.io.File;
import java.util.*;
public class AlberoBinario {
private static class Nodo<E> {
E info;
Nodo<E> figlioS, figlioD;
}
private Nodo<String> radice = null;
public int size(){
return size(radice);
}//size
private int size(Nodo<String> radice){
if(radice==null) return 0;
return 1+size(radice.figlioS)+size(radice.figlioD);
}//size
public void build(String s) {
StringTokenizer st = new StringTokenizer(s,"#");
String parola;
while(st.hasMoreTokens()) {
parola = st.nextToken();
this.add(radice, parola);
}
}//build
private void add(Nodo<String> n,String parola) {
if(n == null) {
n.info = parola;
} else {
if(n.figlioS == null) {
this.add(n.figlioS, parola);
} else if(n.figlioD == null) {
this.add(n.figlioD, parola);
} else if(n.figlioS != null && n.figlioD!= null) {
this.add(n.figlioS, parola);
}
}
}//add
public String preOrder() {
String risultato = preOrder(radice);
return risultato;
}
private String preOrder(Nodo<String> radice){
String risultato = "";
if(radice!= null){
risultato = radice.info+"#";
preOrder(radice.figlioS);
preOrder(radice.figlioD);
}
return risultato;
}//preOrder
public boolean bilanciato(){
return bilanciato(radice);
}//bilanciato
private boolean bilanciato(Nodo<String> albero){
if(radice==null || radice.figlioS==null && radice.figlioD==null) return true;
if(Math.abs(size(radice.figlioS)-size(radice.figlioD))>1) return false;
return bilanciato(radice.figlioS) && bilanciato(radice.figlioD);
}//bilanciato
public int altezza() {
if (radice == null) return 0;
return altezza(radice);
} // altezza
private int altezza(Nodo<String> radice) {
if (radice.figlioS == null && radice.figlioD == null) return 0;
int h1 = 0, h2 = 0;
if (radice.figlioS != null) h1 = 1 + altezza(radice.figlioS);
if (radice.figlioD != null) h2 = 1 + altezza(radice.figlioD);
return h1 > h2 ? h1 : h2;
} // altezza
public boolean equals(Object x){
if(!(x instanceof AlberoBinario)) return false;
if(x==this) return true;
AlberoBinario a = (AlberoBinario) x;
return equals(this.radice, a.radice);
}//equals
private boolean equals(Nodo<String> a1, Nodo<String> a2){
if(a1==null && a2==null) return true;
if(a1==null || a2==null) return false;
if(!a1.info.equals(a2.info)) return false;
return equals(a1.figlioS, a2.figlioS) && equals(a1.figlioD, a2.figlioD);
}//equals
public String toString(){
StringBuilder sb = new StringBuilder(200);
sb.append('[');
toString(radice, sb);
if(sb.length()>0) {sb.setLength(sb.length()-2);} //rimuove ultimo separatore ","
sb.append(']');
return sb.toString();
}//toString
private void toString(Nodo<String> radice, StringBuilder sb){
if(radice!=null){
toString(radice.figlioS, sb);
sb.append(radice.info); sb.append(", ");
toString(radice.figlioD, sb);
}
}//toString
public int hashCode(){
return hashCode(radice);
}//hashCode
private int hashCode(Nodo<String> albero){
int primo=43;
if(albero==null) return 0;
return albero.info.hashCode()*primo+hashCode(albero.figlioS)+hashCode(albero.figlioD);
}//hashCode
public static void main(String[]args) {
Scanner sc=new Scanner( System.in );
File f=null;
do{
System.out.print("Nome file: ");
String nomeFile=sc.nextLine();
f=new File( nomeFile );
if( !f.exists() ) System.out.println(nomeFile+" file inesistente!");
}while( !f.exists() );
AlberoBinario a = new AlberoBinario();
}//main
Potrebbe andare bene fin qui l'esercizio? Se si, ho difficoltà a concludere il main.
Su un file di tipo testo (il cui nome va acquisito preliminarmente da tastiera) è memorizzato il contenuto linearizzato anticipato di un albero binario di nomi (stringhe di caratteri) con la convenzione che l’informazione di un nodo radice è seguita ricorsivamente da quella del figlio sinistro e quindi da quella del figlio destro. Simboli successivi sono separati dal carattere #. Un albero vuoto è specificato mediante la stringa NULL. Ad esempio la successione
NELLA#NULL#CASA#DEL#NULL#FABBRO#NULL#NULL#NULL
specifica l’albero:
NELLA
(freccia sinistra da Nella a Null ecc) (freccia destra da Nella a Casa ecc)
NULL CASA
DEL NULL
NULL FABBRO
Scrivere una classe AlberoBinario (nel package poo.albero) che ammetta un metodo build(String) che riceve una stringa col contenuto linearizzato anticipato dell’albero, verifica la correttezza della stringa e costruisce il corrispondente albero binario. Se la stringa non è corretta (condizione necessaria) allora il metodo solleva un’eccezione. La classe deve esportare altresì (almeno) i seguenti metodi: 1) String preOrder() che visita in ordine anticipato l’albero e crea e restituisce una stringa col contenuto dell’albero, secondo le stesse convenzioni della stringa ricevuta dal metodo build, 2) il metodo int altezza() che ritorna l’altezza dell’albero; 3) boolean bilanciato() che ritorna l’informazione logica se l’albero è o meno bilanciato, 4) AlberoBinario copia() che restituisce un nuovo albero, copia integrale dell’albero this.
Fornire un main di prova che legga da input il nome di un file testo, quindi costruisca il corrispondente albero binario ed invochi su di esso i metodi disponibili. Per le operazioni di visualizzazione, fare riferimento al metodo preOrder.
Io ho scritto il seguente codice:
package poo.albero;
import java.io.File;
import java.util.*;
public class AlberoBinario {
private static class Nodo<E> {
E info;
Nodo<E> figlioS, figlioD;
}
private Nodo<String> radice = null;
public int size(){
return size(radice);
}//size
private int size(Nodo<String> radice){
if(radice==null) return 0;
return 1+size(radice.figlioS)+size(radice.figlioD);
}//size
public void build(String s) {
StringTokenizer st = new StringTokenizer(s,"#");
String parola;
while(st.hasMoreTokens()) {
parola = st.nextToken();
this.add(radice, parola);
}
}//build
private void add(Nodo<String> n,String parola) {
if(n == null) {
n.info = parola;
} else {
if(n.figlioS == null) {
this.add(n.figlioS, parola);
} else if(n.figlioD == null) {
this.add(n.figlioD, parola);
} else if(n.figlioS != null && n.figlioD!= null) {
this.add(n.figlioS, parola);
}
}
}//add
public String preOrder() {
String risultato = preOrder(radice);
return risultato;
}
private String preOrder(Nodo<String> radice){
String risultato = "";
if(radice!= null){
risultato = radice.info+"#";
preOrder(radice.figlioS);
preOrder(radice.figlioD);
}
return risultato;
}//preOrder
public boolean bilanciato(){
return bilanciato(radice);
}//bilanciato
private boolean bilanciato(Nodo<String> albero){
if(radice==null || radice.figlioS==null && radice.figlioD==null) return true;
if(Math.abs(size(radice.figlioS)-size(radice.figlioD))>1) return false;
return bilanciato(radice.figlioS) && bilanciato(radice.figlioD);
}//bilanciato
public int altezza() {
if (radice == null) return 0;
return altezza(radice);
} // altezza
private int altezza(Nodo<String> radice) {
if (radice.figlioS == null && radice.figlioD == null) return 0;
int h1 = 0, h2 = 0;
if (radice.figlioS != null) h1 = 1 + altezza(radice.figlioS);
if (radice.figlioD != null) h2 = 1 + altezza(radice.figlioD);
return h1 > h2 ? h1 : h2;
} // altezza
public boolean equals(Object x){
if(!(x instanceof AlberoBinario)) return false;
if(x==this) return true;
AlberoBinario a = (AlberoBinario) x;
return equals(this.radice, a.radice);
}//equals
private boolean equals(Nodo<String> a1, Nodo<String> a2){
if(a1==null && a2==null) return true;
if(a1==null || a2==null) return false;
if(!a1.info.equals(a2.info)) return false;
return equals(a1.figlioS, a2.figlioS) && equals(a1.figlioD, a2.figlioD);
}//equals
public String toString(){
StringBuilder sb = new StringBuilder(200);
sb.append('[');
toString(radice, sb);
if(sb.length()>0) {sb.setLength(sb.length()-2);} //rimuove ultimo separatore ","
sb.append(']');
return sb.toString();
}//toString
private void toString(Nodo<String> radice, StringBuilder sb){
if(radice!=null){
toString(radice.figlioS, sb);
sb.append(radice.info); sb.append(", ");
toString(radice.figlioD, sb);
}
}//toString
public int hashCode(){
return hashCode(radice);
}//hashCode
private int hashCode(Nodo<String> albero){
int primo=43;
if(albero==null) return 0;
return albero.info.hashCode()*primo+hashCode(albero.figlioS)+hashCode(albero.figlioD);
}//hashCode
public static void main(String[]args) {
Scanner sc=new Scanner( System.in );
File f=null;
do{
System.out.print("Nome file: ");
String nomeFile=sc.nextLine();
f=new File( nomeFile );
if( !f.exists() ) System.out.println(nomeFile+" file inesistente!");
}while( !f.exists() );
AlberoBinario a = new AlberoBinario();
}//main
Potrebbe andare bene fin qui l'esercizio? Se si, ho difficoltà a concludere il main.