Torna alla pagina di Algoritmi e strutture dati
:: Algoritmi e strutture dati - Specifiche ::
Alberi
Sintassi
- creaalbero: () -> albero
Crea ed inizializza un albero vuoto.
- alberovuoto: (albero) -> booleano
Restituisce vero o falso a seconda che l'albero sia vuoto o no.
- radice: (albero) -> nodo
Accede direttamente alla radice.
- padre: (nodo, albero) -> nodo
Accede al padre di un nodo.
- primofiglio: (nodo, albero) -> nodo
Accede al primo figlio di un nodo.
- succfratello: (nodo, albero) -> nodo
Accede al fratello successivo di un nodo.
- foglia: (nodo, albero) -> booleano
Restituisce vero o falso a seconda che il nodo abbia figli o no.
- finefratelli: (nodo, albero) -> booleano
Restituisce vero o falso a seconda che siano stati considerati tutti i fratelli o no.
- insradice: (nodo, albero) -> albero
Inserisce la radice in un albero vuoto.
- inssottoalbero: (nodo, nodo, albero, albero) -> albero
Inserisce un sottoalbero.
- cancsottoalbero: (nodo, albero) -> albero
Cancella un sottoalbero.
- legginodo: (nodo, albero) -> tipoelem
Legge il valore contenuto in un nodo.
- scrivinodo: (tipoelem, nodo, albero) -> albero
Cambia il valore memorizzato in un nodo.
Semantica
- creaalbero() = T'
Post: T' = Λ
- alberovuoto(T) = b
Post: b = vero, se T = Λ; b = falso altrimenti
- radice(T) = u
Pre: T ≠ Λ
Post: u = r
- padre(u,T) = v
Pre: T ≠ Λ, u nodo in T, u ≠ r
Post: u = r
- finefratelli(u, T) = b
Pre: T ≠ Λ, u nodo in T o "sentinella" s
Post: b = vero, se u = s; b = falso altrimenti
- primofiglio(u, T) = v
Pre: T ≠ Λ, u nodo in T, foglia(u,T) = falso
Post: v è primo figlio secondo la relazione di precedenza stabilita tra i figli di u
- succfratello(u, T) = v
Pre: T ≠ Λ, u nodo in T
Post: v nodo che segue u nella relazione di precedenza (v=s se u è l'ultimo fratello)
- foglia(u, T) = b
Pre: T ≠ Λ, u nodo in T
Post: b = vero, se non esiste v in T tale che v = padre(v, T); b = falso altrimenti
- insradice(u,T) = T'
Pre: T = Λ
Post: T' = {u} con u = r, radice di T
- inssottoalbero(u, v, T, U) = T'
Pre: T ≠ Λ, U ≠ Λ, u e v nodi in T, v figlio di u oppure v = u
Post: T' ottenuto da T aggiungendo U come sottoalbero: radice z di U diventa il nuovo fratello che segue v, se u ≠ v, oppure primo diflio di u, se u = v
- cancsottoalbero(u, T) = T'
Pre: T ≠ Λ, U ≠ Λ, u nodo in T
Post: T' ottenuto da T eliminando sottoalbero di radice u; T = Λ se u = r
- legginodo(u, T) = a
Pre: T ≠ Λ, u nodo in T
Post: a è valore memorizzato in u
- scrivinodo(a, u, T) = T'
Pre: T ≠ Λ, u nodo in T
Post: T' è ottenuto da T scrivendo il valore a nel nodo u
Torna alla pagina di Algoritmi e strutture dati
