Appunti di informatica sugli Alberi

Alberi

Alberi binari

Implementazione di alberi binari mediante puntatori.

Definizione

Un albero binario è una struttura dati nella quale ogni nodo ha al massimo due figli, chiamati figlio sinistro e figlio destro.

Funzioni di base

Le funzioni di base per la gestione degli alberi binari includono operazioni come inserimento, cancellazione e ricerca di nodi.

Visita degli alberi

• Visita anticipata / preordine
• Visita simmetrica
• Visita in post ordine

Funzioni alberi binari

• Ricerca
• Cancella

Albero binario di ricerca

Un albero binario è detto di ricerca se soddisfa le seguenti proprietà.

Funzioni di un albero binario di ricerca

• Ricerca
• Visita
• Inserimento di una nuova foglia (elemento)

Questa funzione inserisce il "dato" nell'albero A, e ritorna true (un numero diverso da zero, solitamente 1) se l'elemento è stato inserito correttamente.

Cancellazione

• Cancellazione dell'intero albero
• Cancellazione di un nodo (elemento che ha dei figli)
• Cancellazione di un elemento in un albero binario di ricerca

Alberi generali

Possono avere più di 2 figli, a differenza di quelli binari.

Definizione

Gli alberi generali sono strutture dati in cui ogni nodo può avere un numero variabile di figli.

Funzioni

Le funzioni per gli alberi generali includono inserimento, ricerca e cancellazione, adattate per gestire più figli.

Visita

La visita degli alberi generali può includere tecniche come preordine, postordine, o livello per livello, adattando le visite binarie alle loro caratteristiche.

Albero generale ---> Albero binario