parcial mayo 2018 ej 2b

parcial mayo 2018 ej 2b

de Celia Misa Knuth -
Número de respuestas: 1

hola quería saber si este código esta bien, me cuesta ver como se va enganchando.

  lista menores (ABB t, int K) {

   lista res;

   if (t==NULL) 

     res=NULL;

   else {

     lista auxizq= menores (t->izq,k);

     if (t->dato>=k)

         res=auxizq;

     else {

         lista auxder= menores (t->der,k);

     lista nodoelem = new nodo;

nodoelem->elem= t->dato;

nodoelem->sig= auxizq;

concat(auxder, nodoelem);

res=auxder;

 

}

     }

return res;

}

 

En respuesta a Celia Misa Knuth

Re: parcial mayo 2018 ej 2b

de Fernando Fernandez -
Hola.
Me parece que está bien.

Supongo que lo que decís que te cuesta ver es lo que está dentro de la rama else.
Si es así, veamos que al llegar al concat hay dos listas:
  • auxder es la lista de todos los elementos del subárbol derecho que cumplen la condición y está ordenada de manera decreciente.
  • nodoelem es la lista cuyo primer elemento es la raíz del árbol y el resto son todos los elementos del subárbol izquierdo, porque así se construye al asignar lRaiz->sig. Esta lista también está ordenada de manera decreciente, porque  así lo estaba auxizq y el elemento de la raíz es mayor que todos los de su subárbol izquierdo, por definición de ABB.
Cada elemento del árbol que cumple la condición está en una de las dos listas y cada elemento de lRaiz es menor que cada elemento de auxder, otra vez por definición de ABB.

Entonces el resultado debe ser la concatenación de auxder y lRaiz, en ese orden. Y eso es lo que hace concat, que asumimos que está bien implementada. Hay que tener en cuenta que el primer parámetro de esta función está pasado por referencia.

¿Esto aclara algo?