¡Buenas!
Para borrar un nodo, tienes que seguir los siguientes pasos.
1- Si es un nodo hoja, lo eliminas y pones a NULL el puntero del padre que aputaba a este.
2- Si es un nodo con un solo hijo, el hijo sera el nodo de reemplazo.
3- Si es un nodo con dos hijos, el nodo de reemplazo puede ser o bien el menor de los nodos mayores que el que quieres borrar (el nodo mas a la izquierda del subarbol derecho), ya que este sera mayor que los de la izquierda pero menor que cualquier otro de la derecha, o sino puedes utilizar el mayor de los nodos menores (el nodo mas a la derecha en el subarbol izquierdo) ya que este sera mayor que todos los menores que el nodo que quieres sustituir, pero menor que los mayores.
3.1 - Si utilizas el menor de los nodos mayores, y este tiene un subarbol derecho (el subarbol de los valores mayores que el nodo de reemplazo), tendras que recorrerlo por la derecha hasta alcanzar el mayor valor. Al ser el mayor valor del arbol que tiene como raiz el nodo de reemplazo, este valor seguira siendo mayor que el valor que quieres reemplazar. Pero al partir del valor mas pequeño entre los valores mayores, sera menor que cualquier otro valor del subarbol derecho que sea mayor que el del nodo de reemplazo, por lo tanto tendras que colgar el subarbol derecho del nodo que quieres reemplazar como subarbol derecho del mayor nodo mayor que el menor de los nodos mayores. Como hemos cogido como referencia el menor de los nodos mayores, el subarbol izquierdo de dicho nodo sera nulo, y por lo tanto puedes colgar el subarbol izquierdo del nodo quieres eliminar del nodo izquierdo del menor de los nodos mayores que el que quieres eliminar. Ahora que ya tienes construido el arbol con raiz el nodo de reemplazo de forma correcta, ya puedes eliminar el nodo que querias eliminar, y el puntero del padre que señalaba al nodo que has eliminado deberas apuntarlo al nodo de reemplazo. Evidentemente, si quieres eliminar el nodo raiz, no tendras padre, pero esto no supone ningun problema, ya que el nodo de reemplazo, por como hemos hecho las operaciones de sustitucion del nodo que se quiere eliminar por el de reemplazo, cumple todas la propiedades para ser el nuevo nodo raiz.
3.2- Si eliges como nodo de reemplazo el mayor de los nodos menores, los pasos que tendras que seguir son los anteriores, cambiando mayor por menor y aplicando sentido comun.
Ya ves que explicado es cosa de
, pero en canto te pongas a traducirlo a codigo, lo veras mas claro y lo asimilaras mejor.
¡Saludos!