Fondamenti di programmazione - Appunti

Formattazione del testo

T=T ,…,T . Siano S(T ),…,S(T ) vere,1 k 1 k Tcioè #NULL in T è V(T )+1, per T ki i 1ogni i=1,…,k.I puntatori NULL in T sono: rightsibling di r, e quelli diogni sottoalbero, tranne il rightsibling di c ,…,c1 k-1# in T =NULL=1 +( in T -1)+…+( in T -1)+( in T )#NULL #NULL #NULL1 k-1 k=1+(V(T )+1-1)) +…+ (V(T )+1-1)+V(T )+11 k-1 k=1 + V(T )+…+V(T )+V(T )+11 k-1 k=V(T) +1 Ricorsione su alberi rSchema generale funzione P(T) cc … kP(T) T= 1{ Azione A TT k0 1P(T );1Azione A ;1P(T );2…Azione A ;k-1P(T );kAzione A }k Visite di alberiVisita Preorder: si devono listare i nodi dell’albero inmodo tale che1. ogni nodo precede nella lista tutti i suoidiscendenti2. la lista rispetta le relazione sinistra-destraa (a,b,e,c,d,f,e)c dbe f g Visite di alberi rVisita Preorder: si devono listare inodi dell’albero in modo tale che1. ogni nodo precede nella lista tutti c … cT= 1 ki suoi discendenti2. la lista

rispetta le relazione Tsinistra-destra T1 kvoid preorder (pNode n){
    typedef struct NODE *pNODE;
    pNODE c; /* figlio di n*/
    printf("<c>%c\n</c>", n->nodelabel);
    struct NODE{
        c=n->leftmostchild;
        char nodelabel;
        while (c != NULL){
            pNODE leftmostchild;
            preorder(c);
            rigthsibling;
            c=c->rightsibling;
        }
    }
}

Visite di alberivoid preorder (pNode n) r{
    pNODE c; /* figlio di n*/
    printf("<c>%c\n</c>", n->nodelabel);
    c … cT= 1 kc=n->leftmostchild;
    while (c != NULL) {
        preorder(c);
        c=c->rightsibling;
    }
    T T
}

1 kCORRETTEZZAS(T): preorder(T) stampa la lista preorder di TBASE. Se T ha un solo nodo, lo stampa e si fermaPASSO. I.I.: preorder(T ) da L = lista preorder di T ,i i iper ogni i=1,…,k.Quindi preorder(T) daL=(r, L ,…,L )=lista preorder di T1 kVisite di alberivoid preorder (pNode n) r{
    pNODE c; /* figlio di n*/
    printf("<c>%c\n</c>", n->nodelabel);
    c … cT= 1 kc=n->leftmostchild;
    while (c != NULL) {
        preorder(c);
        c=c->rightsibling;
    }
    T T
}

1 kR.T.: O(n),

postorder di TBASE. Se T ha un solo nodo, lo stampa e si ferma
PASSO. I.I.: postorder(T ) da M = lista postorder deli isottoalbero, per ogni i=1,…,k.
postorder(T) da M=(M ,…,M ,r)=lista postorder di T1 kR.T. O(n), dove n è il numero di nodi di T
Computo dell’ Altezza di un albero
Altezza di un nodo n= max distanza di n da una foglia suadiscendente
Altezza albero= altezza radice
Altezza di una foglia = 0
Altezza di un nodo interno n= 1 + (altezza sottoalbero radicato in n)
= 1 + max altezza figli di n
a Altezza di a = 1 + max { altezza di b, altezza di c,altezza di d }
c d
b = 1 + max { 1,0,1}
= 1 + 1 = 2
e f g 
Computo altezza
Vogliamo una funzione che per ogni nodo calcola l’altezza
del nodo e la scrive nel campo heigth.
typedef struct NODE *pNODE
struct NODE{
char nodelabel;
int height;
pNODE leftmostchild,rigthsibling;
}
Altezza di un nodo interno n = 1 + max altezza figli di n
IDEA: per ogni nodo calcola (ricorsivamente) l’altezza di
ogni suo sottoalbero e calcola il

