Tema 4
Árboles
Estructura de Datos y Algoritmos II
Profesora: Elba Karen Sáenz García
Árboles
• Estructura de datos No lineal
,cada elemento puede tener
varios sucesores y un
predecesor.
• Colección de elementos
llamados nodos, uno de los
cuales se distingue como raíz,
junto con una relación(rama)
que impone una estructura
jerárquica entre los nodos.
Profesora : Elba Karen Sáenz García 2
• En informática se utilizan para
aplicaciones algorítmicas
(ordenación, búsqueda),
compilación (árboles sintácticos,
árboles de expresiones), etc.
Árbol • Otras representaciones :
• Un diagrama de Ven
• anidación de paréntesis
• notación decimal de Dewey
Representación de un árbol
Profesora : Elba Karen Sáenz García 4
Representación de un árbol
Profesora : Elba Karen Sáenz García 5
• Un solo nodo es, por sí mismo un árbol. Ese
nodo es también la raíz de dicho árbol.
• Suponer que es un nodo y que
, ,…., son árboles con raíces
, , … . , , respectivamente. Se puede
Árbol construir un nuevo árbol haciendo que se
constituya en el padre de los nodos
(Definición) , , … . , . En dicho árbol, n es la raíz
y , ,…., son subárboles de la raíz. Lo
nodos , , … . , , reciben el nombre de
hijos del nodo .
• La definición implica que cada nodo del árbol
es raíz de algún subárbol contenido en el árbol
principal.
• Grado de un nodo: Es el número de subárboles o
hijos que tienen como raíz ese nodo. En la figura
8.2 b) la raíz del árbol es libro y este tiene 3
subárboles C1, C2 y C3, el grado de libro es tres.
• Nodo terminal u hoja: Nodo con grado 0, no tiene
subárboles, por ejemplo el nodo C3.
• Grado u orden de un árbol: Grado máximo de los
Términos nodos de un árbol.
• Hijos de un nodo: Nodos que dependen directamente
de ese nodo, es decir, las raíces de sus subárboles.
• Padre de un nodo: Antecesor directo de un nodo,
nodo del que depende directamente.
• Nodos hermanos: Nodos hijos del mismo nodo padre.
• Camino: Sucesión de nodos del árbol , … … , tal que es el
padre de .
• Antecesores de un nodo: Todos los nodos en el camino desde la raíz del
árbol hasta ese nodo.
• Nivel de un nodo: Longitud del camino desde la raíz hasta el nodo.
• Altura (profundidad) de un árbol: Nivel máximo de un nodo en un árbol.
• Amplitud (Anchura): El número de nodos del nivel más poblado.
• Longitud de camino de un árbol: Suma de las longitudes de los caminos a
todos sus componentes.
• Orden: El Orden de un árbol es el número máximo de hijos que puede
tener un Nodo.
Profesora : Elba Karen Sáenz García 9
Ejemplo
• A es la raíz del árbol
• B es hijo de A, C es hijo de A
• D es hijo de B
• A es padre de B
• H es padre de L
• B y C son hermanos- D,E,F son hermanos
• I,E,J,K,G y L son hojas o nodos terminales
• B,C,D,E,F,G,H son nodos interiores o ramas
Profesora : Elba Karen Sáenz García 10
• El grado del nodo A es 2
• El grado de C es 2
• El grado de E es cero
• Grado del árbol es 3
• El nivel de A es 1 (0), el de B es 2 (1)
• El nivel de D es 3(2), el de L es 4 (3)
• La altura del árbol es 4 (3)
• Longitud de camino de A en 1 (0), de B es 2 (1) , de I es 4 (3) de H es
3 (2)
Profesora : Elba Karen Sáenz García 11
Árboles Binarios
• Es un árbol de grado dos, esto es, cada nodo puede tener dos, uno o
ningún hijo
• Se distingue entre el subárbol izquierdo y el subárbol derecho de cada
nodo.
Profesora : Elba Karen Sáenz García 12
Árbol Binario n
• Se puede definir al árbol binario como un
conjunto finito de nodos ( 0), tal
que:
• Si 0, el árbol está vacío
• Si 0
• Existe un nodo raíz
• El resto de los nodos se reparte entre dos
árboles binarios, que se conocen como
subárbol izquierdo y subárbol derecho de la
raíz.
Profesora : Elba Karen Sáenz García 13
• El recorrido de una estructura de datos es el
Recorridos de acceso sistemático a cada uno de sus miembros.
árboles • Hay dos formas básicas de recorrer un árbol; en
profundidad y en amplitud
binarios • Recorrido en profundidad
• Recorrido en anchura
• Alejarse en todo lo posible de la raíz hasta
alcanzar un nodo hoja. Una vez alcanzado se da
un paso atrás para intentar alejarse por un
Recorrido en camino alternativo.
• Variantes:
Profundidad preorden
inorden (simétrico)
posorden
• Pre-orden: (raíz - subarbol izq. - subarbol der).
Recorrido en • Visitar la raíz del árbol
• Recorrer el sub árbol izquierdo en pre-orden
pre-orden • Recorrer el subárbol derecho en pre-orden
Profesora : Elba Karen Sáenz García 17
(subárbol izq-raíz-subárbol derecho)
• Recorrer el subárbol izquierdo en in-orden
• Visitar raíz
Recorrido en • Recorrer el subárbol derecho en in-orden
In- orden
Inorden
Profesora : Elba Karen Sáenz García 19
(subárbol izq-subárbol derecho- raíz)
• Recorrer el subárbol izquierdo en pos-orden
Recorrido • Recorrer el subárbol derecho en pos-orden
• Visitar raíz
pos-orden
Profesora : Elba Karen Sáenz García 21
• También conocida como recorrido por niveles o
Recorrido en en amplitud. Se explora el árbol nivel a nivel, de
izquierda a derecha y del primero al último.
Anchura
Profesora : Elba Karen Sáenz García 23
Ejercicio
• Para el siguiente árbol obtener sus recorridos son:
Profesora : Elba Karen Sáenz García 24
Tarea
Profesora : Elba Karen Sáenz García 25
Características de Árboles
Binarios
Estructura de Datos y Algoritmos II
Profesora: Elba Karen Sáenz García
Profesora : Elba Karen Sáenz García 26
Tipos de árboles
• Arboles binarios. • Arboles multicaminos o
• Arboles binarios distintos multirama
• Arboles binarios similares • Arboles-B
• Arboles binarios equivalentes • Arboles B+
• Arboles binarios completos • Arboles 2-4
• Arboles binarios llenos
• Arboles binarios degenerados
• Arboles binarios de búsqueda
• Arboles equilibrados
Profesora : Elba Karen Sáenz García 27
Árboles
• Árboles binarios distintos. Son distintos cuando sus
estructuras son diferentes.
• Árboles binarios similares. Son similares cuando sus
estructuras son idénticas, pero la información que
contienen sus nodos difiere entre sí.
• Árboles binarios equivalentes. Los árboles binarios
equivalentes se definen como aquellos que son similares
y además los nodos contienen la misma información.
Profesora : Elba Karen Sáenz García 28
Árbol binario lleno
• Es un árbol binario lleno si cada nodo es de grado cero o dos. Es decir,
no existe un nodo que tenga un solo hijo.
Profesora : Elba Karen Sáenz García 29
¿Cúal es un árbol binario lleno?
Profesora : Elba Karen Sáenz García 30
Árbol binario
completo
• Si todos los nodos de grado
cero o uno están en los dos
últimos niveles.
• Las hojas del último nivel
ocupan las posiciones más a
la izquierda de dicho nivel.
• Todos los niveles, excepto
posiblemente el último están
completamente llenos.
Profesora : Elba Karen Sáenz García 31
Árboles equilibrados
• Es equilibrado cuando la diferencia de altura
entre los subárboles de cualquier nodo es
máxima 1.
• Es equilibrado totalmente cuando los
subárboles izquierdo y derecho de cada
nodo tienen las mismas alturas, es decir, es
un árbol lleno.
• Se dice que un árbol completo es
equilibrado y un árbol lleno es totalmente
equilibrado.
Profesora : Elba Karen Sáenz García 32
Operaciones en árboles binarios
• Crear y eliminar el árbol
• Verificar el estado del árbol, si está vacío o no.
• Crear y remover nodos
• Saber si el nodo es hoja o no
• Búsqueda por contenido
• Recorrer el árbol
• Obtener el padre, hijo izquierdo o hijo derecho, dado un nodo.
Profesora : Elba Karen Sáenz García 33
Importante
• Una de las operaciones básicas es la creación del árbol, una vez que ya se
tiene, se pueden realizar las operaciones sobre sus elementos como
recorrerlo, insertar un nuevo nodo, eliminar uno existente o buscar un valor
determinado.
• El proceso de generación de un árbol dependerá de las reglas impuestas por
una aplicación particular y el procedimiento de generación deberá, por
tanto, reproducir de la manera más eficiente posible esas reglas de
generación.
Profesora : Elba Karen Sáenz García 34
Representación de lo árboles con arreglos o
listas
Profesora : Elba Karen Sáenz García 35
Representación con arreglos
• El padre del nodo estará localizado en
la posición ( − 1)/2 si 0 . Si 0,
se trata del nodo raíz y no tiene padre.
• El hijo izquierdo del nodo estará
localizado en la posición
(2 ∗ ( + 1)) − 1 2 ∗ ( + 1) − 1 < .
Si 2 ∗ ( + 1) − 1 ≥ , el nodo no tiene
hijo izquierdo.
• El hijo derecho del nodo estará
localizado en la posición
(2 ∗ ( + 1)) 2 ∗ ( + 1) < .
2 ∗ ( + 1) ≥ , el nodo no tiene hijo
derecho.
Profesora : Elba Karen Sáenz García 36
Representación de lo árboles
Profesora : Elba Karen Sáenz García 37
Representación de cada nodo como objeto o estructura
Cada nodo de un árbol como un objeto o estructura, donde cada nodo contiene
como atributos el valor, y las referencias a los nodos hijos su padre.
Profesora : Elba Karen Sáenz García 38
Profesora : Elba Karen Sáenz García 39
Árboles binarios de
búsqueda
Estructura de Datos y Algoritmos II
Profesora: Elba Karen Sáenz García
• Los nodos se identifican con una llave k
Árboles • No existen nodos con la misma llave
• Los nodos están ordenados de manera
binarios de conveniente para la búsqueda de una llave.
búsqueda
Árbol binario de búsqueda
• Todos los elementos
almacenadas en
• el subárbol izquierdo de
un nodo con llave k,
tienen valores menores
que k.
• en el subárbol derecho de
un nodo con llave k,
tienen valores mayores o
iguales que k. Los subárboles izquierdo y derecho son
también árboles binarios de búsqueda.
Profesora : Elba Karen Sáenz García 42
Inserción
• Se realiza de acuerdo al orden
• Ejemplo: Insertar las siguientes llaves en un árbol binario de
búsqueda 9, 2, 1, 16, 6, 11, 8, 4
Profesora : Elba Karen Sáenz García 43
padre
padre
Insertar()
llave
Profesora : Elba Karen Sáenz García 44
Algoritmo insertar
Insertar(valor)
Inicio
Si árbol vacio
crear nodo raíz con llave correspondiente
Si no
agregarNodo(A nodo-raiz, valor)
Fin Si
Fin
Profesora : Elba Karen Sáenz García 45
AgregarNodo( nodoActual, valor):
Inicio
Si valor < valor del nodoActual vamos a la izquierda
Si nodo Actual tiene hijo izquierdo
AgregarNodo(valor, nodoActual.hijoIzquierdo)
Si no
Formar nuevoNodo y asignarle valor
nodoActual.hijoIzquierdo=nuevoNodo
nodoActual.hijoIzq.padre=nodoActual
Fin Si no
Si no vamos a la derecha
Si nodo Actual tiene hijo derecho
AgregarNodo(valor, nodoActual.hijoDerecho)
Si no
Formar nuevoNodo y asignarle valor
nodoActual.hijoDerecho=Nodo
nodoActual.hijoDer.padre=nuevoActual
Fin Si no
Fin Si no Profesora : Elba Karen Sáenz García 46
Fin
Recorrido del árbol
• La obtención de las llaves se puede realizar en un orden dependiendo del
recorrido que se realice (preorden , in- orden, post orden)
• Se consigue con un procedimiento recursivo.
InOrden(Nodo)
Inicio
Si es Nodo valido
InOrden(Nodo.hijoIzquierdo)
Imprimir Nodo.llave
In_Orden(Nodo.derecho)
Fin Si
Fin
Profesora : Elba Karen Sáenz García 47
InOrden(Nodo)
Inicio
Si es Nodo valido
InOrden(Nodo.hijoIzquierdo)
Imprimir Nodo.llave
In_Orden(Nodo.derecho)
Fin Si
Fin
InOrden(Nodo)
Inicio
Si es Nodo valido
InOrden(Nodo.hijoIzquierdo)
Imprimir Nodo.llave
In_Orden(Nodo.derecho)
Fin Si
Fin
InOrden(Nodo)
Inicio
Si es Nodo valido
InOrden(Nodo.hijoIzquierdo)
Imprimir Nodo.llave
In_Orden(Nodo.derecho)
Fin Si
Fin
NILL
NILL
InOrden(Nodo)
Inicio
Si es Nodo valido
InOrden(Nodo)
InOrden(Nodo.hijoIzquierdo)
Inicio
Imprimir Nodo.llave
Si es Nodo valido
In_Orden(Nodo.derecho)
InOrden(Nodo.hijoIzquierdo)
Fin Si
Imprimir Nodo.llave
Fin
In_Orden(Nodo.derecho)
Fin Si
Fin
Profesora : Elba Karen Sáenz García 48
Algoritmo buscar en árbol binario de búsqueda
Busqueda (nodoX, llave)
Inicio
Si (nodoX==Ninguno) o ( valor==nodoX.llave)
Retornar nodoX
Fin Si
Si llave < nodox.llave
Retornar Busqueda(nodoX.hijoIzq, llave)
En otro caso
Retornar Busqueda(nodoX.hijoDer, llave)
Fin Si
Fin
Profesora : Elba Karen Sáenz García 49
