3

tengo una clase que representa lo que es un Arbol Binario de Búsqueda y tengo una operación que no me deja compilar, que es la del cardinal, que devuelve la cantidad de elementos de un arbol, pero no quiero tener que pasar por valor al puntero como parámetro muestro la estructura de mi clase:

template <class T>
class Conjunto
{
    public:

        // Constructor. Genera un conjunto vacío.
        Conjunto();

        // Destructor. Debe dejar limpia la memoria.
        ~Conjunto();

        // Inserta un elemento en el conjunto. Si este ya existe,
        // el conjunto no se modifica.
        void insertar(const T&);

        // Decide si un elemento pertenece al conjunto o no.
        bool pertenece(const T&) const;

        // Borra un elemento del conjunto. Si este no existe,
        // el conjunto no se modifica.
        void remover(const T&);

        // Siguiente elemento al recibido por párametro, en orden.
        const T& siguiente(const T& elem);

        // Devuelve el mínimo elemento del conjunto según <.
        const T& minimo() const;

        // Devuelve el máximo elemento del conjunto según <.
        const T& maximo() const;

        // Devuelve la cantidad de elementos que tiene el conjunto.
        unsigned int cardinal() const;

        // Muestra el conjunto.
        void mostrar(std::ostream& o) const;

    private:

        struct Nodo
        {
            // El constructor, toma el elemento al que representa el nodo.
            Nodo(const T& v);
            // El elemento al que representa el nodo.
            T valor;
            // Puntero a la raíz del subárbol izquierdo.
            Nodo* izq;
            // Puntero a la raíz del subárbol derecho.
            Nodo* der; 
        };

        bool buscarDesde(const Nodo* nd, const T& clave) const;
        void destruir(Nodo* raiz);
        void insertarAux(Nodo* nodoIn,Nodo* &raiz);
        void removerDesde(Nodo* &padre, Nodo* &nd, const T& clave ); //remover desde
        //Pre: nd pertenece a  ABB, tengo que recibir por referencia para no crear copias
        void removerAux(Nodo* &padre, Nodo* &nd);
        //Pre: nd != nullptr
        const T& minimoDesde(const Nodo* nd) const;
        //Pre: nd != nullptr
        const T& maximoDesde(const Nodo* nd) const;
        unsigned int contarDesde(const Nodo* &nd) const ;
        const Nodo* buscarNodoDesde(const Nodo* nd, const T& clave) const;
        void mostrarDesde( Nodo* nd, std::ostream& o) const;
        T& minimoDesdeRemove(Nodo* nd);


        // Puntero a la raíz de nuestro árbol.
        Nodo* _raiz;



};

La operación que quiero arreglar

template <class T>
unsigned int Conjunto<T>::cardinal() const {
    assert(true);

    return contarDesde(_raiz);
}


template<class T>
unsigned int Conjunto<T>::contarDesde(const Conjunto::Nodo* &nd) const{
    unsigned int cont = 0;
    if(nd == nullptr){
        return cont; //retorno hasta donde llegue de cada rama.
    }
    else{
        cont = 1 + contarDesde(nd->izq) + contarDesde(nd->der);

    }

    return cont;
}

El error de compilación:

error: cannot bind non-const lvalue reference of type ‘const Conjunto<int>::Nodo*&’ to an rvalue of type ‘const Conjunto<int>::Nodo*’
  108 |     return contarDesde(_raiz);

La solución tiene que ser una buena práctica, eficiente al usar referencias como parámetro y que no pueda modificar los valores de mi estructura de Arbol con operaciones recursivas. Como tendría que ser la aridad de contarDesde(parametro)?

2 respuestas 2

1

La solución tiene que ser una buena práctica, eficiente al usar referencias como parámetro y que no pueda modificar los valores de mi estructura de Arbol con operaciones recursivas

Si quieres que sea eficiente no uses referencias sobre punteros. Esa estructura es equivalente a crear un puntero doble, es decir, para acceder a los valores necesitarás dos indirecciones en vez de únicamente una.

Una referencia a un puntero solo es necesaria cuando necesitas que dicho puntero referencie una posición de memoria distinta, que no es el caso.

La función contarDesde no debería, por tanto, usar referencias:

template<class T>
unsigned int Conjunto<T>::contarDesde(const Conjunto::Nodo* nd) const{
    unsigned int cont = 0;
    if(nd == nullptr){
        return cont; //retorno hasta donde llegue de cada rama.
    }
    else{
        cont = 1 + contarDesde(nd->izq) + contarDesde(nd->der);

    }

    return cont;
}

Por otro lado no hay nada malo en pasarle el nodo raiz a la función, es una forma perfectamente lógica de operar.

Ahora bien, si no quieres pasarle el nodo raiz lo que puedes hacer es que modificar contarDesde para que al recibir nullptr empiece a iterar desde el nodo raiz

Ya que hablamos también de buenas prácticas, podemos aprovechar para modificar un poco más la función. Por ejemplo, cont no se usa si nd == nullptr, por lo que o bien retrasas la declaración de ésta variable o bien haces que el if también modifique cont (y de paso te quitas ese segundo return de la función, que no aporta nada

template<class T>
unsigned int Conjunto<T>::contarDesde(const Conjunto::Nodo* nd) const{
    unsigned int cont = 0;
    if(nd == nullptr)
    {
        cont = contarDesde(_raiz);
    }
    else
    {
        cont++;
        if (nd->izq != nullptr)
            cont += contarDesde(nd->izq);
        if (nd->der != nullptr)
            cont += contarDesde(nd->der);
    }

    return cont;
}

Ahora bien, te digo lo mismo que he repetido infinidad de veces. No intentes buscar la máxima eficiencia en el código, es algo que no vas a encontrar. El mejor algoritmo para listas pequeñas no funcionará igual con listas muy muy grandes, no existen los sistemas perfectos.

1

Los punteros pueden ser constantes por la izquierda o por la derecha1:

struct Objeto
{
    void f() {}
    void fc() const {}
} o;

Objeto const *co = &o; // constante por la izquierda
Objeto *const oc = &o; // constante por la derecha

Cuando es constante por la izquierda, lo que es constante es el objeto apuntado, por eso este código falla:

co->f(); // error, f no es constante.

El objeto es constante y en consecuencia no puede llamar a funciones no constantes. Cuando es constante por la derecha, lo que es constante es el puntero, por eso este código falla:

Objeto o2;
oc = &o2; // error, el puntero es constante ergo: no puede cambiar su valor.

El puntero es constante y en consecuencia no puede cambiar la dirección a la que apunta.

El error que recibes es porque el compilador confunde categorías de valor (lado izquierdo o lvalue con lado derecho rvalue) porque intentas pasar un puntero que es constante por el lado derecho (_raiz es constante por lado derecho porque forma parte de this en un contexto constante) a un puntero que es constante por el lado izquierdo (const Conjunto::Nodo* &nd).

Para solucionarlo sólo tienes que decir que el puntero es constante por el lado derecho (o por ambos lados):

template <class T>
class Conjunto
{
    ...
    unsigned int contarDesde(Nodo *const &nd) const ;
    //                             ^^^^^ <--- constante en el lado derecho
    ...
};

1O ambos lados, pero ahora no viene al caso.

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.