Download Diapositiva 1 - WordPress.com

Á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 GENERALES
El 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.
Árbol: Definición recursiva
Un árbol es un conjunto de nodos que:
1.
2.
O bien es vacío.
O tiene un nodo determinado llamado
raíz, del que jerárquicamente desciende
cero o más sub árboles, que son también
árboles.
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))
ÁRBOLES BINARIOS
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).
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
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.
ESTRUCTURA DE DATOS
OFELIA GASPARILLO NÁJERA
601-A DESPRESURIZADO