Temas Variados

Instituto Tecnológico Superior de Fresnillo

Academia de Informática

ESTRUCTURAS DE DATOS
UNIDAD 4: ESTRUCTURAS NO LINEALES OBJETIVO O COMPETENCIA A DESARROLLAR:
Conocer, identificar y aplicar las estructuras no lineales en la solución de problemas del mundo real.

TEMARIO:
TEMAS Estructuras No Lineales SUBTEMAS 4.1 Arboles. 4.1.1 Concepto de árbol. 4.1.2 Clasificación de árboles. 4.1.3Operaciones básicas sobre árboles binarios. 4.1.4 Aplicaciones. 4.1.5 Arboles balanceados (AVL). 4.2 Grafos. 4.2.1 Terminología de grafos. 4.2.2 Operaciones básicas sobre grafos.

ACTIVIDADES DE APRENDIZAJE:
  Consultar en las fuentes bibliográficas la terminología sobre árboles. Comentar información en plenaria. Práctica de ejercicios. Utilizando un lenguaje de programación implemente lasoperaciones básicas (insertar, eliminar, buscar) en un árbol binario de búsqueda, así como los recorridos en preorden, inorden y postorden.

ESTRUCTURAS DE DATOS

Unidad 4. Estructuras No Lineales

1

Instituto Tecnológico Superior de Fresnillo

Academia de Informática

CONTENIDO DE LA UNIDAD 4
TEMA 1: ARBOLES
Definición Los Árboles son estructuras que permiten representar datos quetienen enlaces jerárquicos entre ellos, podemos mencionar por ejemplo registros, árboles genealógicos, etc. Existen diferentes tipos de árboles: Árboles Binarios y Árboles Generales. Un árbol se define como un conjunto de uno o más nodos tales que: 1. Existe un nodo especial llamado Raíz. 2. Los restantes nodos se dividen en conjuntos disjuntos, cada uno de los cuales es un subárbol. Otros deestructura en árbol es el sistema de directorios y archivos de un sistema operativo, otro ejemplo podría ser la tabla de contenido de un libro, dividido en capítulos, y cada uno de ellos en subcapítulos. Aunque el libro sea algo lineal, como una lista, en el que cada capítulo sigue al anterior, también es posible acceder a cualquier punto de él a través de la tabla de contenido.

Representación enmemoria de Árboles
Los Arboles generalmente se pueden representar de dos formas: • Matriz de adyacencia: Es un arreglo [1..n,1..n] de tipo boolean donde n es el número de nodos que tiene el árbol y cada posición de la matriz indicará si existe un enlace entre dos nodos. La representación por medio de matrices de adyacencia es común en lenguajes en que no pueden crearse componentes dinámicamente, yreferenciarlos por medio de punteros. Lista enlazadas: Es una lista de 1 a n, siendo n el número de nodos, donde cada elemento de la lista representa cada uno de los nodos del árbol, enlazados por medio de punteros.

•

Operaciones con árboles
Las operaciones que se llevan a cabo con árboles se pueden aplicar tanto para árboles binarios como generales: • • • • • Añadir o insertar elementos.Buscar o localizar elementos. Borrar elementos. Moverse a través del árbol. Recorrer el árbol completo.

Árboles Binarios
Un Árbol Binario es un árbol ordenado de grado 2, contiene una raíz con dos subárboles llamados subárbol izquierdo y subárbol derecho, un árbol binario de cero nodos se dice que está vacío.

ESTRUCTURAS DE DATOS

Unidad 4. Estructuras No Lineales

2

InstitutoTecnológico Superior de Fresnillo

Academia de Informática

Terminología: Nodo Raíz o Raíz del Arbol Nodo Terminal Nodo Interior Nodo Hijo Nodo Padre Hoja Subárbol elemento superior (cima del árbol) un nodo que no tiene subárboles nodos con uno o dos subárboles nodo situado directamente debajo de otro nodo situado directamente encima de otro elemento o nodo terminal, sin descendiente cualquierconjunto de nodos después del nodo raíz

Existen otros conceptos que definen las características del árbol, en relación a su tamaño:  Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.  Grado: el número de hijos que tiene...