Arbre general. Sumes dels elements de cada camí X17833


Statement
 

pdf   zip   main.cc

html

Donada la classe Arbre que permet gestionar arbres generals usant memòria dinàmica i un tipus T que disposa de l’operador +, cal implementar el mètode

vector<T> sumes_camins() const;

que retorna un vector amb les sumes de tots els elements de cada camí que va de l’arrel a una fulla. Els camins es visiten d’esquerra a dreta.

Cal enviar a jutge.org la següent especificació de la classe Arbre i la implementació del mètode dins del mateix fitxer. Indica dins d’un comentari a la capçalera del mètode el seu cost en funció del nombre d’elements n de l’arbre.

#include <cstdlib> #include <vector> using namespace std; typedef unsigned int nat; template <typename T> class Arbre { public: // Construeix un Arbre format per un únic node que conté a x. Arbre(const T &x); // Tres grans. Arbre(const Arbre<T> &a); Arbre& operator=(const Arbre<T> &a); ~Arbre() throw(); // Col·loca l’Arbre donat com a darrer fill de l’arrel de l’arbre sobre el que s’aplica el mètode i l’arbre a queda invalidat; després de fer b.afegir_fill(a), a no és un arbre vàlid. void afegir_darrer_fill(Arbre<T> &a); static const int ArbreInvalid = 400; // Retorna un vector amb les sumes de tots els elements de cada camí que va de l’arrel a una fulla. vector<T> sumes_camins() const; private: Arbre(): _arrel(NULL) {}; struct node { T info; node* primf; node* seggerm; }; node* _arrel; static node* copia_arbre(node* p); static void destrueix_arbre(node* p) throw(); // Aquí va l’especificació dels mètodes privats addicionals }; // Aquí va la implementació del mètode sumes_camins



Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe Arbre i un programa principal que llegeix un arbre general d’enters i desprès crida el mètode sumes_camins.

Entrada

L’entrada consisteix en la descripció d’un arbre general d’enters (el seu recorregut en preordre, en el qual al valor de cada node li segueix el seu nombre de fills).

Sortida

Una línia per cada camí de l’arbre d’entrada, amb la suma de tots els enters del camí en qüestió.

Observació

Només cal enviar la classe requerida i la implementació del mètode sumes_camins amb el seu cost en funció del nombre d’elements n de l’arbre. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.

Public test cases

  • Input

    -7 3
  8 0
  4 2
    3 1
      0 1
        6 0
    -5 0
  2 4
    9 0
    1 0
    8 0
    5 0

    Output

    1
6
-8
4
-4
3
0

  • Input

    7 0

    Output

    7

  • Input

    7 2
  8 0
  -8 0

    Output

    15
-1
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++