ÁRBOLES

El árbol es una estructura de datos muy importante en informática y en ciencias de la computación. Los árboles son estructuras no lineales, al contrario que los arreglos y las listas enlazadas.

En informática son utilizados para representar fórmulas algebraicas, en diseño de compiladores, procesadores de texto y algoritmos de búsqueda., y en aplicaciones diversas tales como la inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas operativos almacenan sus archivos en árboles.

ÁRBOLES GENERALESEl concepto de árbol implica una

estructura en la que los datos se organizan de modo que los elementos de información están relacionados entre sí a través de ramas.

Conceptos BásicosÁrbol: Conjunto finito de elementos.Raíz : Es el primer nodo insertado.Nodo: Elemento de un árbol.Rama o arco: línea dirigida que conecta los nodos.Nodo Padre: Nodo que tiene nodo(s) sucesores.Nodo Hijo: Nodo que tiene un nodo antecesor.

Conceptos Básicos

Nodo Hoja: Nodo sin hijos o nodo terminal.Nivel: Distancia a la raíz.Altura o profundidad: Es el nivel de la hoja del camino más largo desde la raíz más uno.Subárbol: Cualquier estructura conectada por debajo de la raíz.Nodos hermanos: Los nodos que tienen el mismo padre.Camino: Es una secuencia de nodos (desde la raíz hasta el nodo deseado).Grado del nodo: Número de ramas asociadas.

Un árbol es un conjunto de nodos que:

1. O bien es vacío.2. O tiene un nodo determinado llamado

raíz, del que jerárquicamente desciende cero o más sub árboles, que son también árboles.

Árbol: Definición recursiva

REPRESENTACIÓN DE UN ÁRBOL

De lista: se representa mediante paréntesis.

Notación en paréntesis: A(B(C,D),E,F(G,H,I))

Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles.

En un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles).

ÁRBOLES BINARIOS

REPRESENTACIÓN DE UN ÁRBOL

Un árbol binario se divide en tres subconjunto disjuntos:

{R} Nodo raíz

{I1, I2, …, In} Subárbol izquierdo de R

{D1, D2, …, Dn} Subárbol derecho de R

Equilibrio: Para determinar si un árbol está equilibrado, se calcula el factor de equilibrio de cada nodo.

El factor de equilibrio de un nodo en un árbol binario es la diferencia entre la altura del subárbol derecho (HD) y la altura del subárbol izquierdo (HI). fe(B) = HD - HI .

EQUILIBRIO

La estructura de un árbol binario se construye con nodos.

Un valor null indica un árbol vacío.

Cada nodo debe contener el campo dato (datos a almacenar) y dos campos punteros o referencia, uno al subárbol izquierdo y otro al subárbol derecho, que se conocen como rama izquierda (izquierdo, izqdo) y rama derecha (derecho, dcho) respectivamente.

EQUILIBRIO

ESTRUCTURA DE DATOS

OFELIA GASPARILLO NÁJERA

601-A DESPRESURIZADO