Algoritmi e strutture dati - Specifiche: Alberi

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