[JAVA] Metodo che restituisce la radice di un albero

[dennis87]

Ciao a tutti. Devo realizzare un progetto in Java, che richiede questo:"Negli alberi puo' capitare di non sapere a priori il numero dei figli di ciascun nodo. E' possibile quindi associare ad ogni nodo una lista di puntatori ai suoi figli. La lista a sua volta puo' essere rappresentata con una struttura indicizzata o con una struttura collegata.

Dopo aver realizzato opportunamente una classe NodoLF, utilizzarla per la realizzazione di una classe ALberoLF che implementi i metodi per le seguenti operazioni caratteristiche degli alberi:" e uno di questi metodi è "restituire la radice dell'albero"
Allora, io ho realizzato la classe NodoLF in questa maniera:

public class NodoLF<T> {
	private int indice;
	private T info;
	
	// Realizzazione del costruttore
	public NodoLF(T x){
		info = x;
	}
	
	public int getIndice(){
		return indice;
	}
	
	public T getInfo(){
		return info;
	}
	
	public void setIndice(int n){
		indice = n;
	}
	
	public void setInfo(T x){
		info = x;
	}
}

e il metodo l'ho realizzato cosi:

public class AlberoLF<T> {
	private NodoLF<T>[] padri = new NodoLF[0];
	private NodoLF<T>[] nodi = new NodoLF[0];
	
	public NodoLF<T>[] getPadri(){
		return padri;
	}
	
	public NodoLF<T>[] getNodi(){
		return nodi;
	}
// Punto 5; Restituisce la radice dell'albero.
	public NodoLF<T> radice(){
		NodoLF<T> radice = null;
		int i=0;
		while(padri[i]!=null)
			i++;
		radice=nodi[i];
		return radice;
	}

Ho trovato anche questo per la restituzione dei figli di un nodo

// Punto 7; Restituisce la lista dei figli di un nodo.
	public LinkedList<T> figli(NodoLF<T> v){
		LinkedList<T> figli = new LinkedList<T>();
		// Controllo per generare la lista dei figli
		if(v==null)
			return figli;
		for (int i=0;i<numNodi();i++)
			if(padri[i]==v)
				figli.add(nodi[i].getInfo());
		return figli;
	}

ma non sono sicuro di come è implementata, l'ho ripresa da una gia fatta, in quanto qui si usa un vettore, mentre a me occorre una lista. Ma non capisco come poter implementarlo con una lista.
Grazie a tutti

[dennis87]

nessuno sa aiutarmi?

[Who am I]

Secondo me sei fuori strada, la lista dei figli è un informazione che deve possedere ogni nodo, non puoi metterla nella classe AlberoLF, altrimenti se fai così come si fa a sapere , data la lista dei figli, di quale nodo è figlio un dato elemento?
Ti suggerisco di rifare la classe NodoLF utilizzando un ArrayList, ti do uno spunto per riavviarti:

public class NodoLF<T> {
	
	private T info;
        private ArrayList<NodoLF> figli; // arraylist eventualmente vuota per i nodi foglia
        private NodoLF padre; // riferimento NULL per il nodo radice
	
	<metodi setter e getter>
}

E nella classe AlberoLF metti solamente il riferimento al nodo radice, e tramite quello accedi a tutti i suoi figli (reperibili tramite la lista dei figli).
In questo modo ogni volta che devi rimuovere un nodo come figlio di un certo nodo, rimuovi quell' elemento dalla sua lista dei figli, per aggiungerne uno lo aggiungi alla lista dei figli.
Ogni nodo appena creato contiene una lista dei figli che è vuota.
Inoltre ti faccio notare un' altra cosa:

ma non sono sicuro di come è implementata, l'ho ripresa da una gia fatta, in quanto qui si usa un vettore, mentre a me occorre una lista. Ma non capisco come poter implementarlo con una lista.

Piccolo parere personale: ti sconsiglio di partire da del codice già fatto, altrimenti non capirai mai il meccanismo che c'è dietro.Implementando te daccapo il tutto ne capirai bene il funzionamento.

[Kaamos]

Originariamente inviato da Who am I
Secondo me sei fuori strada, la lista dei figli è un informazione che deve possedere ogni nodo, non puoi metterla nella classe AlberoLF, altrimenti se fai così come si fa a sapere , data la lista dei figli, di quale nodo è figlio un dato elemento?
Ti suggerisco di rifare la classe NodoLF utilizzando un ArrayList, ti do uno spunto per riavviarti:

public class NodoLF<T> {
	
