Algoritmos y Estructuras de Datos (VJ1215)

vector<int> Conjunto::obtenerOrdenados() const {
   vector<int> v(laTalla);
   int i = 0;
   obtenerOrdenados(raiz, v, i);
   return v;
}

void Conjunto::obtenerOrdenados(Nodo * n, vector<int> & v, int & i) const {
   if (n != nullptr) {
      obtenerOrdenados(n->izquierdo, v, i);
      v[i++] = n->dato;
      obtenerOrdenados(n->derecho, v, i);
   }
}
      

Presta atención a estos aspectos de la solución anterior:

1. No utilizamos push_back para insertar datos en el vector, que lo que haría internamente es duplicar la capacidad del vector cada vez que se llena. Para evitar eso, como conocemos la talla del conjunto, le damos ese dato al constructor del vector.

2. El vector se crea en el primero de esos dos métodos y se devuelve con return una sola vez. El segundo método no lo devuelve con return, lo que hace es actualizar el vector y la posición que le pasamos por referencia y que todas las llamadas recursivas comparten.

El coste temporal de este algoritmo es O(n) debido a que se hacen O(n) llamadas recursivas y el coste propio de cada llamada es O(1).

Su coste espacial es O(n) debido a que tenemos un árbol de talla n y un vector de talla n, a lo que se suma el coste de la pila de llamadas recursivas que en el peor caso, si tuviéramos un árbol de altura n, también sería O(n).