Entonces, antes de leer algunos conceptos básicos de informática.
- Un árbol binario es una estructura asignada dinámicamente (generalmente utilizada para el almacenamiento ordenado).
- Debido a su naturaleza, el recorrido de los árboles binarios suele ser recursivo;
Esto se debe a que el recorrido lineal (a través de un bucle) no es natural cuando hay dos vías de bucle.- Recursivo: Esto significa una función que se llama a sí misma.
- En lenguajes pasados de moda, la administración de memoria requiere administración manual de memoria.
- Manual: significa que tienes que hacerlo tú mismo.
- Cuando realiza la gestión manual de la memoria, debe solicitar al sistema subyacente que libere a cada miembro del árbol.
- Gratis: recupere la memoria en los poos globales para que pueda reutilizarse y no se quede sin memoria.
- Liberación: esto se hace llamando a la función
free()
y pasándole el puntero que desea recuperar. - Puntero: es como un palo virtual. Al final es la memoria. Cuando solicita memoria, se le proporciona un puntero (dispositivo virtual) que tiene memoria. Cuando haya terminado, devuelve el puntero (dispositivo virtual).
La solución recursiva:
freeTree(Node* node)
{
freeTree(node->left);
freeTree(node->right);
free(node);
}
El problema es que la recursión significa que repetidamente estás llamando a la misma función. Esto crece la pila. El crecimiento de la pila usa más memoria. La razón por la que está liberando el árbol es porque desea recuperar la memoria usando más memoria, es contraproducente (incluso si recupera ambos bits de memoria).
Por fin la pregunta:
Entonces, el problema se centra en convertir la versión recursiva anterior en una solución lineal (para que no tenga que usar memoria).
Dar el tipo de nodo
typedef struct Node Node;
struct Node
{
Node* left;
Node* right;
};
Escriba una función para liberar un árbol de estos nodos.
Restricciones:
- No se puede usar la recursividad (ni siquiera indirectamente)
No se puede asignar ningún espacio dinámico para el seguimiento.
Tenga en cuenta que hay una solución O (n)
Ganador:
- La mejor complejidad.
- Tie Break 1: primer envío
- Tie Break 2: menor cantidad de personajes.
fuente
C99, 94, O (n)
Editar: todo el mundo parece referirse al
struct Node
igual queNode
como si eltypedef
que la DE, así que lo hice también.Este es en realidad mi primer golf C. Muchos segfaults.
de todos modos, esto requiere C99 porque usa una declaración dentro de la primera declaración del bucle for.
ni siquiera usando
#define
!Este algoritmo funciona transformando el árbol de modo que el nodo superior no tenga un hijo izquierdo, y luego lo elimina y pasa a su hijo derecho.
por ejemplo, si comenzamos con el árbol
el algoritmo mutará los punteros para que el árbol sea
ahora podemos eliminar el nodo superior fácilmente.
fuente
C / C ++ / Objective-C 126 caracteres (incluye la nueva línea final requerida)
No se ejecuta en tiempo O (n). Pero el OP no lo requiere, así que aquí está mi solución O (n 2 ).
Algoritmo: caminar hacia una hoja desde la raíz. Liberarlo. Repita hasta que no haya hojas. Suelta la raíz.
Sin golf:
fuente
c ++ 99 O (n)
Los bucles aquí son excelentes para encadenar a lo largo de una lista pero no para subir y bajar jerarquías. user300 lo logró (estoy impresionado) pero el código es difícil de leer.
La solución es convertir el árbol en una lista.
El truco es hacerlo al mismo tiempo que elimina los nodos.
Versión de golf
Golf expandido
fuente
C, 150 bytes
Pruébalo en JDoodle
fuente