Download Guía 2

1
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
Centro de Investigación y
Transferencia de Tecnología
Estructuras de datos utilizando JAVA
Facultad: Ingeniería
Escuela: Computación
Asignatura: Sistemas Expertos e Inteligencia Artificial
Contenido
En esta práctica de laboratorio se aborda el tema de las estructuras de datos (árboles binarios) en las cuales se estudian
los tipos de recorridos y los diferentes resultados que éstos emiten.
Además, se introduce el estudio de un nuevo lenguaje de programación.
Objetivos Específicos



Implementar el TAD Árbol en Java (Netbeans).
Identificar e implementar los recorridos más comunes en el TAD Árbol.
Crear aplicaciones utilizando Netbeans.
Material y Equipo



Guía de laboratorio N° 2.
Computadora con Netbeans 7 o superior.
Dispositivo de almacenamiento.
Introducción Teórica
En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo
izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre “Binario”).
Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo.
En el caso contrario el hijo es llamado un nodo interno.
Definición de Árbol Binario
Un árbol binario es una estructura de datos de tipo árbol en donde cada uno de los nodos del árbol puede tener 0, 1, ó 2
sub árboles llamados de acuerdo a su caso como:
1.
Si el nodo raíz tiene 0 relaciones, se llama hoja.
2.
Si el nodo raíz tiene 1 relación a la izquierda, el segundo elemento de la relación es el subárbol izquierdo.
3.
Si el nodo raíz tiene 1 relación a la derecha, el segundo elemento de la relación es el subárbol derecho.
2
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
La Figura anterior muestra un árbol binario sencillo de tamaño 9 y altura 4, con un nodo raíz cuyo valor es 15.
La siguiente figura muestra un árbol binario por niveles:
La altura de un árbol es equivalente a la cantidad de niveles del mismo.
Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo
se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subárbol izquierdo y derecho del
subárbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
Recorrido del árbol.
Recorrer el árbol significa que cada nodo sea procesado una vez en una secuencia determinada.
Existen dos enfoques generales:

Recorrido en Profundidad: El proceso exigen alcanzar las profundidades de un camino desde la raíz hacia el
descendiente más lejano del primer hijo, antes de proseguir con el segundo.

Recorrido en Anchura: El proceso se realiza horizontalmente desde la raíz a todos sus hijos antes de pasar con la
descendencia de algunos de ellos.
3
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
Si tomamos como ejemplo el árbol binario:
Para realizar el recorrido en Profundidad de un árbol, existen tres algoritmos distintos:
Recorrido PreOrden (ArbolBinario raíz)
{
if (raiz)
{
visitar (raiz–>dato) ;
PreOrden (raiz–>izq);
PreOrden (raiz–>der);
}
}
El recorrido sería el siguiente: 15, 6, 4, 10, 20, 17, 22
Recorrido enOrden (ArbolBinario raíz)
{
if (raiz)
{
enOrden (raiz–>izq);
visitar (raiz–>dato);
enOrden (raiz–>der);
}
}
El recorrido en orden del árbol sería: 4, 6, 10, 15, 17, 20, 22
Recorrido PostOrden (ArbolBinario raíz)
{
if (raiz)
{
PostOrden (raiz–>izq);
PostOrden (raiz–>der);
visitar (raiz–>dato);
}
}
El recorrido en PostOrden del árbol sería: 4, 10, 6, 17, 22, 20, 15
Procedimiento
1.
Abrir Netbeans y crear un nuevo proyecto con el nombre ArbolBinario.
File  New Project.
4
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
2.
Agregar el nombre a su proyecto (queda a su decisión el cambiarlo de ubicación dentro de la máquina):
3.
Al crear su proyecto aparecerá una clase por defecto con el mismo nombre de éste.
4.
Hacer doble clic sobre la clase (ArbolBinario) y digitar el siguiente código:
5
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
6
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
7
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
5.
La clase se agrega de la siguiente manera:
La clase tendrá el nombre de Nodo.java.
6.
Digitar el siguiente código en la clase Nodo.java.
7.
Agregar un formulario (Jframe.java), esto se logra de la siguiente manera:
8
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
8.
Ahora, procedemos a crear el siguiente diseño haciendo uso del swing de java. Utilizando los siguientes
componentes
Text Field
Panel
Button
Text Area
9
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
9.
Cambiar o verificar las siguientes propiedades de los componentes que se encuentran en el formulario
Nombre de
componente
Panel
Propiedad (Properties)
Propiedad (Code)
preferredSize: 861,478
Variable Name: jPanel2
TextField
text: <vacío>
Variable Name: txDato
Button (1)
text: Agregar Nodo
Variable Name: jButton1
Button (2)
text: Eliminar Árbol
Variable Name: jButton2
Button (3)
text: Pre-orden
Variable Name: jButton3
Button (4)
text: In-orden
Variable Name: jButton4
Button (5)
text: Pos-torden
Variable Name: jButton5
Button (6)
text: Por nivel
Variable Name: jButton6
Button (7)
text: Buscar Dato
Variable Name: jButton7
TextArea
JFrame
Variable Name: jTextArea1
title: Recorrido de Árboles Binarios
preferredSize: 1071,655
resizable: deseleccionar la opción
10. Hacer clic en la opción Source
Verificar y/o agregar las siguientes librerías:
10
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
11. Antes del constructor Frame agregar la declaración del objeto ab (línea 16):
12. En el formulario, siempre en la pestaña Design realizar los siguientes pasos:
a.
Hacer doble clic en el botón Agregar nodo y agregar el siguiente código:
b. Hacer doble clic en el botón Eliminar Árbol y agregar el siguiente código:
c.
Hacer doble clic en el botón Pre-orden y agregar el siguiente código:
11
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
d. Hacer doble clic en el botón In-orden y agregar el siguiente código:
e.
Hacer doble clic en el botón Post-orden y agregar el siguiente código:
f.
Hacer doble clic en el botón Por Nivel y agregar el siguiente código:
g. Hacer doble clic en el botón Buscar Dato y agregar el siguiente código:
12
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
13. Siempre en el código fuente del formulario
Agregar el siguiente método:
14. Guardar los cambios al proyecto
13
Sistemas Expertos e Inteligencia Artificial / Guía II / Ciclo 01 - 2017
15. Ejecutar el proyecto, y hacer pruebas, un ejemplo de salida se ve a continuación:
Análisis de resultados
1.
Modificar el ejercicio, para que también acepte letras en los nodos del árbol binario
Investigación Complementaria
Realizar los siguientes ejercicios:
1.
Mostrar el mayor y menor valor del árbol.
2.
Calcular la cantidad de nodos del árbol
3.
Mostrar la cantidad de niveles del árbol
4.
Retornar la altura del árbol.
Bibliografía

http://www.utm.mx/~rruiz/cursos/ED/material/ABB.pdf

http://informatica.uv.es/iiguia/AED/teoria/apuntes/cuatr2/tema14.pdf

http://eii.ucv.cl/pers/guidi/cursos/estructuras/pdf/Estructuras-ArbolesBinarios.pdf