	private T info;
        private ArrayList<NodoLF> figli; // arraylist eventualmente vuota per i nodi foglia
        private NodoLF padre; // riferimento NULL per il nodo radice
	
	<metodi setter e getter>
}

E nella classe AlberoLF metti solamente il riferimento al nodo radice, e tramite quello accedi a tutti i suoi figli (reperibili tramite la lista dei figli).
In questo modo ogni volta che devi rimuovere un nodo come figlio di un certo nodo, rimuovi quell' elemento dalla sua lista dei figli, per aggiungerne uno lo aggiungi alla lista dei figli.
Ogni nodo appena creato contiene una lista dei figli che è vuota.
Inoltre ti faccio notare un' altra cosa:



Piccolo parere personale: ti sconsiglio di partire da del codice già fatto, altrimenti non capirai mai il meccanismo che c'è dietro.Implementando te daccapo il tutto ne capirai bene il funzionamento.

Quoto e aggiungo che seguendo questo metodo (corretto) l'utente NON dovrebbe interagire con l'albero attraverso i nodi (come ha fatto nel codice poco sopra) ma attraverso le informazioni in essi contenuti, quindi i metodi dovrebbero prendere e restituire oggetti di tipo T.
Un metodo efficace che ti obbliga a fare questo è usare la classe nodo come classe incapsulata nella classe albero, quindi imporsi uno schema iniziale del genere.

class Tree<T>
{

  private static class Node<T>
  {

    // tutta la classe nodo

  }

  // tutta la classe albero

}

[dennis87]

Questo è il testo del progetto.

Negli alberi puo' capitare di non sapere a priori il numero dei figli di ciascun nodo. E' possibile quindi associare ad ogni nodo una lista di puntatori ai suoi figli. La lista a sua volta puo' essere rappresentata con una struttura indicizzata o con una struttura collegata.

Dopo aver realizzato opportunamente una classe NodoLF, utilizzarla per la realizzazione di una classe ALberoLF che implementi i metodi per le seguenti operazioni caratteristiche degli alberi:

01) restituire il numero di nodi presenti nell'albero;

02) restituire il numero di figli di un nodo;

03) restituire il contenuto di un nodo;

04) cambiare il contenuto di un nodo;

05) restituire la radice dell'albero;

06) restituire il padre di un nodo;

07) restituire la lista dei figli di un nodo;

08) inserire la radice in un albero vuoto e restituirla;

09) inserire una nuova radice in un albero non vuoto in modo che la vecchia radice sia sua figlia;

10) inserire un nodo nuovo v come figlio di un nodo u gia' presente nell'albero e restituirlo;

11) inserire un sottoalbero B in modo che la radice di B sia figlia di un nodo u dell'albero;

12) attraversare l'albero in profondita' e restituire la lista dei nodi cosi' incontrati;

13) attraversare l'albero in ampiezza e restituire la lista dei nodi cosi' incontrati;


Fornire inoltre un metodo main TestAlberiLF per testare i metodi implementati.

E' consigliato realizzare un'interfaccia Albero dove siano specificati i metodi sopra e che sia implementata dalla classe Albero LF.

Posso chiedervi un cosiglio su come realizzare?
Grazie ancora

[Who am I]

Guarda che è più facile di quello che sembra.
Inizia a scrivere il codice come ti ho suggerito,per i punti più facili come "restituire il numero di figli di un nodo" non ci dovrebbero essere problemi (in questo caso basta usare il metodo size su figli), ma per ora tu concentrati sulle cose che puoi fare.
Poi se incontri altre difficoltà posta qui altre domande, ma inizia con lo scrivere del codice, hai già gli strumenti necessari.

