1

no logro entender la estructura que os expongo a continuación sobre un árbol binario.

Fichero de cabecera Abin

template <typename T> class Abin {
    struct celda; //declaración adelantada privada
public:
    typedef celda* nodo;
    static const nodo NODO_NULO;

    Abin();//constructor
    void crearRaizB(const T& e);
    void insertarHijoIzqdoB(nodo n, const T& e);
    void insertarHijoDrchoB(nodo n, const T& e);
    void eliminarHijoIzqdoB(nodo n);
    void eliminarHijoDrchoB(nodo n);
    void eliminarRaizB();
    ~Abin(); //destructor
    bool arbolVacioB() const;
    T elemento(nodo n) const; //acceso a elto, lectura
    T& elemento(nodo n); //acceso a elto, lectura/escritura
    nodo raizB() const;
    nodo padreB(nodo n) const;
    nodo hijoIzqdoB(nodo n) const;
    nodo hijoDrchoB(nodo n) const;
    Abin(const Abin<T>& a); // ctor. de copia
    Abin<T>& operator =(const Abin<T>& a); //asignación de árboles
private:
    struct celda{
        T elto;
        nodo padre, hizq, hder;
        celda(const T& e, nodo p = NODO_NULO): elto(e), padre(p), hizq(NODO_NULO), hder(NODO_NULO) {}
    };
    nodo r; //nodo raíz del árbol
    void destruirNodos(nodo& n);
    nodo copiar(nodo n);
};

Entiendo que tenemos una estructura celda con cuatro elementos:

  • elto: elemento (información de tipo char, int...) que va a contener nuestro nodo.
  • nodos padre, hizq, hder: almacena un entero en cada campo que corresponde a la posición en la que se encuentra el elemento.

Mis dudas:

typedef celda* nodo;

¿Qué es exactamente esa línea? ¿En qué línea está definido el tipo nodo?

Si tuvierais algún enlace para lograr entenderlo mejor os lo agradezco porque con todo esto de golpe, la teoría la sé, pero en la práctica me pierdo.

2
  • Esa línea es un alias de tipo, te dice que bajo la etiqueta nodo tendrás un puntero a celda. Commented el 11 mar. 2018 a las 19:38
  • Amigo cambia la pregunta que a mi parecer la tienes mal, estas preguntando sobre typedef, que que pon eso, no pongas diseñar un árbol binario porque tu duda se trata es sobre los alias.
    – Mario
    Commented el 11 mar. 2018 a las 20:16

4 respuestas 4

4

Entiendo que tenemos una estructura celda con cuatro elementos:

Efectivamente celda es una estructura con cuatro variables miembro, donde elto se espacializa en el tipo a usar por la plantilla (int, char, etc).

Sin embargo padre, hizq y hder no son enteros sino punteros.

La clase Albin está creando un mapa de nodos (cada nodo es de tipo celda), donde cada uno de estos nodos conoce tanto a su padre como a sus nodos izquierdo y derecho. Este diseño te permite moverte de forma bidireccional dentro del árbol (de arriba abajo y viceversa).

¿Qué es exactamente esa línea?

Esa línea define un alias y dicho alias actua exactamente como su nombre indica. Un alias no es un tipo nuevo sino una referencia a un tipo dado. En este caso se está creando un alias llamado nodo que sustituye al tipo celda*.

Por si te lo preguntas, los alias sirven para mejorar la legibilidad del código... cuando se usan con criterio. Un ejemplo muy claro se puede encontrar al tratar con punteros a función:

void func(int,char)
{ std::cout << "func(int,char);\n"; }

void ejecutaFuncion( void (*funcPtr)(int,char) )
{
  funcPtr(1,'c');
}

int main()
{
  ejecutaFuncion(func);
}

La sintaxis va quedando más y más fea cuanto más compleja es la llamada a func. Este código puede quedar mucho más limpio si se usa un alias:

typedef FuncPtr void(*)(int,char);

void ejecutaFuncion( FuncPtr funcPtr )
{
  funcPtr(1,'c');
}

De esta forma por muy compleja que sea la definición del puntero a función, la declaración de la función ejecutaFuncion no solo permanece constante sino que además es facil de entender.

