Arboles

UNIVERSIDAD ANDINA DEL CUSCO
FACULTAD DE INGENIERÍA
CARRERA PROFESIONAL DE INGENIERÍA DE SISTEMAS
ALGORITMICA Y LABORATORIO DE PROGRAMACIÓN II

Estructuras de Datos Dinámicas: Á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 arrays y las
listas enlazadas, que constituyenestructuras lineales.
Los árboles se utilizan para representar fórmulas algebraicas, para organizar objetos en
orden de tal forma que las búsquedas sean muy eficientes y en aplicaciones diversas
tales como inteligencia artificial o algoritmos de cifrado. Casi todos los sistemas
operativos almacenan sus archivos en árboles o estructuras similares a árboles.
Además de las aplicaciones citadas,los árboles se utilizan en diseño de compiladores,
procesadores de texto y algoritmos de búsqueda.
Un árbol consta de un conjunto finito de elementos, denominados nodos y de un
conjunto finito de líneas dirigidas, denominadas ramas, que conectan los nodos. El
número de ramas asociado con un nodo es el grado del nodo.

Figura 1. Árbol

ÁRBOLES BINARIOS
Un árbol binario es un árbol cuyosnodos no pueden tener más de dos subárboles. En
un árbol binario, cada nodo puede tener cero, uno o dos hijos (subárboles). Se conoce
el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.

Figura 2. Árboles binarios
Nota
Un árbol binario no puede tener más de dos subárboles.
Ing. Ramiro Mora Jiménez

UNIVERSIDAD ANDINA DEL CUSCO
FACULTAD DE INGENIERÍACARRERA PROFESIONAL DE INGENIERÍA DE SISTEMAS
ALGORITMICA Y LABORATORIO DE PROGRAMACIÓN II

Un árbol binario es una estructura recursiva. Cada nodo es la raíz de su propio
subárbol y tiene hijos, que son raíces de árboles, llamados subárboles derecho e
izquierdo del nodo, respectivamente.

Figura 3. Ejemplos
Algunos conceptos de la estructura de datos tipo árbol:
• Nodo Padre de un nodo Nes aquel que apunta al mismo. En un árbol cada nodo sólo
puede tener un padre. En el ejemplo 1, A es el padre de B y C, y a su vez, B es el padre
de D.
• Nodo Hijo de otro nodo A es cualquier nodo apuntado por el nodo A. Un nodo puede
tener varios hijos. En el ejemplo 1, B y C son los nodos hijos de A y todos los nodos
tienen uno o dos hijos.
• Nodo Raíz es el único del árbol que no tienepadre. En la representación que hemos
utilizado, el nodo raíz es el que se encuentra en la parte superior del árbol: A.
• Hojas son todos los nodos que no tienen hijos. En la representación del ejemplo 1
son hojas los nodos situados en la parte inferior: D, G, H y F.
• Nodos Interiores son los nodos que no son ni el nodo raíz, ni nodos hoja. En el
ejemplo 1, son nodos interiores B, C y E.
•Camino es una secuencia de nodos, en el que dos nodos consecutivos cualesquiera
son padre e hijo. En el ejemplo 1 A-B-D es un camino, al igual que E-G y C-E-H.
• Rama es un camino desde el nodo raíz a una hoja. En el ejemplo 1, A-C-E-G y AC-F
son ramas.
• Altura es el máximo número de nodos de las ramas del árbol. Dicho en otros
términos, el máximo número de nodos que hay que recorrer parallegar de la raíz a una
de las hojas. La altura del árbol del ejemplo 1 es 4, ya que esa es la longitud de la rama
A-C-E-H, que junto a A-C-E-G son las dos más largas.
Ing. Ramiro Mora Jiménez

UNIVERSIDAD ANDINA DEL CUSCO
FACULTAD DE INGENIERÍA
CARRERA PROFESIONAL DE INGENIERÍA DE SISTEMAS
ALGORITMICA Y LABORATORIO DE PROGRAMACIÓN II
• Grado es el número máximo de hijos que tienen los nodosdel árbol. Así, en el
ejemplo anterior el árbol es de grado dos. Démonos cuenta de que una lista no es más
que un árbol de grado uno, tal y como podemos ver en los ejemplos 2 y 3.
• Nivel de un nodo, es el número de nodos del camino desde la raíz hasta dicho nodo.
En el árbol del ejemplo 1, A tiene nivel 1; B y C tienen nivel 2; D, E y F tienen nivel 3 y G
y H tienen nivel 4.
Existen...