[dennis87]

Originariamente inviato da Who am I
Guarda che è più facile di quello che sembra.
Inizia a scrivere il codice come ti ho suggerito,per i punti più facili come "restituire il numero di figli di un nodo" non ci dovrebbero essere problemi (in questo caso basta usare il metodo size su figli), ma per ora tu concentrati sulle cose che puoi fare.
Poi se incontri altre difficoltà posta qui altre domande, ma inizia con lo scrivere del codice, hai già gli strumenti necessari.

Grazie, ma non mi è chiaro come realizzare la classe NodoLF, cioè non ho capito a cosa serve.

[Who am I]

Provo a spiegarmi meglio:

public class NodoLF<T> {
	
	private T info;
        private ArrayList<NodoLF> figli; // arraylist eventualmente vuota per i nodi foglia
        private NodoLF padre; // riferimento NULL per il nodo radice
	
	<metodi setter e getter>
}

Se vuoi disegnare un grafo su carta e penna, nel disegno ci saranno tanti nodi, ogni nodo conterrà:

1)Una informazione che può ad esempio essere un numero;
2)Zero o più frecce uscenti che sono dirette verso altri nodi, cioè verso i figli;
3)Una frecce entrante che parte dal nodo padre, eccetto per la radice che non ha padre.

Ebbene la classe NodoLF serve a racchiudere tutte queste informazioni:

1)info è l' informazione contenuta nel nodo;
2)figli è la lista dei figli, cioè l' insieme delle frecce uscenti;
3)padre è il riferimento al padre del nodo.

Quindi per aggiungere un figlio a un nodo semplicemente aggiungi un elemento all' ArrayList figli, per leggere la lista dei figli la scorri, ecc..

Chiaro?

[dennis87]

si, adesso si. Grazie mille. Provo a scrivere del codice domani mattina e semmai posto qui. Grazie ancora.

[dennis87]

Buongiorno a tutti. Ho provato a implementare la classe NodoLF, vi posto il codice

import java.util.ArrayList;


public class NodoLF<T> {
	private T info;							// Contiene l'informazione del nodo.
	private ArrayList<NodoLF> figli;		// Array contenente i figli, può essere vuota per i nodi foglia.
	private NodoLF padre;					// Radice dell'albero. Riferimento NULL.
	
	public NodoLF(T x){
		info=x;
	}
	
	public T getInfo(){
		return info;
	}
	
	public void setInfo(T x){
		info=x;
	}
	
	public void setPadre(){
		padre=null;
	}
}

può andare bene?
Mentre nella classe AlberoLF ho fatto questo per ora

public class AlberoLF<T> {
	
	private NodoLF<T>[] nodi=new NodoLF[0];
	private NodoLF<T>[] padri=new NodoLF[0];

	// Metodo che restituisce la lista dei figli di un nodo n. Sarebbe il punto 7.
	public ArrayList<NodoLF<T>> figli(NodoLF<T> n){
		ArrayList<NodoLF<T>> figli = new ArrayList<NodoLF<T>>();
		if(n==null){
			return figli;
		}
		for(int i=0;i<numNodi();i++){
			if(padri[i]==n){
				figli.add(nodi[i]);
			}
		}
		return figli;
	}
	
	// Punto 1; Restituisce il numero dei nodi presenti nell'albero.
	public int numNodi(){
		return nodi.length;
	}
	
	// Punto 2; Restituisce il numero dei figli di un nodo. Al metodo gli passo un nodo n.
	public int numFigli(NodoLF<T> n){
		 return figli(n).size();
	}
	
	// Punto 3; Restituisce il contenuto di un nodo. Gli passo un nodo n e mi restituisce il suo contenuto attraverso la funzione getInfo.
	public T infoNodo(NodoLF<T> n){
		return n.getInfo();
	}
	
	// Punto 4; Cambia il contenuto di un nodo. Gli passo al metodo il nodo n a cui devo cambiare il contenuto (l'informazione) e l'informazione che devo assegnare al nodo n.
	public void changeInfo(NodoLF<T> n, T info){
		n.setInfo(info);
	}
}