maxVisite di alberi

IDEA: per ogni nodo calcola r (ricorsivamente) l'altezza di ogni suo sottoalbero e calcola il max c


void computeHt (pNode n){
    pNODE c;
    n->height = 0;
    c = n->leftmostchild;
    while (c != NULL){
        computeHt(c);
        if (c->height >= n->height)
            n->height = 1 + c->height;
        c = c->rightsibling;
    }
}


Computo altezza


void computeHt (pNode n){
    pNODE c;
    n->height = 0;
    c = n->leftmostchild;
    while (c != NULL) {
        computeHt(c);
        if (c->height >= n->height)
            n->height = 1 + c->height;
        c = c->rightsibling;
    }
}


CORRETTEZZA S(T): computeHt(n) calcola correttamente l'altezza del nodo n

BASE: Se T ha un solo nodo, pone height = 0 e si ferma

PASSO: I.I.: computeHt(n) calcola correttamente l'altezza del nodo n

computeHt(n) calcola correttamente l'altezza del figlio n di n, per ogni i=1,...,k. in->heigth= max{1+ n ->height, ..., 1+ n ->height}1 k= max{1+ altezza T ,, ..., 1+ altezza T } (per I.I)1 k= 1 + max altezza sottoalberi

Alberi Binari

Ogni nodo ha < 2 figli: figlio destro, figlio sinistro

a db gfe c

Alberi Binari

Definizione ricorsiva

BASE. Albero vuoto è albero binario

PASSO. Dati 2 alberi binari T ,T ed un nuovo nodo r1 2rT= è un albero binarioT T1 2 con sottoalbero di sinistra T 1sottoalbero di destra T 2

Alberi Binari

Bastano due puntatori per nodo:figlio destro, figlio sinistro

Struttura dati

Typedef struct NODE *TREE
struct NODE{
  etype nodelabel;
  TREE leftchild, rightchild;
}

Ricorsione su Alberi Binari

FUNZIONE (T TREE){
  Azione A 0
  FUNZIONE(T )1
  Azione A ;1
  FUNZIONE(T )2
  Azione A ;2
}

Visita Inorder

Visita Inorder: si devono visitare i nodi dell'albero in modo tale che

1. ogni nodo segue nella lista tutti i nodi del sottoalbero di sinistra
2. precede

elementi permettendo

1. Inserzione di nuovi elementi (insert)
2. Cancellazione di elementi dall'insieme (delete)
3. Ricerca di un elemento per sapere se è nell'insieme (lookup)

Insieme di elementi = dizionario

Assumiamo: elementi del dizionario scelti da un insieme (detto universo) ordinato (esiste relazione <); es. interi, reali, stringhe caratteri.

Alberi Binari di RICERCA

Albero binario di ricerca (BST): albero binario con "label" tale che per ogni nodo n

1. ogni nodo nel sottoalbero sinistro di n ha label < della label di n
2. ogni nodo nel sottoalbero destro di n ha label > della label di n

Alberi Binari di RICERCA

Albero binario di ricerca (BST):

10
   / \
  5   15
 /   /  \
11  11   20
   / \
  22  22

SI

NO

Alberi Binari di RICERCA

Albero binario di ricerca (BST):

albero binario con“label” tale che per ogni nodo n
1. ogni nodo nel sottoalbero sinistro di n ha label < della label di n
2. ogni nodo nel sottoalbero destro di n ha label > della label di n

10
    10
        15
            15
            7
                7
            20
                20
            5
                11
              &

return FALSE;
else if (x==T->element) return TRUE;
else if (x<T->element) return lookup(T->leftchild, x);
else return lookup(T->rightchild, x)

Alberi Binari di RICERCA
BOOLEAN lookup(TREE T, etype x){
    if(T==NULL) return FALSE;
    else if (x==T->element) return TRUE;
    else if (x<T->element) return lookup(T->leftchild, x);
    else return lookup(T->rightchild, x)
}