Unidad 4 Estructuras no lineales

4.1 Arboles

4.1.1 Concepto de árbol

4.1.2 Clasificación de arboles

4.1.3 Operaciones básicas sobre arboles 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.

4.1  ARBOLES

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos.

También se suele dar una definición recursiva: un árbol es una estructura en compuesta por un dato y varios árboles.

Esta estructura se usa principalmente para representar datos con una relación jerárquica entre sus elementos, como por ejemplo registros, árboles genealógicos, y tablas de contenidos. Vamos a profundizar en un tipo especial de árbol llamado árbol binario, la cual puede ser implementada fácilmente en la computadora; aunque en un árbol puede parecer muy restrictivo. También se va a ampliar sobre árboles más generales y puntos con relación a los árboles binarios; entre estos tenemos a la terminología, los árboles binarios complementos, árboles binarios de búsqueda, búsqueda e inserción en árboles binarios de búsqueda, árboles generales, representación de árboles generales en la computadora y correspondencia entre los árboles generales y árboles binarios.

4.1.1 CONCEPTO DE ARBOLES

Caso base: un árbol con sólo un nodo (es a la vez raíz del árbol y hoja). 

Una sucesión de nodos del árbol, de forma que entre cada dos nodos consecutivos de la sucesión haya una relación de parentesco, decimos que es un recorrido árbol. Existen dos recorridos típicos para listar los nodos de un árbol: primero en profundidad y primero en anchura. En el primer caso, se listan los nodos expandiendo el hijo actual de cada nodo hasta llegar a una hoja, donde se vuelve al nodo anterior probando por el siguiente hijo y así sucesivamente. En el segundo, por su parte, antes de listar los nodos de nivel n+1 (a distancia n+1 aristas de la raíz), se deben haber listado todos los de nivel n. Otros recorridos típicos del árbol son preorden, postorden e inorden:

 

El recorrido en inorden, también llamado orden simétrico (aunque este nombre sólo cobra significado en los árboles binarios) consiste en recorrer en primer lugar A_1, luego la raíz y luego cada uno de los hijos A_2 \dots A_k en orden simétrico.

 

El recorrido en postorden, también llamado orden posterior consiste en recorrer en primer lugar cada uno de los hijos A_1, A_2 \dots A_k en orden posterior y por último la raíz.