10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
Dopo avere introdotto tutti i concetti relativi ad un albero possiamo darne, comprendendone il significato, la seguente definizione ricorsiva:
DEF. 2( RICORSIVA) Un albero è un insieme non vuoto T di nodi dove: a) esiste un solo nodo distinto detto radice; b) i rimanenti nodi sono ripartiti in n insiemi tutti disgiunti T1, T2, …. Tn con n ≥ 0 ciascuno dei quali è a sua volta un albero
Se l’ insieme T è vuoto si parla di albero vuoto
PROBLEMA DELL’ ATTRAVERSAMENTO DI UN ALBERO
In informatica è fondamentale trovare dei buoni metodi o algoritmi di attraversamento o visita di un albero poiché tali operazioni sono fortemente richieste dalle applicazioni che li utilizzano.
Notazione: esame di un nodo: significa accedere al nodo ed estrarre le informazioni contenute in esso;
attraversare o visitare un albero: significa esaminare sistematicamente in un ordine appropriato tutti i nodi di un albero in modo che ciascun n odo venga visitato una volta sola;
attraversamento o visita di un albero: significa trovare un qualsiasi algoritmo che ci permetta di visitare un albero
I due principali algoritmi di attraversamento di un albero sono: 1) attraversamento o visita in ordine ANTICIPATO( PRE-ORDER); 2) attraversamento o visita in ordine POSTICIPATO( POST ORDER);
Esempio: albero di riferimento
A
B C
D
M
N
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 52