La traccia è la seguente:
Dato un albero T i cui nodi sono etichettati con uno dei due possibili colori verde e giallo, progettare un algoritmo che stabilisca se esiste un cammino monocromatico radice-foglia. Scrivi uno pseudo codice ed analizza la sua complessità.
Allora io ovviamente ho utilizzato la tecnica del Divide et impera però ho qualche dubbio sull'ultima restituzione. Il mio pseudo codice è il seguente:
Sia n la radice dell'albero:
- Codice:
Alg(n)
If(n==NULL)
Return true;
Else {
If(n.dato.ch!=n.sx.dato.ch)
{ if(n.dato.ch!=n!dx.dato.ch)
Return false;
Else Return Alg(n.dx);
}
Else {
If(n.dato.ch!=n.dx.dato.ch)
Return Alg(n.sx);
Else return Alg(n.sx) && Alg(n.dx); (?????)
}
}
Mi rendo conto che la penultima riga di comando è scritta male ma non saprei come altro risolvere il problema.
Quando entrambi i figli hanno lo stesso colore cosa dovrebbe restituire il codice?
Grazie a chi risponderà!!