Arbres Verd-Blau P24958

Considerem arbres binaris on cada node pot tenir un color associat: verd o blau. Diem que un arbre binari amb colors és un arbre verd-blau quan compleix aquestes dues propietats:

• Tot node verd té tots els seus fills blaus.
• Tots els camins que van d’un node fins a qualsevol de les seves fulles té el mateix nombre de nodes blaus.

Donat un arbre verd-blau, diem que la seva alçada blava és el nombre de nodes blaus en els camins des de la seva rel fins a les seves fulles (com que l’arbre és verd-blau, aquest valor és únic).

Per exemple, l’arbre de la figura següent és un arbre verd-blau i la seva alçada blava és 3.

Entrada

L’entrada comença amb un natural n, el nombre d’arbres que cal tractar. Després apareix la descripció dels n arbres, corresponent al seu recorregut en preordre, amb els nodes verds marcats amb caràcters G, els nodes blaus marcats amb caràcters B i els arbres buits marcats amb guions.

Sortida

Per a cada arbre de l’entrada, si aquest és un arbre verd-blau, cal escriure la seva alçada blava. Altrament, cal escriure no.

Observació

Heu de crear l’arbre on la informació del color sigui explícita en el node, i vetllar per no tenir fuites de memòria.