0

Se me pide que elimine todos los nodos de un árbol binario de búsqueda, liberando su memoria, y con O(n), siendo n la cantidad de elementos del árbol. Mi problema viene con esta última parte, ¿para llegar a ese orden tendría que usar alguna estructura iterativa (for, while o repeat) no? pero veo más sencillo hacerlo utilizando recursión con el recorrido postOrder.

struct nodoABB {
  int dato;
  nodoABB *izq, *der;
};
typedef struct nodoABB * ABB;

void deleteTree(ABB a) {
  if (a!= NULL) {
    deleteTree(a->izq);
    deleteTree(a->der);
    delete a;
  }
}
4
  • es correcto tu argumento pero no entiendo cual es el problema? o que esperas...
    – user46896
    Commented el 5 oct. 2022 a las 14:15
  • @ArcanisGK507 el problema es que el tiempo de ejecución del algoritmo debe ser O(n), y no sé si ese algoritmo cumple con eso. Commented el 5 oct. 2022 a las 14:32
  • y como se evalua eso??
    – user46896
    Commented el 5 oct. 2022 a las 14:36
  • @ArcanisGK507 se llama notación Big O. Puedes ahondar sobre el tema en YouTube. De forma simple, se mide con los ciclos. La complejidad de un for es O(n). La de dos for anidados O(n²). La de 3, O(n³) y así. Entre paréntesis va una función matemática. Si la graficas te puedes hacer una idea de que el crecimiento de la función es mayor que el de n.
    – Mateo
    Commented el 5 oct. 2022 a las 16:52

1 respuesta 1

0

Usa el destructor, deja que el compilador haga su magia:

struct nodoABB {
    ~nodoABB() {
        delete izq;
        delete der;
    }

    int dato;
    nodoABB *izq{nullptr}, *der{nullptr};
};

El destructor destruirá el árbol recursivamente, si el nodo a borrar está vacío (contiene nullptr) la operación delete no hará nada.

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge you have read our privacy policy.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.