Arbre binari. Comprovar la propietat "suma dels fills" X21635


Statement
 

pdf   zip   main.cc

html

Donada la classe Abin que permet gestionar arbres binaris usant memòria dinàmica, cal implementar el mètode

bool compleix_suma_fills();

que retorna si compleix la propietat ’Suma dels fills’: Per tot node el seu valor és igual a la suma dels valors dels nodes (arrels) del fill esquerre i del fill dret. Considera que els fills buits tenen un valor de node igual a 0, i que els nodes fulla sempre compleixen la propietat.

Cal enviar a jutge.org la següent especificació de la classe Abin i la implementació del mètode dins del mateix fitxer.

#include <cstdlib> #include <iostream> using namespace std; typedef unsigned int nat; template <typename T> class Abin { public: Abin(): _arrel(NULL) {}; // Pre: cert // Post: el resultat és un arbre sense cap element Abin(Abin<T> &ae, const T &x, Abin<T> &ad); // Pre: cert // Post: el resultat és un arbre amb un element i dos subarbres // Les tres grans Abin(const Abin<T> &a); ~Abin(); Abin<T>& operator=(const Abin<T>& a); // operador << d’escriptura template <class U> friend std::ostream& operator<<(std::ostream&, const Abin<U> &a); // operador >> de lectura template <class U> friend std::istream& operator>>(std::istream&, Abin<U> &a); bool compleix_suma_fills() const; // Pre: true // Post: retorna si compleix la propietat ’Suma dels fills’: // Per tot node el seu valor és igual a la suma dels valors // dels nodes (arrels) del fill esquerre i del fill dret. private: struct node { node* f_esq; node* f_dret; T info; }; node* _arrel; static node* copia_nodes(node* m); static void esborra_nodes(node* m); static void print_nodes(node* m, ostream &os, string d1); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació del mètode compleix_suma_fills i dels privats addicionals



Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe Abin i un programa principal que llegeix un arbre binari i desprès crida el mètode compleix_suma_fills.

Entrada

L’entrada consisteix en la descripció d’un arbre binari d’enters (el seu recorregut en postordre precedit per la mida de l’arbre). 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 exemple, l’arbre (mira el PDF de l’enunciat)

es descriuria amb

10 4 0 7 1 2 0 0 2 4 0 1 0 6 1 7 -1 5 2 3 2

Sortida

El contingut 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'.

Observació

Només cal enviar la classe requerida i la implementació del mètode compleix_suma_fills. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

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'.

  • Input

    10
4 0
7 1
2 0
0 2
4 0
1 0
6 1
7 -1
5 2
3 2

    Output

    [3]
 \__[5]
 |   \__[7]
 |   |   \__.
 |   |   \__[6]
 |   |       \__[1]
 |   |       |   \__.
 |   |       |   \__.
 |   |       \__.
 |   \__[4]
 |       \__.
 |       \__.
 \__[0]
     \__[2]
     |   \__.
     |   \__.
     \__[7]
         \__[4]
         |   \__.
         |   \__.
         \__.

L'arbre no compleix la propietat 'Suma dels fills'.
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++