Buenas,
Implementé la primer idea que tuve para este problema y la función que hace lo que se pide, pero me quedó un código bastante entreverado, y salvo ponerle bastantes comentarios para que quede claro lo que hace cada parte no logré mejorar el código para nada. Los cambios que intenté después de eso no funcionaron.
Quería pedir ayuda, ya sea para mejorar el código original o para arreglar el segundo intento.
Este es el código que funciona:
void insertarPalabra(Lista palabra, AG &t) { AG anterior = t; if (anterior->pH != NULL) { AG ptr = anterior->pH; //Recorro los hijos de t buscando la primer letra de palabra //o la primera que le sigue en el abecedario while (ptr != NULL && ptr->letra < palabra->letra) { anterior = ptr; ptr = ptr->sH; } //si encontre la letra, busco la siguiente entre los hijos de ptr if (ptr != NULL && ptr->letra == palabra->letra) { insertarPalabra(palabra->sig, ptr); return; } //Creo nodo para la primer letra e inserto justo antes de ptr AG nuevoNodo = crearNodo(palabra->letra); nuevoNodo->sH = ptr; //Busco quien apunta a ptr y hago que apunte a nuevoNodo //anterior queda apuntando al nodo recien insertado if (anterior->sH == ptr) { anterior->sH = nuevoNodo; anterior = anterior->sH; } else if (anterior->pH == ptr) { anterior->pH = nuevoNodo; anterior = anterior->pH; } palabra = palabra->sig; } // if //Inserto el resto de la palabra (toda la palabra si el arbol era vacio) while (palabra != NULL) { anterior->pH = crearNodo(palabra->letra); anterior = anterior->pH; palabra = palabra->sig; } //inserto un '$' al final de cada palabra anterior->pH = crearNodo('$'); }
Lo que me parece entreverado es estar llevando registro del nodo anterior al nodo con el que vengo trabajando (ptr), y especialmente la parte donde tengo que buscar si el que apuntaba a ptr es su padre o su hermano a la izquierda para que apunte al nuevo nodo.
Esto es lo que intenté para que sea más claro, pero no funciona:
void insertarPalabra(Lista palabra, AG &t) { insertar(palabra, t->pH); } void insertar(Lista palabra, AG &t) { AG ptr = t; if (ptr != NULL) { //Recorro el primer nivel buscando la primer letra de palabra //o la primera que le sigue en el abecedario if (ptr != NULL && ptr->letra < palabra->letra) { insertar(palabra, ptr->sH); return; } //si encontre la letra, busco la siguiente entre los hijos if (ptr != NULL && ptr->letra == palabra->letra) { insertar(palabra->sig, ptr); return; } //Creo nodo para la primer letra e inserto justo antes de ptr AG nuevoNodo = crearNodo(palabra->letra); nuevoNodo->sH = ptr; ptr = nuevoNodo; palabra = palabra->sig; } // if //Inserto el resto de la palabra (toda la palabra si el arbol era vacio) while (palabra != NULL) { ptr = crearNodo(palabra->letra); ptr = ptr->pH; palabra = palabra->sig; } //inserto un '$' al final de cada palabra ptr = crearNodo('$'); }
En este caso con la función insertarPalabra(), que lo único que hace es llamar a insertar() con t->pH, lo que busco es sacarme de arriba el nodo dummy.
Mas allá de otros errores que probablemente tenga, el problema principal es que los nodos que inserto no quedan colgados del árbol t, t siempre queda vacío, es decir que ese error no está dentro del if (ptr != NULL). Probablemente esté en el while del final.
Este ejercicio me pareció muy interesante. Agradezco una mano para mejorar el código.