Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

[Java] Metodo per un albero binario

27/06/2019, 18:56

Buonasera, sto svolgendo un esercizio proposto dal mio professore in un tema d'esame passato, ma sto riscontrando non pochi problemi nella scrittura di un metodo.
Il testo è il seguente: "Implementa un albero binario di ricerca non generico per memorizzare un insieme di Stringhe ordinate alfabeticamente. L'albero deve avere i seguenti metodi:
_ insert -> per l'inserimento di una Stringa;
_ printCrescente -> per la stampa del contenuto dell'albero in ordine alfabetico crescente (dalla A alla Z);
_ printDecrescente -> per la stampa del contenuto dell'albero in ordine alfabetico decrescente (dalla Z alla A);
_ getPiuLunga -> resituisce la stringa più lunga presente."

I primi tre metodi li ho implementati senza difficoltà, ma il metodo getPiuLunga mi sta facendo uscire di testa.

Riporto il mio operato:
Codice:
public class Esercizio
{
   public static void main(String[] args)
   {
      AlberoStringhe str_tree = new AlberoStringhe();

      str_tree.insert("Berlino");
      str_tree.insert("Parigi");
      str_tree.insert("Copenaghen");
      str_tree.insert("Lisbona");
      str_tree.insert("Zurigo");
      str_tree.insert("Amsterdam");
      str_tree.insert("Londra");
      str_tree.insert("Dublino");

      System.out.print("Ordine crescente -> ");
      str_tree.print(true); // uso true per la stampa in ordine crescente

      System.out.print("\n\nOrdine decrescente -> ");
      str_tree.print(false); // uso false per la stampa in ordine decrescente

      System.out.print("\n\nLa più lunga è: " + str_tree.getPiuLunga());
   }
}

class AlberoStringhe
{
   class Nodo
   {
      String dato;
      AlberoStringhe left;
      AlberoStringhe right;

      Nodo(String s)
      {
         this.dato = s;
      }
   }

   private Nodo radice;

   public void insert(String str)
   {
      if(radice == null)
      {
         radice = new Nodo(str);
         radice.left = new AlberoStringhe();
         radice.right = new AlberoStringhe();
      }
      else
      {
         if(radice.dato.compareTo(str) < 0)
            radice.right.insert(str);
         else
            radice.left.insert(str);
      }
   }

   public void print(boolean val)
   {
      if(val)
         printCrescente();
      else
         printDecrescente();
   }

   private void printCrescente()
   {
      if(radice != null)
      {
         radice.left.printCrescente();
         System.out.print(radice.dato + " ");
         radice.right.printCrescente();
      }
   }

   private void printDecrescente()
   {
      if(radice != null)
      {
         radice.right.printDecrescente();
         System.out.print(radice.dato + " ");
         radice.left.printDecrescente();
      }
   }   

   public String getPiuLunga()
   {
      return getPiuLunga(radice);
   }

   private String getPiuLunga(Nodo nodo)
   {
      String s = "";
      // ??????????
      return s;
   }
}


La mia idea è quella di chiamare il metodo getPiuLunga() dal main, il quale chiama un altro metodo getPiuLunga passandogli in input la radice dell'albero (overloading) così da poter realizzare la ricorsione con i sottoalberi sx e dx. Il problema è che qualunque tipo di implementazione io provi, non funziona. :?

Qualcuno riuscirebbe gentilmente ad aiutarmi in questa implementazione riportandomi del codice? :smt023

Re: [Java] Metodo per un albero binario

27/06/2019, 20:11

Fabbiooo ha scritto:Buonasera, sto svolgendo un esercizio proposto dal mio professore in un tema d'esame passato, ma sto riscontrando non pochi problemi nella scrittura di un metodo.
Il testo è il seguente: "Implementa un albero binario di ricerca non generico per memorizzare un insieme di Stringhe ordinate alfabeticamente. L'albero deve avere i seguenti metodi:
_ insert -> per l'inserimento di una Stringa;
_ printCrescente -> per la stampa del contenuto dell'albero in ordine alfabetico crescente (dalla A alla Z);
_ printDecrescente -> per la stampa del contenuto dell'albero in ordine alfabetico decrescente (dalla Z alla A);
_ getPiuLunga -> resituisce la stringa più lunga presente."

I primi tre metodi li ho implementati senza difficoltà, ma il metodo getPiuLunga mi sta facendo uscire di testa.

Riporto il mio operato:
Codice:
public class Esercizio
{
   public static void main(String[] args)
   {
      AlberoStringhe str_tree = new AlberoStringhe();

      str_tree.insert("Berlino");
      str_tree.insert("Parigi");
      str_tree.insert("Copenaghen");
      str_tree.insert("Lisbona");
      str_tree.insert("Zurigo");
      str_tree.insert("Amsterdam");
      str_tree.insert("Londra");
      str_tree.insert("Dublino");

      System.out.print("Ordine crescente -> ");
      str_tree.print(true); // uso true per la stampa in ordine crescente

      System.out.print("\n\nOrdine decrescente -> ");
      str_tree.print(false); // uso false per la stampa in ordine decrescente

      System.out.print("\n\nLa più lunga è: " + str_tree.getPiuLunga());
   }
}

