Download Tema: Repaso sobre estructuras de datos utilizando C

Sistemas Expertos e Inteligencia Artificial. Guía No. 2
1
Facultad: Ingeniería
Escuela: Computación
Asignatura: Sistemas Expertos e
Inteligencia Artificial
Tema: Repaso sobre estructuras de datos utilizando
C#.
Objetivos Específicos

Implementar la estructura de datos Árbol en C #.

Identificar e implementar los recorridos más comunes en la estructura de datos Árbol.

Crear aplicaciones utilizando Windows Forms de Microsoft Visual C#.
Materiales y Equipo
 Guía Número 2.
 Computadora con programa Microsoft Visual C#.
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 No. 2
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 Figura siguiente muestra un Árbol binario:
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:
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
3
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.
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 en PreOrden del árbol es 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);
}
}
4
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
El recorrido en EnOrden del árbol es el siguiente: 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 es el siguiente: 4, 10, 6, 17, 22, 20, 15
Procedimiento
Ejemplo 1. Implementaremos un árbol binario de búsqueda en C#:
1. Crear un proyecto de tipo Windows Forms Application, se sugiere darle el nombre de “Arbol
Binario”.
2. A continuación se les proporcionan ciertas clases y funciones para implementar el objeto “nodo”
de la estructura de datos Árbol.
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
5
6
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
7
3. Agregar una clase al proyecto, se sugiere darle el nombre de “Arbol Binario”. Esta clase la
utilizaremos para definir la estructura “Árbol”.
El código es el siguiente:
8
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
9
4. Ahora debe diseñar el formulario que nos servirá para implementar el simulador del Árbol
Binario de Búsqueda que queremos realizar.
Queda a creatividad de cada estudiante el diseño del mismo.
En la siguiente imagen se muestra cómo podría lucir el formulario:
10
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
Análisis de resultados
1) Tomando como referencia el código ejemplo proporcionado, se les pide implementar un
Simulador de la estructura de datos Árbol Binario de Búsqueda (ABB) con la siguiente
funcionalidad:
a) Insertar Nodo
b) Eliminar Nodo
c) Buscar Nodo
d) Desarrolle el método “Mostrar/Recorrer el Árbol en profundidad” usando los
siguientes recorridos:
 Recorrido en orden.
 Recorrido en Pre-orden.
 Recorrido en Post-orden.
Investigación Complementaria
Para la siguiente semana:
1. Aplicar las modificaciones necesarias, para agregar mayor funcionalidad al programa
simulador del Árbol ABB.
Deben implementarse las siguientes opciones:
a. Desarrollar el método “Recorrer el Árbol en Anchura”.
b. Determinar el elemento máximo y el mínimo en un ABB (identificarlos gráficamente en el
árbol).
c. Determinar la altura del ABB.
d. Determinar la profundidad de un nodo (se solicitará el dato al usuario, identificarlo
gráficamente en el árbol).
e. Determinar el número de nodos en cualquier momento.
2. Investigar ¿Cuál es la Estructura de los Sistemas Basados en Conocimiento?
Sistemas Expertos e Inteligencia Artificial. Guía No. 2
Guía 2: Repaso sobre
datos utilizando C#.
estructuras
de
Hoja de cotejo:
Alumno:
Máquina No:
Docente:
GL:
11
2
Fecha:
EVALUACIÓN
%
CONOCIMIENTO
Del 20
al 30%
APLICACIÓN
DEL
CONOCIMIENTO
Del 40%
al 60%
ACTITUD
Del 15%
al 30%
TOTAL
100%
1-4
5-7
8-10
Conocimiento
deficiente
de los
fundamentos
teóricos
Conocimiento
y explicación
incompleta de
los
fundamentos
teóricos
Conocimiento
completo y
explicación
clara de los
fundamentos
teóricos
No tiene
actitud
proactiva.
Actitud
propositiva y
con
propuestas no
aplicables al
contenido de
la guía.
Tiene actitud
proactiva y
sus propuestas
son concretas.
Nota