Arbre 2-acolorit. X58923

Statement

html

Feu la funció

bool arbre2Acolorit(BinaryTree<int>);

tal que, donat un arbre binari A que només conté zeros i uns, torni true si i només si l’arbre està 2-acolorit.

Assumim que el número zero i el número u indiquen dos colors diferents. Diem que un arbre està 2-acolorit si tot node de l’arbre té un color diferent al dels seus fills (si en tingués).

Per exemple, els arbres A1 i A2 estan 2-acolorits, mentre que A3 no ho està perquè hi ha un node (marcat amb una fletxa) que té el mateix color que el seu fill.

         A1            A2          A3

         1             0           0
        / \           / \         / \
       0   0         1   1       1   1  <--
      / \ / \           /       /   / \
     1  1 1  1         0       0   1   0

La funció que heu de fer ha de ser al fitxer arbre2Acolorit.cpp.

La puntuació que podeu obtenir és la següent:

Solució correcta en els jocs de proves públics: 5 punts.
Solució correcta en els jocs de proves públics, especificació de la funció, H.I. i funció fita: 7 punts.
Solució correcta en els jocs de proves públics i privats: 8 punts.
Solució correcta en els jocs de proves públics i privats, especificació de la funció, H.I. i funció fita: 10 punts.

Només acceptarem una solució recursiva per a aquest problema.

Quan diem especificació de la funció, H.I. i funció fita volem dir que hi ha de ser tot. Dit altrament: no es donarà una fracció dels 2 punts si doneu només, per exemple, l’especificació de la funció, o només la H.I. i la fita. Se us donarà la bonificació dels 2 punts únicament si feu totes 3 coses correctament.

Entrada

La funció rep un arbre binari d’enters de zeros i uns.

Sortida

Torna un booleà b que és true (false altrament) si i només si l’arbre està 2-acolorit.

Observació

Heu d’enviar la solució comprimida en un fitxer .tar:

tar cvf program.tar arbre2Acolorit.cpp

Observeu que per compilar us donem el Makefile,

la capçalera del mòdul funcional arbre2Acolorit.hpp, la implementació de l’arbre binari BinaryTree.hpp, i el programa principal program.cpp.

Public test cases

Input

INLINEFORMAT
1(0(1(,),1(,)),0(1(,),1(,)))
0(1(,),1(0(,),))
0(1(0(,),),1(1(,),0(,)))

Output

SI
SI
NO

Input

VISUALFORMAT
             1
             |
      ------- -------
     |               |
     0               0
     |               |
 ---- ----       ---- ----
|         |     |         |
1         1     1         1

     0
     |
 ---- ----
|         |
1         1
          |
      ----
     |
     0

          0
          |
      ---- ----
     |         |
     1         1
     |         |
 ----      ---- ----
|         |         |
0         1         0

Output

SI
SI
NO

Information

Author: PRO1-Vilanova
Language: Catalan
Official solutions: Make
User solutions: Make