Estoy aprendiendo arboles binarios de búsqueda (ABB). Esta es la función que no entiendo:
nodo *crearNodo(int valor){
nodo *nuevo_nodo = new nodo();
nuevo_nodo->dato = valor;
nuevo_nodo->derecha = NULL;
nuevo_nodo->izquierda = NULL;
return nuevo_nodo;
}
Siendo más específico, lo que quiero es que me traten de explicar es ¿Cómo funciona esa función y además por qué esa función es de tipo puntero?. Gracias a quien me haya quitado mi duda. PD: esto es de C++.
¿Cómo funciona esa función y además por qué esa función es de tipo puntero?
La función no es de tipo puntero, la función es de tipo nodo *(int).
El tipo nodo *(int) es una función que devuelve un puntero a nodo (nodo *) y recibe un entero (int), todas estas funciones comparten el mismo tipo:
nodo *crearNodo(int valor);
nodo *patatas_Fritas_con_Ketchup_y_mayonesa(int valor);
nodo *f(int valor);
nodo *cn(int valor);
Respecto a cómo funciona, estos son los detalles:
nodo *nuevo_nodo = new nodo(); crea un objeto nodo en memoria dinámica (mediante el operador new). Para crear dicho objeto se ha usado su constructor por defecto (es decir: el constructor que no recibe parámetros), la memoria que ocupa ese nuevo objeto está apuntada por el puntero nuevo_nodo.nuevo_nodo->dato = valor; se asignan datos al sub-objeto dato del objeto nodo (en notación C++ sería nodo::dato), dado que se asigna a través de un puntero (nuevo_nodo) es necesario usar el operador flecha (->)1.nuevo_nodo->derecha = NULL; se asignan datos al sub-objeto derecha del objeto nodo (en notación C++ sería nodo::derecha), dado que se asigna a través de un puntero (nuevo_nodo) es necesario usar el operador flecha (->)1, el sub-objeto nodo::derecha seguramente será otro puntero a nodo (nodo *) y se le asigna el resultado de desplegar la macro NULL para indicar que ese puntero no apunta a nada.nuevo_nodo->izquierda = NULL; se asignan datos al sub-objeto izquierda del objeto nodo (en notación C++ sería nodo::izquierda), dado que se asigna a través de un puntero (nuevo_nodo) es necesario usar el operador flecha (->)1, el sub-objeto nodo::izquierda seguramente será otro puntero a nodo (nodo *) y se le asigna el resultado de desplegar la macro NULL para indicar que ese puntero no apunta a nada.return nuevo_nodo; envía fuera de la función la dirección de memoria dinámica almacenada en nuevo_nodo que ahora está apuntando a un objeto nodo cuyos sub-objetos nodo::dato, nodo::izquierda y nodo::derecha han sido inicializadas.Ahora, vamos a la parte seria:
PD: esto es de C++.
Esto sería C++ si estuviéramos en el año 19852, hace décadas que un código así se considera obsoleto, propenso a errores, innecesariamente largo y repleto de malas prácticas.
Para empezar, está enérgicamente desaconsejado devolver punteros desde funciones, más aún si este puntero apunta a memoria dinámica, supón los siguientes usos de la función crearNodo:
crearNodo(0);
crearNodo(1) = NULL;
if (es_martes())
{
nodo *trece = crearNodo(13);
}
En el primer caso el puntero devuelto se pierde, generando una fuga de memoria. En el segundo caso el puntero devuelto es sobrescrito por otro valor (dando lugar a otra fuga de memoria) para después ser descartado. En el tercer caso el puntero devuelto se guarda en una variable, pero no se borra el puntero antes de que la variable salga de ámbito, generando otra fuga de memoria más.
En C++11 se añadieron al lenguaje los atributos, y en C++17 se añadió el atributo [[nodiscard]], que permite declarar objetos y retornos de función como datos que no deben descartarse:
[[nodiscard]] nodo *crearNodo(int valor);
Cambiando la función para usar atributos, evitaremos el primer caso de fuga de memoria, pero no evitaremos el segundo o tercero, es imposible evitar que nuestro código sea usado por idiotas3 pero podemos esforzarnos para que nuestro código sea inocuo incluso cuando se usa mal. Si cambiamos el puntero en crudo por un puntero inteligente:
std::unique_ptr<nodo> crearNodo(int valor);
Evitaremos las fugas de memoria incluso en el segundo y tercer caso.
Suponiendo que el objeto nodo tenga este aspecto:
struct nodo {
int valor;
nodo *izquierda, *derecha;
};
Podemos hacer que la creación e inicialización del nodo sea en una sola línea:
nodo *nuevo_nodo = new nodo{valor, NULL, NULL};
return nuevo_nodo;
Si inicializamos los sub-objetos donde son declarados, el código puede acortarse más:
struct nodo {
int valor;
nodo *izquierda = NULL, *derecha = NULL;
};
nodo *crearNodo(int valor){
nodo *nuevo_nodo = new nodo{valor};
return nuevo_nodo;
}
Es más, ni siquiera necesitamos la variable temporal:
nodo *crearNodo(int valor){
return new nodo{valor};
}
Llegados a este punto, me pregunto incluso ¿para qué queremos la función crearNodo?, si usamos un puntero inteligente ya tenemos una función para crear un nodo:
std::unique_ptr<nodo> n = std::make_unique<nodo>(valor);
NULL, usa nullptr.La macro NULL se traduce (dependiendo de implementación) en 0 o en (void*)0, esto se debe a que los enteros son implícitamente convertibles a punteros:
int *i = 0; // 0 es un entero ¡no un puntero!
void f(int *puntero){}
f(0); // 0 es un entero ¡no un puntero!
Esto puede provocar problemas:
void f(int *puntero){}
void f(int valor){}
f(NULL); // Llamada ambigua ¿llamas a la versión puntero o a la versión entero?
Para evitar esto se creó el literal de puntero nulo nullptr:
void f(int *puntero){}
void f(int valor){}
f(0); // Llama a la versión entero
f(nullptr); // Llama a la versión puntero
Tu nodo debería tener este aspecto:
struct nodo {
int valor;
nodo *izquierda = nullptr, *derecha = nullptr;
};
Y la función crearNodo no debería siquiera existir, usa punteros inteligentes y llama a std::make_unique.
1Lee esta respuesta para saber más del operador flecha.
2C++ nació oficialmente en 1983.
3Programar hoy día es una carrera entre los ingenieros de software esforzándose por crear mayores y mejores programas a prueba de idiotas, y el universo intentando crear mayores y mejores idiotas. Por el momento, el universo va ganando —Douglas Adams—
