Alberi_Qualsiasi_N-ari

ESERCIZI PER ALBERI QUALSIASI

CONTA-NODI(t)---------------CHIEDI SE GIUSTO--------------
    if(t==null)
        return 0;
    if(t.left!=NULL)
        L= 1+CONTA-NODI(t.left);
    if(t.right!=NULL)
        r= 1+CONTA-NODI(t.right);
    return 1+l+r; //avevi sbagliato con t.parent

----------------------------------------------------------------------------------------

CERCA(T,k)
    if(T==null)
        return NULL;
    if(T.info==k)
        return T;
    l=CERCA(t.left)
    if(l!=NULL)
        return l;
    r = CERCA(T.right)
    if(r!=NULL)
        return r;
    return NULL
}

-------------------------------------------------------------------------

BINARIO(T)
    return BINARIO-RADICE(t.root)

BINARIO-RADICE(T){
if(t==NULL)
    return true;
return BINARIO-RIC(T.left, 1);
}

BINARIO-RIC(T, i)
    if(t==null)
        return TRUE;
    if(i<0)
        return FALSE
    ritorno_right = BINARIO-RIC(T.right, i-1)
    if(!ritorno_right)
        return FALSE;
    ritorno_left = BINARIO-RIC(T.left, 1)
    if(!ritorno_left)
        return FALSE;
    return TRUE;

----------------------------------------------------------------------------------

GRADO-MASSIMO(T)
    return GRADO-MASSIMO-RIC(T.root)

GRADO-MASSIMO-RIC(T)
if(T==NULL)
    return 0;
cont = 1+GRADO-MASSIMO-RIC(T.right)
figli = GRADO-MASSIMO-RIC(T.left)
return Max(cont , figli);

---------------------------------------------------------------------------------

COPIA_ALBERO(t)
    n = CONTA_NODI(t.root)
    /* nuovonodo è un array di dimensione n, dove nuovonodo[i] è un riferimento al nodo del nuovo albero che rappresenta la copia del       nodo dell’albero t con indice i */
    for i = 0 to nuovonodo.length{
        /* creo un nuovo nodo nuovonodo[i] */
        nuovonodo[i].info = i
        nuovonodo[i].parent = NULL
        nuovonodo[i].left = NULL
        nuovonodo[i].right = NULL
    }
    /* tout è un nuovo albero */
    tout.root = NULL
    /* inizializzazione (non indispensabile) */
    if (t.root != NULL)
        tout.root = nuovonodo[t.root.info]
    COPIA(t.root, nuovonodo)
    return tout

CONTA_NODI(n)
    if (n == NULL)
        return 0
    return 1 + CONTA_NODI(n.right) + CONTA_NODI(n.left)

COPIA(n, nuovonodo)
    if (n == NULL)
         return
    if (n.parent != NULL)
        nuovonodo[n.info].parent = nuovonodo[n.parent.info]
    if (n.left != NULL)
        nuovonodo[n.info].left = nuovonodo[n.left.info]
    if (n.right != NULL)
        nuovonodo[n.info].right = nuovonodo[n.right.info]
    COPIA(n.left, nuovonodo)
    COPIA(n.right, nuovonodo)
------------------------------------------------------------------------