Arbre general. Quants nodes de grau n té? X10656


Statement
 

pdf   zip   main.cc

html

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

nat quants_grau(nat n) const;

que retorna quants nodes de grau n té.

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

#include <cstdlib> 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 primer 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_fill(Arbre<T> &a); static const int ArbreInvalid = 400; // Indica quants nodes de grau n té. nat quants_grau(nat n) 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 quants_grau



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 i desprès crida vàries vegades el mètode quants_grau.

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). A continuació segueix una seqüència d’enters que representen diferents valors per testejar quants_grau.

Sortida

Una línia per cada element n de la seqüència d’enters d’entrada, amb la quantitat de nodes de grau n que té.

Observació

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

Public test cases

  • Input

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

    Output

    12
4
3
2
0
1
0

  • Input

    7 0
0
1

    Output

    1
0

  • Input

    7 1
  8 0
0
1
2

    Output

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