Métodos de búsqueda (arboles)

TEMA 4.

Árboles
CONSIDERACIONES GENERALES.
Se detallan a continuación ejercicios de implementación de funcionalidades de árboles binarios con estructuras dinámicas (referencias). A la hora de abordar la resolución de un ejercicio sobre árboles binarios se recomienda tener en cuenta las siguientes consideraciones generales: Identificar si se trata de un caso de solo consulta, es decir, elalgoritmo a desarrollar no implica modificar la información inicialmente contenida en el árbol o modificación (inserción, borrado, eliminación). Tener en cuenta si el tratamiento permite finalización anticipada. Es decir, si es necesario recorrer toda la estructura (la finalización se produce cuando se cumpla por última vea la condición arbol==null) o acaba anticipadamente con el cumplimiento de unacondición (por ejemplo encontrar el valor de una clave). En este caso no deberán realizarse posteriores llamadas recursivas. Si el algoritmo implica tratamiento de hojas. Recuérdese que la condición que debe cumplirse para que un nodo sea hoja es (arbol.iz == null) && (arbol.de == null). Si el tratamiento implica consideración de nivel. Como ya se ha indicado se necesita un argumento (nivel), convalor inicial = 1 que se incrementa en cada llamada recursiva.
Cuando se trata de un árbol binario de búsqueda deberá tenerse en cuenta que no se considerará correcto el acceder a una clave mediante exploración exhaustiva del árbol o la no consideración del lugar que ocupan las claves superiores o inferiores a una dada.

ArbolesCalcularMenorDiferencia Enunciado. Dada la siguiente declaraciónde ARBOL BINARIO: class NodoArbol { int clave; NodoArbol iz; NodoArbol de; } public class Arbol { NodoArbol raiz; } SE PIDE: Codificar un método en Java que, recibiendo como parámetro un árbol binario perteneciente al tipo anterior, devuelva la menor diferencia, en valor absoluto, entre la clave contenida en el nodo raíz del árbol y otra clave contenida en algún otro nodo. OBSERVACIONES: No sepermite la utilización de ninguna estructura de datos auxiliar. Al final de la ejecución del método, el árbol deberá permanecer en la misma situación inicial. Si el árbol está vacío, el método deberá devolver como resultado el valor cero. Si el árbol posee un solo nodo, el método deberá devolver como resultado la clave contenida en ese nodo. Orientación. El ejercicio (tratamiento principal,buscarMenorDiferencia) consiste en realizar sendas llamadas a los subárboles izquierdo y derecho. En cada una de ellas (menorDiferencia) se obtiene la menor diferencia entre la raíz y la totalidad de nodos del subárbol correspondiente. El resultado será la menor de las dos. Dicho algoritmo verifica las situaciones excepcionales de árbol vacío, con un solo nodo o con un solo subárbol. El método recursivomenorDiferencia recorre un (sub)árbol y obtiene la menor diferencia entre sus claves y el valor de un argumento que es la clave del árbol inicial. El recorrido puede realizarse en cualquier orden y no existe posibilidad de terminación anticipada. Cada vez que se alcanza la condición de terminación (arbol == null) se inicializa el método con la diferencia entre la clave y la raíz. Para ello esnecesario pasar como argumento la clave del nodo desde el que se hace la llamada (argumento entero ant)1.

Obsérvese que aunque este cálculo se realiza dos veces no implica múltiple recorrido. Otra posibilidad que no utilizaría este argumento sería inicializar con la constante Integer.MAX_VALUE.

1

Código.
static int menorDiferencia (NodoArbol arbol, int raiz, int ant) { int resul, resulIz; if(arbol != null) { resulIz = menorDiferencia (arbol.iz, raiz, arbol.clave); if (Math.abs (arbol.clave - raiz) < resulIz) resulIz = Math.abs (arbol.clave - raiz); resul = menorDiferencia (arbol.de, raiz, arbol.clave); if (resulIz < resul) resul = resulIz; } else resul = Math.abs (ant - raiz); return resul; } static int buscarMenorDiferencia (NodoArbol arbol) { int resul = 0, resulIz; if (arbol !=...