Decanonymo

bool Vacio(lista *r) { return r==NULL; } bool EsHoja(lista *r) { return !r->derecho && !r->izquierdo; } //declarar actual void Borrar(const int dat) { lista *padre = NULL; lista *nodo; int aux; actual = raiz; // Mientras sea posible que el valor esté en el árbol if(Eshoja(actual)) { raiz=NULL; return; } while(!Vacio(actual)) { if(dat == actual->dato) { // Si el valor está en el nodo actual if(EsHoja(actual)) { // Y si además es un nodo hoja: lo borramos if(padre) // Si tiene padre (no es el nodo raiz) // Anulamos el puntero que le hace referencia if(padre->derecho == actual) padre->derecho = NULL; else if(padre->izquierdo == actual) padre->izquierdo = NULL; delete actual; // Borrar el nodo actual = NULL; return; } else { // Si el valor está en el nodo actual, pero no es hoja // Buscar nodo padre = actual; // Buscar nodo más izquierdo de rama derecha if(actual->derecho) { nodo = actual->derecho; while(nodo->izquierdo) { padre = nodo; nodo = nodo->izquierdo; } } // O buscar nodo más derecho de rama izquierda else { nodo = actual->izquierdo; while(nodo->derecho) { padre = nodo; nodo = nodo->derecho; } } // Intercambiar valores de no a borrar u nodo encontrado // y continuar, cerrando el bucle. El nodo encontrado no tiene // por qué ser un nodo hoja, cerrando el bucle nos aseguramos // de que sólo se eliminan nodos hoja. aux = actual->dato; actual->dato = nodo->dato; nodo->dato = aux; actual = nodo; } } else { // Todavía no hemos encontrado el valor, seguir buscándolo padre = actual; if(dat > actual->dato) actual = actual->derecho; else if(dat < actual->dato) actual = actual->izquierdo; } } }