In informatica un albero n-ario è un albero i cui nodi hanno, al più, grado n; per albero si intende un grafo non orientato, connesso ed aciclico. È una struttura dati ampiamente utilizzata in campo informatico.
Come da caratteri comuni degli alberi, esso ha un nodo chiamato radice (o root), che può avere un numero di figli in numero pari o inferiore all'arietà dell'albero. I nodi senza figli vengono detti foglie e tutti gli altri sono chiamati nodi interni. Gli n nodi figli dello stesso genitore vengono chiamati fratelli.
Una sequenza di nodi e rami tali che ciascun nodo (tranne l'ultimo) sia padre del successivo si chiama cammino.
Il numero di archi (o rami) coinvolti in un cammino è detta lunghezza del cammino.
In generale, un cammino con K nodi ha K-1 archi, ossia ha lunghezza K-1.
La lunghezza del più lungo cammino da un nodo ad una foglia si chiama altezza del nodo; tutte le foglie hanno infatti altezza 0, e i genitori delle foglie, altezza 1.
Se T è un albero e X è un suo nodo, l'insieme dei nodi di T contenente X e tutti i suoi discendenti si chiama sotto-albero di T. X è detta radice del sotto-albero.
Implementazione degli alberi n-ari
[modifica | modifica wikitesto]Tramite l'utilizzo di strutture di programmazione generiche, è possibile dare delle diverse implementazioni agli alberi n-ari. Una delle più diffuse per questa struttura dati, attuabile utilizzando uno dei tanti linguaggi di programmazione, è l'implementazione dinamica primo figlio-fratello, conveniente perché prescinde dal numero di figli che può avere un nodo.
In questa implementazione ogni nodo ha sempre e solo due riferimenti:
- al primo figlio (a sinistra)
- al primo fratello (a destra)
A seguire, degli esempi di queste implementazioni.
Implementazione primo figlio-fratello
[modifica | modifica wikitesto]Ecco il codice sorgente Java di una implementazione con visite preorder e postorder:
class NTreeNode<E> //implementazione nodo albero con tipo generico E
{
protected NTreeNode firstChild; //primo figlio
protected NTreeNode sibling; //fratello
protected E element; //elemento del nodo
public NTreeNode() //costruttore
{
this(null,null, null);
}
public NTreeNode(E element, NTreeNode firstChild)
{
this(element, firstChild,null);
}
public NTreeNode(E element, NTreeNode firstChild, NTreeNode sibling)
{
this.element=element;
this.firstSon=firstChild;
this.sibling=sibling;
}
public String toString(){
return (String) element;
}
}
public class NTree //classe pubblica albero
{
protected NTreeNode root; //radice dell'albero
protected int size; //variabile per la grandezza dell'albero
public NTree() //costruttore
{
root=null;
size=0;
}
public boolean insert(NTreeNode parent, NTreeNode[] children) //metodo per l'inserimento
{
if(this.search(parent) && children.length!=0)
{
NTreeNode temp=this.searchNode(parent);
temp.firstChild = children[0];
for(int i=1; i < children.length; i++)
temp=temp.sibling = children[i];
return true;
}
else
System.out.println("Errore, nodo inesistente. Impossibile inserire i nodi dei figli");
//stampa errore
return false;
}
public boolean search(NTreeNode node) //metodo per la ricerca di un nodo
{
NTreeNode p=this.root;
if(p!=null){
if(p==node) return true;
else
{
NTreeNode t=p.firstChild;
while(t!=null)
{
search(t);
t = t.sibling;
}
}
}
return false;
}
public TNodeList searchNode(TNodeList node)
{
TNodeList p=this.root;
if(p!=null){
if(p==node) return p;
else
{
TNodeList t=p.children.head;
while(t!=null)
{
search(t);
t=t.next;
}
}
}
return null;
}
public void preorder(){
preorder(root);
}
public void preorder(NTreeNode p){
if(p!=null){
System.out.println(p.toString());
NTreeNode t=p.firstChild;
while(t!=null){
preorder(t);
t = t.sibling;
}
}
}
public void postorder(){
postorder(root);
}
public void postorder(NTreeNode p){
if(p!=null){
NTreeNode t=p.firstChild;
while(t!=null){
postorder(t);
t = t.sibling;
}
System.out.println(p.toString());
}
}
}
Implementazione con lista collegata
[modifica | modifica wikitesto]Di seguito, un'altra implementazione di alberi n-ari molto diffusa, stavolta sfruttando delle liste concatenate. Il linguaggio di programmazione scelto per questa implementazione è il Java.
class TNodeList<E>
{
public E element;
public TNodeList next;
public LinkedList children;
public TNodeList(E element)
{
children=new LinkedList();
this.element=element;
}
public String toString()
{
return (String)this.element;
}
}
class LinkedList
{
TNodeList head, tail;
int size;
public LinkedList(){
head=tail=null;
size=0;
}
public void addFirst(TNodeList node)
{
if(head==null){
head=tail=node;
}
else
{
node.next=head;
head=node;
}
size++;
}
public void addLast(TNodeList node)
{
if(tail==null)
{
head=tail=node;
}
else
{
tail.next=node;
tail=node;
}
size++;
}
}
public class NTL
{
public TNodeList root;
public int size;
public NTL(TNodeList root)
{
this.root=root;
size=0;
}
public boolean insert(TNodeList[] children, TNodeList parent)
{
if(this.search(parent))
{
TNodeList tmp=this.searchNode(parent);
if(children.length!=0)
{
for(int i=0; i<children.length; i++)
{
parent.children.addLast(children[i]);
}
return true;
}
else
{
System.out.println("Nessun figlio da inserire");
return false;
}
}
System.out.println("Nodo genitore inesistente");
return false;
}
public boolean search(TNodeList node)
{
if(size!=0)
{
TNodeList p=this.root;
if(p!=null)
{
if(p==node) return true;
else
{
TNodeList t = p.children.head;
while(t!=null)
{
search(t);
t=t.next;
}
}
}
}
return false;
}
public TNodeList searchNode(TNodeList node)
{
TNodeList p=this.root;
if(p!=null){
if(p==node) return p;
else
{
TNodeList t = p.children.head;
while(t!=null)
{
search(t);
t=t.next;
}
}
}
return null;
}
public void preorder(){
preorder(root);
}
public void preorder(TNodeList p){
if(p!=null){
System.out.println(p.toString());
TNodeList t = p.children.head;
while(t!=null){
preorder(t);
t=t.next;
}
}
}
public void postorder(){
postorder(root);
}
public void postorder(TNodeList p){
if(p!=null){
TNodeList t = p.children.head;
while(t!=null){
postorder(t);
t=t.next;
}
System.out.println(p.toString());
}
}
