Dada la estructura:
Código
struct nodo { struct nodo *padre; struct nodo *izquierdo; struct nodo *derecho; char *valor; };
Ya puedo agregar y buscar nodos sin problema y al momento de eliminar nodos hay varios casos ya aborde la mayoria de ellos solo tengo un detalle con el ultimo.
Casos:
- El Nodo a eliminar no tiene hijos (Listo)
- El Nodo a eliminar solo tiene un hijo derecho o izquierdo (Listo)
- El Nodo a eliminar tiene ambos hijos (Pendiente)
El detalles es el decidir como reconectar los nodos cuando el noda eliminar tiene 2 hijos... (Si es un problema de algoritmo pero lo pongo aqui por que esta en C)
Si esos 2 hijos no tienen hijos no hay problema simplemente selecciono uno y lo pongo en el lugar del nodo eliminado. Pero el peor de los casos es cuando ambos nodos tienes 2 hijos cada uno mas o menos asi:
Código:
p
|
-> n
/ \
d i
/ \ / \
d i d i
La pregunta que tengo aqui seria la siguiente...
Tengo que hacer una funcion que reconecte y reorganize los nodos del arbol ¿Que recomendarian ustedes una funcion iterativa o una recursiva?
La otra solucion que tengo es manejar el nodo a eliminar como un arbol independiente desvincularlo del arbol principal y recorrer este nuevo subarbol de izquierda a derecha o viceversa y agregar cada nodo del subarbol al arbol principal, con excepcion de nodo a eliminar que seria la raiz del subarbol.
¿Que recomiendan ustedes?
La funcion que tengo es la siguiente:
Código
void eliminar_nodo(struct nodo *arbol,char *valor) { struct nodo *n; struct nodo *padre; struct nodo *derecho; struct nodo *izquierdo; if(debug_arbol) debug_arbol = 0; n = buscar_valor(arbol,valor); if(n) { if(n->derecho == NULL && n->izquierdo == NULL) { //No tiene hijos, hay que determinar si es el hijo derecho o izquierdo de su padre y desvincularlo padre = n->padre; if(padre->derecho == n) { padre->derecho = NULL; free_nodo(n); } else { padre->izquierdo = NULL; free_nodo(n); } } else { if(n->derecho != NULL && n->izquierdo != NULL) { // Tiene 2 Hijos padre = n->padre; // Detalle aqui..... } else { if(n->derecho != NULL) { //Solo tiene al hijo derecho derecho = n->derecho; padre = n->padre; if(padre->derecho == n) { //hay que determinar si es el hijo derecho o izquierdo de su padre y vincular dicho nodo, con el nodo derecho del n actual y liberar n despues de eso padre->derecho = derecho; free_nodo(n); } else { padre->izquierdo = derecho; free_nodo(n); } } else { //Solo tiene al hijo izquierdo izquierdo = n->izquierdo; padre = n->padre; if(padre->derecho == n) { //hay que determinar si es el hijo derecho o izquierdo de su padre y vincular dicho nodo, con el nodo izquierdo del n actual y liberar n despues de eso padre->derecho = izquierdo; free_nodo(n); } else { padre->izquierdo = izquierdo; free_nodo(n); } } } } } else { } }
Solucion en : http://foro.elhacker.net/programacion_cc/c_eliminando_nodo_de_arbol_binario-t453185.0.html;msg2072953#msg2072953