PDF de programación - Tema: Repaso sobre estructuras de datos utilizando C#

Sistemas Expertos e Inteligencia Artificial. Guía No. 2

1



Tema: Repaso sobre estructuras de datos utilizando
C#.



Facultad: Ingeniería
Escuela: Computación
Asignatura: Sistemas Expertos e
Inteligencia Artificial

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



11



Guía 2: Repaso sobre estructuras de
datos utilizando C#.

Hoja de cotejo:

2

Alumno:

Docente:

Máquina No:

GL:

Fecha:



%

1-4

5-7

8-10

Nota

EVALUACIÓN

CONOCIMIENTO



Del 20
al 30%

APLICACIÓN
DEL
CONOCIMIENTO

Del 40%
al 60%

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



ACTITUD



Del 15%
al 30%

No tiene
actitud
proactiva.

Tiene actitud
proactiva y
sus propuestas
son concretas.

Actitud
propositiva y
con
propuestas no
aplicables al
contenido de
la guía.

TOTAL 100%