10 : Allocazione dinamica della memoria Vers . 8.3 – Ottobre 2023
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