PROBLEMA Implementazione albero n-ario in Java

aleshepard

Nuovo Utente
Salve a tutti ragazzi, sono nuova e piuttosto disperata per una consegna che ho a breve :cry:
Devo implementare un albero n-ario in Java con vari metodi, ma sto avendo diversi problemi. Vi riporto i metodi incriminati:

Java:
//Classe del nodo

public class Nodo_m_ario {
    public Nodo_m_ario padre;
    public List<Nodo_m_ario> figli = new ArrayList<Nodo_m_ario>(maxNrFigli);
    public String info;

    public static int maxNrFigli;

    public Nodo_m_ario (String info) {
        this.info=info;
        figli  = new ArrayList<Nodo_m_ario>(maxNrFigli);
    }
   
    public Nodo_m_ario() {
    }

    public void aggiungiFiglio(int posizione, Nodo_m_ario figlio) {
        if(this.figli.size()>=maxNrFigli) {
            System.out.println("Impossibile aggiungere nodo");
            } else {
                figlio.padre=this;
                this.figli.add(figlio);
            }
    }

//Classe dell'albero:

public class Albero_m_ario extends Nodo_m_ario {
    public Nodo_m_ario radice;

    public Albero_m_ario(int arietà) {
        super();
        Nodo_m_ario.maxNrFigli = arietà;      
    }
   
    //Inserire la radice di cui è nota l'informazione che essa conterrà.
    public void impostaRadice(String info) {
        radice = new Nodo_m_ario(info);
        radice.padre = null;
        radice.figli = new ArrayList<Nodo_m_ario>(Nodo_m_ario.maxNrFigli);
    }

    //Inserire un nuovo nodo V come figlio i-esimo di un nodo U, già presente nell'albero.
    public void aggiungiNodoV(Nodo_m_ario u, String info, int i) {
        Nodo_m_ario child = new Nodo_m_ario(info);
        u.aggiungiFiglio(i, child);
    }
   
    //Inserire una nuova radice in un albero non vuoto in modo che la vecchia radice sia figlia i-esima della nuova.
    public void cambiaRadice(Nodo_m_ario nuovaRadice, int i) {
        Nodo_m_ario vecchiaRadice = this.radice;
        nuovaRadice.figli = null;
        nuovaRadice.figli.set(i, vecchiaRadice);
        vecchiaRadice.padre = nuovaRadice;
        this.radice = nuovaRadice;
    }
Quando nel metodo main provo ad inserire la radice e i nodi nell'albero viene sollevata un'eccezione di puntatore nullo, controllando il debugger ho scoperto che quando inserisco un nuovo nodo quello vecchio non viene salvato come padre.
Sto impazzendo, non capisco dove sia l'errore, se ci fosse qualcuno disposto ad aiutarmi sarei molto felice! Grazie in anticipo :love:
 
Ultima modifica:

Skills07

Moderatore
Staff Forum
9,656
2,633
Hardware Utente
CPU
Ryzen 7 2700x
Dissipatore
Stock
Scheda Madre
Aourus Gigabyte X-470
Hard Disk
Samsung Evo 850 250gb,2tb toshiba, 500gb western digital, 160gb segate
RAM
16 gb G.Skill Tridentz 3200 mhz RGB
Scheda Video
Sapphire RX 580 8gb ddr5
Monitor
Samsung Smart TV Full HD 50 Pollici/ Hp ES 24 IPS
Alimentatore
XFX 80 plus 750 watt
Case
Aerecool xpredator x3
Sistema Operativo
Windows 10 Pro 64
per favore metti il codice sotto la tag code grazie
 
