Arbre binari. Crea arbre binari complert de n nivells X75469


Statement
 

pdf   zip   main.cc

html

Donada la classe Abin 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 n 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 Abin 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 n, 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 addicionals



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 natural i desprès crida el mètode Abin(nat n).

Entrada

L’entrada consisteix en un natural.

Sortida

El contingut de l’arbre binari desprès de cridar el mètode Abin(nat n).

Observació

Només cal enviar la classe requerida, la implementació del mètode Abin (nat n) i el seu cost en funció de n, 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.

Public test cases

  • 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]
                     \__.
                     \__.
    • Information
    Author
    Jordi Esteve
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++