Sub Tree C

[Cr4m3]

Salve a tutti, è la prima volta che posto qui, volevo un vostro consiglio su queste due funzioni, dato che abbiamo avuto una discussione con un mio amico sulla loro fattibilità.

Secondo voi sono giuste?

Grazie mille per le risposte.

P.S. Scusate se non ci sono commenti, cmq il codice dovrebbe essere chiaro

/----------/
Si definisca una funzione ricorsiva C che restituisce 1 se il primo dei due alberi in input e' un sottoalbero del secondo, 0 altrimenti. La funzione ha il seguente prototipo: int subTree(treePtr T, treePtr U). (Suggerimento: si usi una funzione d'appoggio per testare l'uguaglianza di alberi).

int alberiuguali(TreePtr A,TreePtr B)
{
/*PostC: Restituisce 1 se l'albero A è uguale all'albero B, restituisce 0
quando trova un valore di A diverso da quello di B;*/

if(A==NULL && B==NULL) return 1;

if(!A) return 0;
if(!B) return 0;

if(A->info == B->info)
{
alberiuguali(A->lPtr,B->lPtr);
alberiuguali(A->rPtr,B->rPtr);
}
else
return 0;
}

int subTree(TreePtr T, TreePtr U)
{

//PostC: Restituisce 1 se T è un sottoalbero di U, 0 altrimenti;

int ris1, ris2;

if(!T) return 1;
if (!U) return 0;

ris1 = alberiuguali(U->lPtr, T);

if (ris1 == 1)
return 1;

ris2 = alberiuguali(U->rPtr, T);

if (ris2 == 1)
return 1;

return 0;
}

[cionci]

Un errore c'è perchè tu non fai una ricorsione nelle funzione subTree... Se per sottoalbero si intende che l'abero T possa essere essere un sottoalbero di U a partire da qualsiasi livello, allora il tuo codice è sbagliato perchè controlli sono il primo livello...

int subTree(TreePtr T, TreePtr U)
{

//PostC: Restituisce 1 se T è un sottoalbero di U, 0 altrimenti;

  /*verifico se a questo livello sono uguali*/
  if(alberiuguali(U, T) > 0)
     return 1:
  
  /*a questo livello la condizione non si è verificata, bisogna scendere in un sotto livello*/
  if((subTree(T, U->lPtr)+subTree(T, U->rPtr)) > 0)
    return 1;
  
  return 0; 
}

C'è anche un errorino nella prima funzione: ti ritornava sempre zero perchè non facevi un retarn nel caso in cui entrambi i sottoalberi fossero uguali...

int alberiuguali(TreePtr A,TreePtr B)
{
    /*PostC: Restituisce 1 se l'albero A è uguale all'albero B, restituisce quando trova un valore di A diverso da quello di B;*/

    if(A==NULL && B==NULL) return 1;

    if(!A) return 0;
    if(!B) return 0;

    if(A->info == B->info)
    {
        if((alberiuguali(A->lPtr,B->lPtr) + alberiuguali(A->rPtr,B->rPtr)) == 2)
            return 1;
    }
    else
        return 0;
}

[Cr4m3]

cmq io pensavo che T sottoalbero di U, fosse il sottoalbero radicato in U->lptr e in U->rPtr

[cionci]

Originariamente inviato da Cr4m3

cmq io pensavo che T sottoalbero di U, fosse il sottoalbero radicato in U->lptr e in U->rPtr

Sinceramente non lo so...ma io come sottoalbero darei una definizione che coincide con quello che ho scritto sopra... Se hai una definizione formale è ben accetta... Cmq anche con la tua definizione la prima funzione aveva quel problemino...

[Cr4m3]

Questa viene dagli appunti della professoressa.

[cionci]

Infatti è come dico io... L'albero formato dai nodi 3 e 4 è sottolabero del nodo 2, e quindi è sottoalbero dell'albero principale...anche se il sottoalbero 3 e 4 non è figlio del nodo radice...

[Cr4m3]

ok grazie mille

[Cr4m3]

un ultima cosa, non è che avessi qualche appunto, qualche sito o qualche libro da consigliarmi, dove vengono spiegati in maniera chiara e semplice sti benedetti alberi, Grazie

[cionci]

No...mi dispiace... Ho avuto da sempre un particolare feeling con gli alberi e le strutture e la programmazione ricorsive... Mi sono sempre basato sugli appunti