Árboles

INTRODUCCION
• Las listas enlazadas son estructuras lineales
• Son flexibles pero son secuenciales, un elemento detrás de otro
• Los árboles
• Junto con los grafos son estructuras de datos no lineales
• Superan las desventajas de las listas
• Sus elementos se pueden recorrer de distintas formas, no necesariamente uno
detrás de otro
• Son muy útiles para la búsqueda y recuperación de información
Representación gráfica de un árbol

Diagramas de Venn Nodos y aristas (círculos y flechas)

Representación gráfica de un árbol

Paréntesis anidados Nodos

 Arboles

• Un árbol representa una jeraquía

Ejemplos:
Estructura Organizativa de una Eempresa

tabla de contenido de un libro

Sistema de archivos de Unix o DOS/Windows
 A es Padre

CONCEPTO
B y C hijos de A:
hermanos
B es Padre
D, E, F hijos de B
A
• Estructura que organiza sus elementos formando
jerarquías: PADRES E HIJOS
B C
 Los elementos de un árbol se llaman nodos
 Si un nodo p tiene un enlace con un nodo m,
 p es el padre y m es el hijo
D E F
 Los hijos de un mismo padre se llaman: hermanos
 Todos los nodos tienen al menos un padre, menos la raíz: A
 Si no tienen hijos se llaman hoja: D, E, F y C
B
 Un subárbol de un árbol
 Es cualquier nodo del árbol junto con todos sus descendientes
D E F
TERMINOLOGIA
• Raíz: único nodo que no tiene antecesor, es decir, sin padre.
• Rama: arista formado entre dos nodos.
• Antecesor: un nodo A es el antecesor de un nodo B si por alguna de las
ramas de A se puede llegar a B (15 y 17).
• Sucesor: un nodo X es sucesor de un nodo Y si por alguna de las ramas de Y
se puede llegar a X.
• Grado de un nodo: número de descendientes directos que tiene un nodo.
• Grado del árbol: es el mayor grado entre sus nodos.
TERMINOLOGIA
• Nodo interno: es aquel que tiene al menos un descendiente o nodo hijo.
• Nodo hoja (externo): nodo que no tiene descendientes o no tiene nodos
hijos, posee grado 0.
• Descendiente directo: hijo.
• Descendientes: hijo, nieto...
• Subárbol: árbol formado por un nodo y sus descendientes.
TERMINOLOGIA
• Padre: es el antecesor inmediato de un nodo.
• Hijo: cualquiera de sus descendientes inmediatos.
• Descendiente de un nodo: es cualquier sucesor de un nodo.
• Hermano de un nodo: es otro nodo con el mismo padre.
• Generación: es un conjunto de nodos con la misma profundidad.
• Hoja: es el nodo que no tiene sucesores (sin hijos) (terminal). Los que tienen
predecesor y sucesor se llaman nodos interiores.
• Rama: es cualquier camino del árbol.
TERMINOLOGIA
• Camino: Secuencia de nodos conectados dentro de un arbol
• Longitud del camino: es el numero de nodos menos 1 en un camino
• Altura del árbol: es el nivel mas alto del árbol
• Un árbol con un solo nodo tiene altura 1
• Nivel(profundidad) de un nodo: es el numero de nodos entre el nodo y la raíz.
• Nivel de un árbol
• Es el numero de nodos entre la raíz y el nodo mas profundo del árbol, la altura del un árbol entonces
 Terminología de Arboles
• A es el nodo raíz
• B es el padre de D y E
• C es el hermano de B
• D y E son los hijos de B
• D, E, F, G, I son nodos externos o hojas
• A, B, C, H son nodos internos
• La profundidad (nivel) de E es 3
• La altura del árbol es 4
• El grado del nodo B es 2
Actividad. Determinar lo siguiente
del arbol
• Raiz del árbol
• Padre
• Hermanos
• Grado del árbol
• Grado de A,B,C,D,E
• Nivel de A,B,D,C,L
• Altura del árbol
Árbol binario
Operaciones en un árbol binario
• Entre las operaciones básicas a realizar en un árbol binario están las
de sus recorridos:
• Recorrer árbol
• Preorden
• Inorden
• Postorden
• Inserción nodo
• Entre otras
Creación de un árbol binario de
búsqueda (ABB)
• Los ABB son un tipo especial de • El primer número es la raíz del árbol con
árbol binario donde: sus subárboles izquierdo y derecho vacío.
• La información contenida en el • Luego, cada valor se compara con la
información del nodo raíz y se crean los
nodo puede ser un tipo de dato
nuevos hijos con el siguiente criterio:
primitivo (int, char, double) o • Si el número es igual que la información
cualquier tipo de objeto. del nodo raíz, entonces se notificará que
• Un enlace al hijo derecho (raíz hay duplicidad.
del subárbol derecho). • Si el valor es menor que la información del
nodo raíz, entonces se crea un hijo por la
• Un enlace al hijo izquierdo (raíz parte izquierda del árbol.
del subárbol izquierdo). • Si el número a ingresar es mayor que la
información del nodo raíz, entonces se crea
un hijo por la parte derecha del árbol.
Ejemplo
• Se requiere construir un ABB con los siguientes valores:
• 19, 15 47, 40, 12, 50, 17
Ejemplo
• Se requiere construir un ABB con los siguientes valores:
• 19, 15 47, 40, 12, 50, 17
Actividad
• Construya un ABB con los siguientes valores:
 Actividad
• Construya un ABB con los siguientes valores:
Arboles binarios
Programación
Representación

• Nodos como registros: contienen

tres campos
• IZQ  Campo donde se almacena la
dirección el subárbol izquierdo del
nodo.
• INFO  Almacena la información del
nodo.
• DER  Campo donde se almacena la
dirección el subárbol derecho del
nodo.
Representación
Lenguajes
Recorridos en el árbol - Preorden

Descripción: Algoritmo
Proceso Preorden(Nodo)
Si Nodo ≠ nulo Entonces
// Visitar la raíz
Imprimir([Link])
// Recorrer subárbol izquierdo
Preorden([Link])
// Recorrer subárbol derecho
Preorden([Link])
Fin Si
Fin Proceso
Recorridos en el árbol - Postorden

Descripción: Algoritmo
Proceso Postorden(Nodo)
Si Nodo ≠ nulo Entonces
// Recorrer subárbol
izquierdo
Postorden([Link])
// Recorrer subárbol derecho
Postorden([Link])
// Visitar la raíz
Imprimir([Link])
Fin Si
Fin Proceso
Recorridos en el árbol - Inorden

Descripción: Algoritmo
Proceso Inorden(Nodo)
Si Nodo ≠ nulo Entonces
// Recorrer subárbol izquierdo
Inorden([Link])
// Visitar la raíz
Imprimir([Link])
// Recorrer subárbol derecho
Inorden([Link])
Fin Si
Fin Proceso
FJ
J
CA