class AlberoStringhe
{
   class Nodo
   {
      String dato;
      AlberoStringhe left;
      AlberoStringhe right;

      Nodo(String s)
      {
         this.dato = s;
      }
   }

   private Nodo radice;

   public void insert(String str)
   {
      if(radice == null)
      {
         radice = new Nodo(str);
         radice.left = new AlberoStringhe();
         radice.right = new AlberoStringhe();
      }
      else
      {
         if(radice.dato.compareTo(str) < 0)
            radice.right.insert(str);
         else
            radice.left.insert(str);
      }
   }

   public void print(boolean val)
   {
      if(val)
         printCrescente();
      else
         printDecrescente();
   }

   private void printCrescente()
   {
      if(radice != null)
      {
         radice.left.printCrescente();
         System.out.print(radice.dato + " ");
         radice.right.printCrescente();
      }
   }

   private void printDecrescente()
   {
      if(radice != null)
      {
         radice.right.printDecrescente();
         System.out.print(radice.dato + " ");
         radice.left.printDecrescente();
      }
   }   

   public String getPiuLunga()
   {
      return getPiuLunga(radice);
   }

   private String getPiuLunga(Nodo nodo)
   {
      String s = "";
      // ??????????
      return s;
   }
}


La mia idea è quella di chiamare il metodo getPiuLunga() dal main, il quale chiama un altro metodo getPiuLunga passandogli in input la radice dell'albero (overloading) così da poter realizzare la ricorsione con i sottoalberi sx e dx. Il problema è che qualunque tipo di implementazione io provi, non funziona. :?

Qualcuno riuscirebbe gentilmente ad aiutarmi in questa implementazione riportandomi del codice? :smt023


ciao
qualcosa del genere dovrebbe andare, devi passare la stringa vuota la prima volta che chiami il metodo,
Codice:
private String getPiuLunga(String str)
{
        if(radice == null) return null;
        if(radice.dato.lenght() > str.lenght) {
             str= radice.dato;
        }
   radice.right.getPiuLunga(str)
   radice.left.getPiuLunga(str)

   return str;
   }

Re: [Java] Metodo per un albero binario

27/06/2019, 21:09

Ho provato ad implementare il tuo metodo, tuttavia non funziona :(

Codice:
   public String getPiuLunga()
   {
      return getPiuLunga(radice.dato);
   }

   private String getPiuLunga(String str)
   {
      if(radice == null)
         return "";
      if(radice.dato.length() > str.length())
         str = radice.dato;
      radice.right.getPiuLunga(str);
      radice.left.getPiuLunga(str);
      return str;
   }


Mi dà sempre come output Berlino, quando invece dovrebbe essere Copenaghen :?

Re: [Java] Metodo per un albero binario

27/06/2019, 22:27

Fabbiooo ha scritto:Ho provato ad implementare il tuo metodo, tuttavia non funziona :(

Codice:
   public String getPiuLunga()
   {
      return getPiuLunga(radice.dato);
   }

   private String getPiuLunga(String str)
   {
      if(radice == null)
         return "";
      if(radice.dato.length() > str.length())
         str = radice.dato;
      radice.right.getPiuLunga(str);
      radice.left.getPiuLunga(str);
      return str;
   }


Mi dà sempre come output Berlino, quando invece dovrebbe essere Copenaghen :?


hai ragione,
colpa mia, non ho considerato che le stringhe in java sono oggetti immutabili

prova così

Codice:
public String getPiuLunga(StringBuffer str)
{
        if(radice == null) return null;
        if(radice.dato.length() > str.length()) {
             str.setLength(0);
             str.append(radice.dato);
        }
   radice.right.getPiuLunga(str);
   radice.left.getPiuLunga(str);

   return str.toString();
   }
}



e nel main:

Codice:
      System.out.print("\n\nLa più lunga è: " + str_tree.getPiuLunga(new StringBuffer("")));


ciao

Re: [Java] Metodo per un albero binario

27/06/2019, 22:34

p.s. ho appena letto che in programmi con un solo thread è preferibile utilizzare StringBuilder piuttosto che StringBuffer

Re: [Java] Metodo per un albero binario

28/06/2019, 08:41

Devo dire che questa soluzione con StringBuffer è veramente interessante! :-D
Avevo pensato ad una stringa che si modificasse nel corso dell'analisi dell'albero, ma non essendo a conoscenza di StringBuffer ero con le mani legate :D
Ti ringrazio per l'aiuto! :smt023
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.