cerca
Algoritmi e strutture dati - Specifiche: Alberi
modifica cronologia stampa login logout

Wiki

UniCrema


Materie per semestre

Materie per anno

Materie per laurea


Help

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, ur
    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 uv, 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