Comprovar la propietat 'Suma dels fills' en un arbre binari usant memòria dinàmica X86759


Statement
 

pdf   zip   tar

html

Escriviu el codi del mètode compleix_suma_fills de la classe arbreBin que, donat un arbre binari d’enters, compleix que per tot node el seu valor és igual a la suma dels valors dels nodes (arrels) del fill esquerre i del fill dret. Considereu que els fills buits tenen un valor de node igual a 0, i que els nodes fulla sempre compleixen la propietat.

bool compleix_suma_fills() const; /* Pre: true */ /* Post: Retorna si compleix la propietat 'Suma dels fills': Per tot node el seu valor es igual a la suma dels valors dels nodes (arrels) del fill esquerre i del fill dret */

Entrada

Com a entrada hi haurà la mida de l’arbre i els nodes de l’arbre binari en postordre. Per cada node s’indica el seu valor i el nombre de fills (2 fills, -1 indica un fill esquerra, 1 indica un fill dret o 0 fills).

Per llegir els arbres, s’ha utilitzat l’operador >> que es troba definit a la classe arbreBin.

Sortida

Com a sortida es mostrarà l’estructura de l’arbre binari seguit d’un d’aquests dos textos:

L'arbre compleix la propietat 'Suma dels fills'.
L'arbre no compleix la propietat 'Suma dels fills'.

Per escriure els arbres, s’ha utilitzat l’operador << que es troba definit a la classe arbreBin.

Observació

Feu la solució usant els atributs privats de la classe enlloc dels mètodes públics. Per això s’ha definit a la part privada de la classe aquest mètode que també heu d’implementar:

static bool compleix_suma_fills(node_arbre* p); /* Pre: true */ /* Post: Retorna si l'arbre apuntat per p compleix la propietat 'Suma dels fills': Per tot node el seu valor es igual a la suma dels valors dels nodes (arrels) del fill esquerre i del fill dret */

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

tar cvf program.tar arbreBin_compleix_suma_fills.cpp

Observeu que per compilar us donem el Makefile, la classe arbreBin amb tots els seus mètodes implementats excepte els dos mètodes compleix_suma_fills i el programa principal program.cpp.

Public test cases

  • Input

    6
3 0
5 0
8 2
2 0
2 -1
10 2

    Output

    [10]
 \__[2]
 |   \__.
 |   \__[2]
 |       \__.
 |       \__.
 \__[8]
     \__[5]
     |   \__.
     |   \__.
     \__[3]
         \__.
         \__.
L'arbre compleix la propietat 'Suma dels fills'.

  • Input

    7
2 0
7 0
1 1
6 0
5 -1
6 2
8 2

    Output

    [8]
 \__[6]
 |   \__[5]
 |   |   \__.
 |   |   \__[6]
 |   |       \__.
 |   |       \__.
 |   \__[1]
 |       \__[7]
 |       |   \__.
 |       |   \__.
 |       \__.
 \__[2]
     \__.
     \__.
L'arbre no compleix la propietat 'Suma dels fills'.
    • Information
    Author
    Neus Català - Jordi Esteve
    Language
    Catalan
    Official solutions
    Make
    User solutions
    Make