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

Statement

html

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.

Public test cases

Input

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

Output

Information

Author: Jordi Esteve
Language: Catalan
Official solutions: C++
User solutions: C++