Nombre de nodes amb els dos subarbres buits d'un arbre binari X34192

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

  nat nodes_subarbres_buits() const;

que retorna el nombre de nodes amb els dos subarbres buits de l’arbre binari.

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>
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);

    // Retorna el nombre de nodes amb els dos subarbres buits
    nat nodes_subarbres_buits() const;

  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);

    // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació del mètode nodes\_subarbres\_buits

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 $nodes\_subarbres\_buits$.

Entrada

L’entrada consisteix en la descripció d’un arbre binari d’enters (el seu recorregut en preordre, en el qual inclou les fulles marcades amb un -1). Per exemple, l’arbre (mireu el PDF de l’enunciat)

es descriuria amb

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

Sortida

Una línia amb el nombre de nodes amb els dos subarbres buits de l’arbre binari.

Observació

Només cal enviar la classe requerida i la implementació del mètode $nodes\_subarbres\_buits$. Podeu ampliar la classe amb mètodes privats. Seguiu estrictament la definició de la classe de l’enunciat.