Authors	Title
Silvio Santoriello [email protected] Edoardo Stefanacci [email protected]	Implementazione di un albero n-ario in Java - Algoritmi e Strutture Dati 24/25

Progetto Algoritmi e Strutture Dati 2024/2025

Il seguente progetto consiste nell'implementazione in linguaggio Java di una struttura dati di tipo Albero N-Ario tramite due strutture indicizzate (Array) contenenti i Nodi dell'albero ed i riferimenti ai rispettivi padri. L'intero codice si basa su due classi principali, AlberoVP e NodoVP, le quali ospitano i metodi dedicati ad eseguire operazioni sull'intero albero o su di uno specifico nodo.

Overview dei metodi relativi alla classe AlberoVP

La classe AlberoVP<T> implementa una struttura ad albero generico in cui ogni nodo può avere un numero arbitrario di figli. È costruita per essere flessibile e facilmente navigabile, mantenendo una lista dei nodi (nodesList) e dei relativi padri (parentList) per consentire operazioni rapide e coerenti sulla struttura.

Costruttori

• AlberoVP()
  Crea un albero vuoto.
• AlberoVP(NodoVP<T> root)
  inizializza l’albero con un nodo radice. Il nodo radice non ha padre e viene impostato al livello 0.

Gestione della Radice

• setRootInEmptyTree(NodoVP<T> root)
  Permette di impostare una radice in un albero inizialmente vuoto.
• setRootNotEmpty(NodoVP<T> newRoot)
  Consente di sostituire la radice attuale con un nuovo nodo. Il vecchio nodo radice diventa figlio della nuova radice. L’intero albero viene aggiornato di conseguenza, incluso il livello dei nodi.

Metodi getter e setter

• getRoot()
  Restituisce il nodo radice dell'albero.
• getParent(NodoVP<T> n)
  Restituisce il nodo padre del nodo specificato.
• getChildList(NodoVP<T> n)
  Restituisce la lista dei figli di un nodo.
• getChildListSize(NodoVP<T> n)
  Restituisce il numero di figli del nodo specificato.
• getNodeInfo(NodoVP<T> n)
  Restituisce l'informazione contenuta nel nodo.
• setNodeInfo(NodoVP<T> n, T info)
  Imposta una nuova informazione per il nodo.
• getNodeLevel(NodoVP<T> n)
  Restituisce il livello (profondità) di un nodo, partendo dalla radice a livello 0.
• getNodeLeavesSize(NodoVP<T> n)
  Restituisce il numero di foglie (nodi terminali) discendenti dal nodo specificato.

Aggiunta di nuovi Nodi

• addNodeChild(NodoVP<T> parent, NodoVP<T> child)
  Aggiunge un nuovo figlio al nodo parent. Questo metodo aggiorna automaticamente il padre del nodo figlio, il livello e le liste interne dell'albero.

Informazioni sull'albero

• getNodesListSize()
  Restituisce il numero totale di nodi nell’albero.
• getHeight()
  Calcola e restituisce l’altezza dell’albero, cioè il livello massimo raggiunto da un nodo.

Visite

• visitaBF()
  Esegue una visita in ampiezza (Breadth-First), restituendo i nodi nell’ordine in cui verrebbero esplorati livello per livello.
• visitaDF()
  Esegue una visita in profondità (Depth-First), restituendo i nodi nell’ordine di una visita pre-order. È implementata ricorsivamente.

Stampa

• toString()
  Restituisce una rappresentazione testuale dell’albero a partire dalla radice, mostrando ricorsivamente tutti i figli.
  Esempio: Claudia[Marco[Silvia[], Ugo[]], Luca[], Giulia[Andrea[Carlo[]], Gianna[]]]

Overview dei metodi relativi alla classe NodoVP

La classe NodoVP<T> rappresenta un singolo nodo all’interno di un albero generico. Ogni nodo può contenere un’informazione di tipo generico T, un riferimento al proprio nodo padre, una lista di figli e un numero intero che rappresenta il livello (profondità) del nodo nell’albero.

Costruttore

• NodoVP(T info)
  Crea un nodo contenente l’informazione info. Inizialmente il nodo non ha padre né figli, il livello deve essere impostato separatamente.

Accesso ai dati

• getInfo()
  Restituisce l’informazione contenuta nel nodo.
• getParent()
  Restituisce il nodo padre.
• getChildList()
  Restituisce la lista dei figli del nodo.
• getChildListSize()
  Restituisce il numero di figli del nodo.
• getLevel()
  Restituisce il livello (profondità) del nodo nell’albero, con la radice al livello 0.
• getLeavesSize()
  Restituisce il numero di figli del nodo che sono foglie (cioè che non hanno a loro volta figli).

Modifica dei dati

• setInfo(T info)
  Imposta una nuova informazione nel nodo.
• setParent(NodoVP<T> parent)
  Imposta il nodo padre del nodo corrente.
• setLevel(int level)
  Imposta il livello del nodo nell’albero.
• addChild(NodoVP<T> child)
  Aggiunge un nuovo figlio al nodo e aggiorna automaticamente il livello del figlio.
• addChild(NodoVP<T> child, T info)
  (Deprecated) — Aggiunge un figlio sovrascrivendone l’informazione. Questo metodo non è utilizzato nella nostra implementazione.