Tengo una duda, el ejercicio dice que no se puede visitar cada nodo más de una vez, si yo utilizo la función removerMaxABB hasta tener k nodos, eso se considera visitar más de una vez cada nodo? Y si es así como lo podría resolver? Muchas gracias
Algunos inconvenientes en tu propuesta.
¿Cómo sabés cuando quedan k nodos? Tendrías que por ejemplos contarlos al principio. Eso ya cuenta como una visita a cada nodo.
Para acceder al máximo (o al padre de él) tuviste que recorrer todos los hijos derechos desde la raíz. Para remover el siguiente vas a tener que volver a recorrer todos, excepto el último. Y así con cada uno. Finalmente tendrías que volver a recorrerlos para alcanzar el kesimo. O sea que hay nodos a los que vas a visitar varias veces.
Por último, estás modificando el árbol.
Sobre una posible solución. Esta no es la verdadera pero puede ser inicio para encontrarla. ¿Si hicieras una recorrida en orden del árbol (visitando cada nodo una sola vez) en qué paso de esa recorrida estarías visitando el kesimo?
disculpe pero a que se refiere con visita?
si yo recorro un arbol contando sus nodos, voy una vez a cada nodo, pero por recursion cuando desapilo en realidad paso 2 veces, solo que no termine de recorrer la funcion en su nodo porque salte al sig.
lo que quiero decir, es que por recorrer una vez se refiere a que la funcion se ejecute una sola vez en su totalidad en el nodo?
me esta siendo dificil pensar en una manera de sacar esta funcion sin agregarle otro parametro o pasar mas de 1 vez por cada nodo.
Podés definir una función auxiliar, posiblemente recursiva, con algún otro parámetro. Lo hicimos varias veces en el práctico acerca de recursión.
Supongamos que el nodo es el parámetro de la llamada a esa función. Al comienzo de la función se hacen algunas acciones que involucran al nodo. Luego tal vez se hace una llamada con el hijo izquierdo como parámtero. Al volver de la llamada se hacen más acciones. Después tal vez se hace una llama con el hijo derecho como parámetro. Y al volver se hacen más acciones.
Todas las acciones, las que se hacen al principio, a la vuelta de la primera de las llamadas a sus hijos, y al final son parte de la misma visita al nodo.
Visto de otra forma, que sea visitado solo una vez significa que solo una vez es el parámetro de una llamada.