Foro de elhacker.net

Hola a todos!, estoy estudiando programación, y tengo un ejercicio sobre arboles binarios. El ejercicio me pide encontrar el segundo mayor y el segundo menor de un árbol binario. Tengo el código de como encontrar el mayor, aquí les dejo, si alguien puede ayudarme se le agradecería mucho :)

int buscarmenor(ABB arbol)
{
 int menor;
 while(arbol->izq!=NULL)
      arbol=arbol->izq;
 menor=arbol->valor;
 return menor;
}

int buscarmayor(ABB arbol)
{
 int mayor;
 while(arbol->der!=NULL)
      arbol=arbol->der;
 mayor=arbol->valor;
 return mayor;
}

Sabes cómo funcionan los árboles binarios?

Si la respuesta es sí, sabes que cada nodo tiene un valor... los nodos de la izquierda tienen un valor inferior y los de la derecha un valor mayor.

Con esta idea fácilmente puedes adivinar que, tomando como referencia los 3 últimos nodos de la izquierda, puedes tener 3 escenarios diferentes:

     A                 A                 A
    /                  / \                  \
   B                 B  C                 C

En el 1er caso, tenemos que el nodo A tiene un valor X y, por fuerza, el nodo B tiene un valor necesariamente menor, luego en este caso el valor buscado sería A.

En el 2º caso, A tiene un valor X, B es menor y C es el mayor de los 3... el valor buscado es el del nodo A.

En el 3er caso, A tiene un valor inferior al B... el valor buscado es el del nodo B.

Con esta información, una opción sería diseñar un algoritmo que recorra la rama izquierda de cada nodo, empezando por el raiz. Una vez localizado el último grupo de nodos... mirar a ver si es del tipo 1, 2 o 3 y devolver el resultado correspondiente.

Otra opción podría ser recorrer todo el árbol y almacenar los dos números más pequeños que te encuentres... con eso tendrías el número más pequeño y, el buscado, el segundo más pequeño.

Para el caso del segundo mayor la lógica a implementar sería similar. Ya es gusto del programador ( es decir, tu decisión ), elegir la opción que crea más adecuada.

Un saludo.