¿En qué línea está definido el tipo nodo?

Ya hemos visto que nodo es un alias y que lo estás definiendo en esa misma línea.

2
typedef celda* nodo;

¿Qué es exactamente esa línea? ¿En qué línea está definido el tipo nodo?

Ese es el menor problema del código que has compartido, pero empezaremos por resolver esa duda. Esa línea es una declaración typedef que según el estándar de C++ (traducción y resaltados míos):

10.1.3 El especificador typedef

1 [...] Un nombre declarado con el especificador typedef es un nombre-typedef. Dentro del ámbito de su declaración un nombre-typedef es sintácticamente equivalente a una palabra clave y nombra al tipo asociado con el identificador de la manera que se describe en la Cláusula 11. Un nombre-typedef es entonces, un sinónimo de otro tipo. Un nombre-typedef no introduce un nuevo tipo como lo hace la declaración de una clase o un enumerado. [Ejemplo: tras

 typedef int MILLAS, *KLICKSP;

las construcciones

MILLAS distancia;
extern KLICKSP metricp;

Son todas declaraciones correctas; el tipo de distancia es int y el de metricp es “puntero a int”. — fin del ejemplo ]

Así pues tu línea typedef celda* nodo; está creando un sinónimo del tipo celda* con nombre nodo, en otras palabras: para el compilador nodo y puntero a celda (celda*) serán exactamente lo mismo.

Este tipo de declaración de sinónimos se considera confusa porque no sigue el formato de otros constructos de C++, así que en el estándar C++11 se añadió una forma diferente de definir sinónimos:

using nodo = celda*;

La instrucción anterior es equivalente a tu typedef y es más fácil de entender por seguir el formato de asignación habitual al que el lenguaje nos tiene acostumbrados, en cambio no permite hacer definiciones múltiples (como vemos en el ejemplo de typedef del estándar), pero en contrapartida permite hacer sinónimos plantilla.


No hay encapsulamiento.

El código que compartes denota un diseño terrible que ignora por completo los principios de encapsulamiento al dar detalles de la implementación interna mediante la interfaz pública. Por otro lado, no contiene ni un sólo método de búsqueda mediante tipo almacenado (T) si no que en todos los casos espera recibir un nodo para hacer cualquier operación; en mi opinión, deberías repasar toda la implementación y ver otros ejemplos de árboles binarios.

1

El tipo nodo no está definido como tal, lo que tienes es un puntero a la estructura celda.

Es decir, nodo es lo mismo que celda, pero le asigna la palabra/alias nodo que es el que utiliza en el resto del código para que al utilizarlo en el árbol sea mas fácil de entender. Por ejemplo, es mas visible poner nodo padre que si pusiese celda padre.

1

Typedef

Un alias de tipo es un nombre diferente por el cual se puede identificar un tipo. En C++, cualquier tipo válido puede ser alias para que pueda ser referido con un identificador diferente.

En C++ se existen dos maneras de definir un alias, la primera que es heredado de C, es con typedef:

typedef tipo_dato_existente alias_de_tipo_dato

y la otra manera que ya es de C++,

using alias_de_tipo_dato = tipo_dato_existente.

Que beneficios tiene el utilizar un alias, hay varias, una de tantas es que separar tus tipos de dato de la arquitectura del tu pc y funcionamiento del Sistema Operativo, por ejemplo el tipo de dato int es un tipo de dato de 32 bits en procesadores de 32 bits, pero en un procesador de 64bits, este suele tener 32 o 64bits y esto puede afectar el funcionamiento de tu programa, si este es multiplataforma, así que se puede crear un alias para el tipo de dato que se necesita dependiendo del sistema, sin necesidad de cambiar todo tu programa, simplemente cambias el tipo de dato que apunta el alias y listo.

esa línea lo que hace es define un alias llamado nodo el cual es un puntero a una estructura llamada celda.

1
  • 1
    Lo que dices de "y la otra manera que ya es C++" no es totalmente correcto. using únicamente está disponible a partir de C++11. En C++98 (o incluso C++03) no puedes usar using pese a programar en C++...
    – eferion
    Commented el 12 mar. 2018 a las 8:38

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.