Arboles Binarios

Árboles Binarios
ESTRUCTURA DE DATOS
Algoritmos, abstracción y objetos
Luis Joyanes Aguilar

Definición - 1
• Un árbol binario es un árbol en el que cada nodo no puede tener
más de dos hijos odescendientes.
• En particular, un árbol binario es un conjunto de nodos que es, o
bien el conjunto vacío, o un conjunto que consta de un nodo raíz
enlazado a dos árboles binarios disjuntos denominadossubárbol
izquierdo y subárbol derecho.
• Cada uno de estos subárboles es, a su vez, un árbol binario.

Definición - 2
• En un árbol binario los hijos se conocen como hijo izquierdo e
hijo derecho.

•
••
•

Un nodo que no tiene hijos se denomina hoja.
Los nodos con descendientes se denominan nodos interiores.
Cualquier nodo sin sucesores se denomina un nodo terminal.
La altura del árbol se define comoel nivel más alto del árbol.

Características - 1
• El nivel o profundidad de un nodo se define
como una cantidad mayor en uno al número
de sus ascendientes.
– Si n es la raíz de un árbol T, entoncesestá en el
nivel 1.
– Si n no es la raíz de T, entonces su nivel es
mayor que el nivel de su padre.

• La altura de un árbol es el número de nodos
en el camino más largo desde la raíz a una
hoja;dicho de otro modo, la altura de un
árbol es el número de niveles distintos.
– Si T es vacío, entonces la altura es O.
– Si T no es vacío, entonces su altura es igual al
nivel máximo de sus nodos.Características - 2
• Un árbol binario lleno de altura h tiene todas sus hojas
a nivel h y todos los nodos que están a nivel menor que
h tiene cada uno dos hijos (cada nodo tiene o dos hijos
o ninguno sies una hoja).
– Si T está vacío, entonces T es un árbol binario lleno de
altura O.
– Si no está vacío y tiene altura h > 0, entonces T es un árbol
binario lleno si los subárboles de la raíz son ambosárboles
binarios llenos de altura h - 1.

Características - 3
• Un árbol binario completo de altura h es un árbol binario que está
relleno a partir del nivel h - 1, con el nivel h relleno de...