Si se desea implementar un árbol binario de búsqueda utilizando una matriz, se pueden definir las siguientes clases NodoArbol y Arbol:
Utilizando las clases anteriores, utilizaríamos la siguiente matriz para guardar el contenido del árbol de la figura 1.12.:
Figura 1.12. Ejemplo de árbol binario.
La clave de la raíz del árbol (10) aparece en la posición 0 de la matriz, en el campo clave. Su hijo izquierdo (el 5), está en la posición 3 de la matriz (dado que matriz [0].izq =3), mientras que el hijo derecho (15) estará en la posición 2. Cuando un elemento es una hoja (por ejemplo, el 15), su hijo izquierdo y su hijo derecho tendrán como valor NULL (es decir, -1).
4.1.1. Recorridos en profundidad.
A continuación se detallan los códigos correspondientes a los tres recorridos en profundidad. En cualquiera de los casos, desde el método de llamada se llama a uno auxiliar recursivo, pasándole como argumento la posición de la raíz (0).
Recorrido en preorden:
En el método recursivo privado preOrdenAux, se escriben las claves del árbol en preorden: primero escribimos la clave del nodo (matriz [i].clave), luego se avanza por la izquierda (haciendo la llamada con matriz [i].izq), y luego por la derecha (matriz [i].der).
Recorrido en orden central:
Recorrido en post-orden:
En el método recursivo privado ordenCentralAux, se escriben las claves del árbol en post orden: primero se avanza por la izquierda (haciendo la llamada con matriz [i].izq, ), luego por la derecha (matriz [i].der) y por último escribimos la clave del nodo (matriz [i].clave).
4.1.2. Búsqueda.
Para realizar una búsqueda en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si no hemos llegado a un nodo vacío (if (i != NULL), en cuyo caso devolveremos false como resultado), y luego vamos avanzando por la rama correspondiente:
- si la clave es mayor que la buscada seguiremos por la izquierda (resul = busqueda (matriz [i].izq, dato)),
- si la clave es menor que la buscada seguiremos por la derecha (resul = busqueda (matriz [i].der, dato)),
- y si la clave es la que estamos buscando, pararemos devolviendo como resultado true.
4.1.3. Inserción.
Para realizar la inserción en un árbol binario de búsqueda sobre matriz, es necesario comprobar primero si todavía no está lleno el árbol (comprobando la variable miembro numNodos). Si se va a insertar en un árbol vacío, la inserción se hará en el método de llamada (insertar):
Para el resto de los nodos utilizaremos el método recursivo insertarAux. Para ello, primero habrá que localizar dónde deberíamos insertar el nodo (realizando una búsqueda guiada por el árbol). Una vez localizado, utilizaremos para el nuevo nodo la primera posición libre en la matriz (la posición numNodos).
4.1.4. Eliminación.
Para eliminar una clave, se sigue la misma estrategia que en el apartado 3.2.2:
- El método recursivo eliminar busca la clave que se desea eliminar.
- Si es una hoja se elimina directamente,
- Si es un nodo con un hijo se sustituye por el hijo,
- Y si es un nodo con dos hijos se llama al método eliminarDosHijos para sustituir la clave del nodo por la inmediatamente anterior (bajando una vez a la izquierda y luego todo el rato a la derecha hasta encontrar un nodo sin hijo izquierdo).
Por último, si encontramos el nodo a eliminar, en cualquiera de los casos (tenga cero, uno o dos hijos) se utilizará un método auxiliar (borrarNodo) para desplazar los elementos que haya a continuación del nodo eliminado.
Por ejemplo, si en el árbol de la figura 1.13., representado por la matriz que aparece a continuación, eliminamos el nodo 20, el resultado sería el de la figura 1.14:
Figura 1.13. Árbol binario antes de eliminar.
Resultado:
Figura 1.14. Árbol binario después de eliminar la clave 20.
Obsérvese que, al haber desplazado los elementos de la matriz hacia la izquierda, la clave 25 aparece repetida. De todas formas, dicho valor no se tendrá en cuenta, dado que la posición 5 sólo se alcanzará en caso de insertar una nueva clave (y se sustituirá dicha clave por su nuevo valor).
No hay comentarios:
Publicar un comentario