  • Mi piace
Reactions: Mursey

DispatchCode

Utente Attivo
572
325
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
Il nome della classe dovresti darlo seguendo le convenzioni del linguaggio: se la classe è composta da più parole, l'iniziale di ciascuna parola va in maiuscolo.
Poi... le variabili accentate?
Anche la gerarchia che hai creato: perchè l'albero estende il nodo?
Anche i membri della classe pubblici andrebbero rivisti.

Nell'aggiunta del figlio, non consideri la posizione, se non ho visto male.

Comunque ci sono probabilmente altre cose da sistemare, ma senza la formattazione del codice con l'apposito tag evito di proseguire (e attendo almeno una tua risposta ;) ).
 

aleshepard

Nuovo Utente
Ho utilizzato la tag code, perdonate la distrazione :ok:

Il nome della classe dovresti darlo seguendo le convenzioni del linguaggio: se la classe è composta da più parole, l'iniziale di ciascuna parola va in maiuscolo.
Poi... le variabili accentate?
Anche la gerarchia che hai creato: perchè l'albero estende il nodo?
Anche i membri della classe pubblici andrebbero rivisti.

Nell'aggiunta del figlio, non consideri la posizione, se non ho visto male.

Comunque ci sono probabilmente altre cose da sistemare, ma senza la formattazione del codice con l'apposito tag evito di proseguire (e attendo almeno una tua risposta ;) ).
Riguardo alle convenzioni del linguaggio, lo so e la cosa mi infastidisce, ma il docente ha fornito determinate istruzioni e per evitare casini ho preferito attenermi. Intanto ho corretto i membri della classe pubblici, per quanto riguarda la gerarchia avevo reso l'albero sottoclasse del nodo pensando di avere più variabili e metodi in comune, ma in effetti andando avanti con il progetto ho notato che è una cosa superflua.

Comunque ho provato a modificare il metodo aggiungiFiglio così:
Java:
    public void aggiungiFiglio(int posizione, Nodo_m_ario figlio) {
        if(this.figli.size()>=maxNrFigli) {
            System.out.println("Impossibile aggiungere nodo");
            } else {
                figlio.padre = this;
                this.figli.add(posizione, figlio);
            }
    }
ma il problema persiste e non capisco il perché. Probabilmente il motivo è più banale di quanto io pensi e in tal caso mi scuso, sto ancora imparando a programmare :cry:
 

DispatchCode

Utente Attivo
572
325
Hardware Utente
CPU
Intel i7 6700HQ, 2.60Ghz, 4 core 8 threads
Scheda Madre
Asustek
Hard Disk
Hitachi 7200 rpm, 1TB
RAM
16GB DDR4 (2 slot su 4)
Scheda Video
Nvidia Geforce GTX 960M, 4GB
Scheda Audio
Realtek
Sistema Operativo
Windows 10 64bit
Secondo me ti sei incasinata un pò la vita; sarebbe utile vedere il codice aggiornato con le ultime tue modifiche.
Puoi pubblicare il codice per intero? Così non è chiaro cosa fai esattamente per creare l'albero.

Non sarebbe complessa la realizzazione in sé: hai un Nodo radice che ha un valore e nel tuo caso un ArrayList di Nodi figli, più un riferimento al Nodo padre.
In teoria potresti anche astrarre la creazione del nodo: passi l'informazione, e la creazione del Nodo è interna all'albero.

La firma dei metodi ti è stata data, oppure hai scelto tu i parametri?
 

aleshepard

Nuovo Utente
Certo, ti carico tutto ciò che ho fatto fino ad ora, premetto che ci sono diversi problemini che sto correggendo. Mi sono state date indicazioni su come implementare i metodi, alcuni parametri li ho scelti io.

Java:
package albero_m_ario;

import java.util.ArrayList;
import java.util.List;

public class Nodo_m_ario {
    protected Nodo_m_ario padre;
    protected List<Nodo_m_ario> figli = new ArrayList<Nodo_m_ario>(maxNrFigli);
    protected String info;

    protected static int maxNrFigli;

    public Nodo_m_ario (String info) {
        this.info=info;
        figli  = new ArrayList<Nodo_m_ario>(maxNrFigli);
    }
    
    public Nodo_m_ario() {
    }
    
    public void aggiungiFiglio(int posizione, Nodo_m_ario figlio) {
        if(this.figli.size()>=maxNrFigli) {
            System.out.println("Impossibile aggiungere nodo");
            } else {
                figlio.setPadre(this);
                this.figli.add(posizione, figlio);   
            }
    }
    
    public Nodo_m_ario getPadre() {
        return padre;
    }

    public void setPadre(Nodo_m_ario padre) {
        this.padre = padre;
    }

    public List<Nodo_m_ario> getFigli() {
        return figli;
    }

    public void setFigli(List<Nodo_m_ario> figli) {
        this.figli = figli;
    }

    public String getInfo() {
        return info;
    }

    public void setInfo(String info) {
        this.info = info;
    }

    public static int getMaxNrFigli() {
        return maxNrFigli;
    }

    public static void setMaxNrFigli(int maxNrFigli) {
        Nodo_m_ario.maxNrFigli = maxNrFigli;
    }
    
    public int numeroFigli() {
        return figli.size();
    }
    
    public boolean isFoglia() {
        return numeroFigli()==0;
    }
    
    public int livello(){
        int livello=0;
        Nodo_m_ario temp=this.getPadre();
        while(temp!=null){
            livello++;
            temp=temp.getPadre();
        }
        return livello;
    
    }
Java:
package albero_m_ario;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;

public class Albero_m_ario extends Nodo_m_ario {
    private Nodo_m_ario radice;
    private int altezza;

