Arbre binari. Calcula arbre altures X11985

Statement

html

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

void arbre_altures();

que modifica el contingut de l’arbre per tal de guardar a cada node l’altura del seu subarbre.

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 l’altura // del seu subarbre. void arbre_altures(); 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_altures

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

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

Observació

Només cal enviar la classe requerida i la implementació del mètode arbre_altures. 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]
     \__.
     \__.

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

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]
         |   \__.
         |   \__.
         \__.

[5]
 \__[4]
 |   \__[3]
 |   |   \__.
 |   |   \__[2]
 |   |       \__[1]
 |   |       |   \__.
 |   |       |   \__.
 |   |       \__.
 |   \__[1]
 |       \__.
 |       \__.
 \__[3]
     \__[1]
     |   \__.
     |   \__.
     \__[2]
         \__[1]
         |   \__.
         |   \__.
         \__.

Input

-1

Output

.

.

Input

3 -1 -1

Output

[3]
 \__.
 \__.

[1]
 \__.
 \__.

Input

3 2 -1 -1 -1

Output

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

[2]
 \__.
 \__[1]
     \__.
     \__.

Input

3 -1 2 -1 -1

Output

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

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

Input

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

Output

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

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

Information

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