Arbre general. Modifica arbre amb el seu simètric. X57825

Donada la classe $Arbre$ que permet gestionar arbres generals d’enters usant memòria dinàmica implementats amb la tècnica de primer fill-següent germà, cal implementar el mètode

  void arbre_simetric();

que modifica l’arbre canviant-lo pel seu simètric (simetria especular: s’inverteix l’ordre dels fills de cada node).

Cal enviar a jutge.org la següent especificació de la classe $Arbre$ i la implementació del mètode dins del mateix fitxer. Al principi de cada mètode implementat, dins d’un comentari, cal indicar el cost temporal amb el raonament corresponent, incloent l’equació de la recurrència si fos necessari.

#include <cstdlib>
#include <string>
using namespace std;
typedef unsigned int nat;

template <typename T>
class Arbre {

public:
  // Construeix un Arbre format per un únic node que conté a x.
  Arbre(const T &x);

  // Tres grans.
  Arbre(const Arbre<T> &a);
  Arbre& operator=(const Arbre<T> &a);
  ~Arbre() throw();

  // Col·loca l'Arbre donat com a primer fill de l'arrel de l'arbre sobre el que s'aplica el mètode i l'arbre a queda invalidat; després de fer b.afegir\_fill(a), a no és un arbre vàlid.
  void afegir_fill(Arbre<T> &a);

  // Imprimeix la informació dels nodes en preordre, cada element en una nova línia i precedit per espais segons el nivell on està situat.
  void preordre() const;

  static const int ArbreInvalid = 400;

  void arbre_simetric();
  // Pre: cert
  // Post: Modifica l'arbre amb el simètric de l'arbre original

private:
  Arbre(): _arrel(NULL) {};
  struct node {
    T info;        // Informació del node
    node* primf;   // Punter al primer fill
    node* seggerm; // Punter al següent germà
  };
  node* _arrel; // Punter a l'arrel de l'arbre
  static node* copia_arbre(node* p);
  static void destrueix_arbre(node* p) throw();
  static void preordre(node *p, string pre);

  // Aquí va l'especificació dels mètodes privats addicionals
};

// Aquí va la implementació del mètode arbre\_simetric i privats addicionals

Per testejar la solució, jutge.org ja té implementats la resta de mètodes de la classe $Arbre$ i un programa principal que llegeix un arbre general d’enters i després crida els mètodes $arbre\_simetric$ i $preordre$.

Entrada

L’entrada consisteix en la descripció d’un arbre general d’enters (el seu recorregut en preordre, en el qual al valor de cada node li segueix el seu nombre de fills).

Sortida

El recorregut en preordre de l’arbre general resultant. Cada element en una nova línia i precedit per espais segons el nivell on està situat.

Observació

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

Al principi de cada mètode implementat i dins d’un comentari cal indicar el cost temporal amb el raonament corresponent, incloent l’equació de la recurrència si fos necessari.