albero binario
albero binario
albero binario particolare albero in cui da ciascun nodo-padre discendono al massimo due nodi-figli. I due rami che discendono da un nodo sono detti figlio sinistro e figlio destro: uno dei due o entrambi possono non esistere. Ogni ramificazione successiva determina un nuovo livello di profondità dell’albero. Indicando con 0 il livello del nodo che costituisce la radice dell’albero, il numero totale dei nodi di un livello l è n = 2l.
La visita di un albero per la costruzione di algoritmi di ricerca è particolarmente significativa nel caso di un albero binario ordinato (in cui cioè è definito un ordinamento dei nodi). Essa può avvenire secondo tre modalità:
• visita anticipata, o in preordine, in cui per ogni nodo si analizza il nodo stesso poi il suo ramo sinistro e quindi il suo ramo destro;
• visita simmetrica, o in ordine, in cui per ogni nodo si analizza prima il suo ramo sinistro, poi il nodo stesso quindi il suo ramo destro;
• visita posticipata, o differita o in postordine, in cui per ogni nodo si analizza prima il suo ramo sinistro, poi quello destro, infine il nodo stesso.