    public Albero_m_ario(int arietà) {
        super();
        Nodo_m_ario.maxNrFigli = arietà;       
    }
    
    //Inserire la radice di cui è nota l'informazione che essa conterrà.
    public Nodo_m_ario impostaRadice(String info) {
        if (radice!=null){
            return null;
        }
        radice = new Nodo_m_ario(info);
        radice.padre = null;
        return radice;
    }

    //Inserire un nuovo nodo V come figlio i-esimo di un nodo U, già presente nell'albero.
    public void aggiungiNodoV(Nodo_m_ario u, String info, int i) {
        Nodo_m_ario child = new Nodo_m_ario(info);
        u.aggiungiFiglio(i, child);

        if(child.livello()>altezza){
            altezza=child.livello();
        }
    }
    
    //Inserire una nuova radice in un albero non vuoto in modo che la vecchia radice sia figlia i-esima della nuova.
    public void cambiaRadice(Nodo_m_ario nuovaRadice, int i) {
        Nodo_m_ario vecchiaRadice = this.radice;
        nuovaRadice.figli.set(i, vecchiaRadice);
        vecchiaRadice.padre = nuovaRadice;
        this.radice = nuovaRadice;
    }

    //Restituire il numero di nodi interni presenti nell'albero.
    public int numeroNodiInterni(Nodo_m_ario node) {
        int count=0;
        count++;
        if(node.figli.size()!= 0 && (!(node.isFoglia()))) {
            for(Nodo_m_ario u : node.figli)
                count = count+numeroNodiInterni(u);
        }
        return count;
    }
    
    public int numeroNodiInterni() {
        return numeroNodiInterni(this.radice);
    }
    
    //Visita per livelli
    public void visitaDFS() {
        Stack<Nodo_m_ario> stack = new Stack<Nodo_m_ario>();
        stack.push(radice);
        while (!stack.isEmpty()) {
            Nodo_m_ario element = stack.pop();
            System.out.println(element.info);
            List<Nodo_m_ario> nodi = element.getFigli();
            for(int i = 0; i < nodi.size(); i++) {
                Nodo_m_ario n = nodi.get(i);
                if (n!=null) {
                    stack.push(n);
                }
            }
        }
    }
    
    //Visita anticipata
    public void visitaBFS() {
        LinkedList<Nodo_m_ario> queue = new LinkedList<Nodo_m_ario>();
        queue.add(radice);
        while (!queue.isEmpty()) {
            Nodo_m_ario element = queue.remove();
            System.out.println(element.info);
            List<Nodo_m_ario> nodi = element.getFigli();
            for (int i = 0; i < nodi.size(); i++) {
                Nodo_m_ario n = nodi.get(i);
                if(n!=null) {
                    queue.add(n);
                }
            }
        }
    }

    //Restituire il contenuto di un nodo interno.
    public String getContenutoNodoInterno(Nodo_m_ario node) {
        if (node.isFoglia()) {
            System.out.println("Non è un nodo interno");
        }
        return node.getInfo();
    }
    
    //Cambiare il contenuto di un nodo interno.
    public void cambiaContenutoNodoInterno(Nodo_m_ario node, String newInfo) {
        if (!(node.isFoglia())){
            node.setInfo(newInfo);
        }
    }
    
    //Restituire la radice dell'albero.
    public Nodo_m_ario getRadice() {
        return radice;
    }   
    
    //Dato un nodo interno, restituire il numero dei suoi figli che siano nodi interni.
    public void numeroFigli(Nodo_m_ario node) {
        List<Nodo_m_ario> nodi = node.getFigli();
        System.out.println(nodi.size());
    }
    
    //Dato un nodo interno, restituire la lista delle informazioni dei suoi figli che siano nodi interni.
    public void contenutoFigli(Nodo_m_ario node) {
        List<Nodo_m_ario> nodi = node.getFigli();
        for (int i = 0; i < nodi.size(); i++) {
            System.out.println(i);
        }
    }
    
    //Restituire il padre di un nodo interno.
    public Nodo_m_ario getPadre(Nodo_m_ario node) {
        return node.getPadre();
    }

    //Restituire il numero delle foglie dell'albero.
    public int getFoglie() {
        List<Nodo_m_ario> foglie = new ArrayList<>();
        for (Nodo_m_ario u : figli) {
            if (u.isFoglia()) {
                foglie.add(u);
            }
        }
        return foglie.size();
    }
    
    //Restituire il livello di un nodo.
     public int livello(Nodo_m_ario v){
         return v.livello();
     }
    
     //Restituire l'altezza dell'albero.
    public int altezza(){
        return altezza;
    }
 

Entra

oppure Accedi utilizzando