Arbre binari. Crea arbre binari complert de n nivells X75469
Donada la classe que permet gestionar arbres binaris usant memòria dinàmica, cal implementar el mètode
Abin(nat n);que crea un arbre binari complert amb nivells, on la informació de cada node de l’arbre és el nivell a on està situat.
Cal enviar a jutge.org la següent especificació de la classe i la implementació del mètode dins del mateix fitxer. Indica, dins d’un comentari a la capçalera del mètode, el seu cost en funció de , així com l’equació de recurrència que t’ha permès deduir el seu cost.
#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);
Abin(nat n);
// Pre: cert
// Post: Crea un arbre binari complert amb n nivells, on la informació
// de cada node de l'arbre és el nivell a on està situat
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 Abin(nat n) i privats addicionalsPer testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe i un programa principal que llegeix un natural i desprès crida el mètode .
Entrada
L’entrada consisteix en un natural.
Sortida
El contingut de l’arbre binari desprès de cridar el mètode .
Observació
Només cal enviar la classe requerida, la implementació del mètode i el seu cost en funció de , així com l’equació de recurrència que t’ha permès deduir el seu cost. Pots ampliar la classe amb mètodes privats. Segueix estrictament la definició de la classe de l’enunciat.
Input
0
Output
.
Input
1
Output
[1] \__. \__.
Input
2
Output
[1]
\__[2]
| \__.
| \__.
\__[2]
\__.
\__.
Input
3
Output
[1]
\__[2]
| \__[3]
| | \__.
| | \__.
| \__[3]
| \__.
| \__.
\__[2]
\__[3]
| \__.
| \__.
\__[3]
\__.
\__.
Input
4
Output
[1]
\__[2]
| \__[3]
| | \__[4]
| | | \__.
| | | \__.
| | \__[4]
| | \__.
| | \__.
| \__[3]
| \__[4]
| | \__.
| | \__.
| \__[4]
| \__.
| \__.
\__[2]
\__[3]
| \__[4]
| | \__.
| | \__.
| \__[4]
| \__.
| \__.
\__[3]
\__[4]
| \__.
| \__.
\__[4]
\__.
\__.
Input
5
Output
[1]
\__[2]
| \__[3]
| | \__[4]
| | | \__[5]
| | | | \__.
| | | | \__.
| | | \__[5]
| | | \__.
| | | \__.
| | \__[4]
| | \__[5]
| | | \__.
| | | \__.
| | \__[5]
| | \__.
| | \__.
| \__[3]
| \__[4]
| | \__[5]
| | | \__.
| | | \__.
| | \__[5]
| | \__.
| | \__.
| \__[4]
| \__[5]
| | \__.
| | \__.
| \__[5]
| \__.
| \__.
\__[2]
\__[3]
| \__[4]
| | \__[5]
| | | \__.
| | | \__.
| | \__[5]
| | \__.
| | \__.
| \__[4]
| \__[5]
| | \__.
| | \__.
| \__[5]
| \__.
| \__.
\__[3]
\__[4]
| \__[5]
| | \__.
| | \__.
| \__[5]
| \__.
| \__.
\__[4]
\__[5]
| \__.
| \__.
\__[5]
\__.
\__.
Input
6
Output
[1]
\__[2]
| \__[3]
| | \__[4]
| | | \__[5]
| | | | \__[6]
| | | | | \__.
| | | | | \__.
| | | | \__[6]
| | | | \__.
| | | | \__.
| | | \__[5]
| | | \__[6]
| | | | \__.
| | | | \__.
| | | \__[6]
| | | \__.
| | | \__.
| | \__[4]
| | \__[5]
| | | \__[6]
| | | | \__.
| | | | \__.
| | | \__[6]
| | | \__.
| | | \__.
| | \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[3]
| \__[4]
| | \__[5]
| | | \__[6]
| | | | \__.
| | | | \__.
| | | \__[6]
| | | \__.
| | | \__.
| | \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[4]
| \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[5]
| \__[6]
| | \__.
| | \__.
| \__[6]
| \__.
| \__.
\__[2]
\__[3]
| \__[4]
| | \__[5]
| | | \__[6]
| | | | \__.
| | | | \__.
| | | \__[6]
| | | \__.
| | | \__.
| | \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[4]
| \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[5]
| \__[6]
| | \__.
| | \__.
| \__[6]
| \__.
| \__.
\__[3]
\__[4]
| \__[5]
| | \__[6]
| | | \__.
| | | \__.
| | \__[6]
| | \__.
| | \__.
| \__[5]
| \__[6]
| | \__.
| | \__.
| \__[6]
| \__.
| \__.
\__[4]
\__[5]
| \__[6]
| | \__.
| | \__.
| \__[6]
| \__.
| \__.
\__[5]
\__[6]
| \__.
| \__.
\__[6]
\__.
\__.
- Author
- Jordi Esteve
- Language
- Catalan
- Official solutions
- C++
- User solutions
- C++