Arbre binari. Calcula arbre amb factors d'equilibri X34743

Statement

html

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

void arbre_factors_equilibri();

que modifica el contingut de l’arbre per tal de guardar a cada node el factor d’equilibri (diferència entre l’altura del fill esquerra i l’altura del fill dret).

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); // Modifica el contingut de l’arbre per tal de guardar a cada node el factor // d’equilibri (diferència entre l’altura fill esquerra i l’altura fill dret). void arbre_factors_equilibri(); 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 arbre_factors_equilibri

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

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 (mira 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

El contingut de l’arbre binari abans i desprès de cridar el mètode arbre_factors_equilibri.

Observació

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

Public test cases

Input

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

Output

[7]
 \__[8]
 |   \__[4]
 |   |   \__[3]
 |   |   |   \__.
 |   |   |   \__.
 |   |   \__[6]
 |   |       \__.
 |   |       \__.
 |   \__[9]
 |       \__.
 |       \__.
 \__[5]
     \__.
     \__.

[-2]
 \__[-1]
 |   \__[0]
 |   |   \__[0]
 |   |   |   \__.
 |   |   |   \__.
 |   |   \__[0]
 |   |       \__.
 |   |       \__.
 |   \__[0]
 |       \__.
 |       \__.
 \__[0]
     \__.
     \__.

Input

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

Output

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

[-1]
 \__[-2]
 |   \__[2]
 |   |   \__.
 |   |   \__[-1]
 |   |       \__[0]
 |   |       |   \__.
 |   |       |   \__.
 |   |       \__.
 |   \__[0]
 |       \__.
 |       \__.
 \__[1]
     \__[0]
     |   \__.
     |   \__.
     \__[-1]
         \__[0]
         |   \__.
         |   \__.
         \__.

Input

-1

Output

.

.

Input

3 -1 -1

Output

[3]
 \__.
 \__.

[0]
 \__.
 \__.

Input

3 2 -1 -1 -1

Output

[3]
 \__.
 \__[2]
     \__.
     \__.

[1]
 \__.
 \__[0]
     \__.
     \__.

Input

3 -1 2 -1 -1

Output

[3]
 \__[2]
 |   \__.
 |   \__.
 \__.

[-1]
 \__[0]
 |   \__.
 |   \__.
 \__.

Input

-3 -2 -1 -1 -4 -1 -1

Output

[-3]
 \__[-4]
 |   \__.
 |   \__.
 \__[-2]
     \__.
     \__.

[0]
 \__[0]
 |   \__.
 |   \__.
 \__[0]
     \__.
     \__.

Information

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