arboles binario

ARBOLES
ESTRUCTURAS DE DATOS
2006

DEFINICION
Un árbol (tree) es un conjunto finito de
nodos.
Es una estructura jerárquica
aplicable sobre una colección de elementos
u objetos llamados nodos; uno de los cuales
es conocido como raíz.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

Los árboles representan las estructuras no
lineales y dinámicas. Nolineales, puesto
que a cada elemento del árbol pueden
Dinámicas,
seguirle varios elementos.
puesto que la estructura árbol puede
cambiar durante la ejecución del programa.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

EJEMPLOS DE ARBOLES

Figura 1 :Árboles

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006CARACTERISTICAS Y PROPIEDADES DE
LOS ÁRBOLES EN GENERAL
Todo árbol que no es vacío, tiene un único nodo raíz.
Un nodo X es descendiente directo de un nodo Y, si el nodo X
apunta al nodo Y. X es hijo de Y.
Un nodo X es antecesor directo de un nodo Y, si el nodo X apunta
al nodo Y. X es el padre de Y.
Se dice que todos los nodos que son descendientes directos
(hijos) de un mismo nodo (padre), sonhermanos.
Todo nodo que no tiene ramificaciones (hijos) se conoce con el
nombre de terminal u hoja.

Todo nodo que no es raíz, ni terminal u hoja se conoce con
el nombre de interior.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

CARACTERISTICAS Y PROPIEDADES DE
LOS ÁRBOLES EN GENERAL

Grado es el número de descendientes directos de un
determinado nodo.Grado del árbol es el máximo grado de todos
los nodos del árbol.
Nivel es el número de arcos que deben ser recorridos para
llegar a un determinado nodo. Por definición la raíz tiene nivel 1.
Altura del árbol es el máximo número de niveles de todos los
nodos del árbol.
Rama es un camino desde el nodo raíz a una hoja.

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006Figura 2 :Árbol General

A raíz del árbol
B es el hijo de A. C es hijo de A.
B es padre de D. D es padre de I.
B y C son hermanos. D, E, F son hermanos.
I, E, J, K, G, L son hojas.
B, D, F, C y H son nodos interiores.
Nivel del nodo A es 1. Nivel del nodo E es 3.
La altura del árbol es 4.

El grado de nodo A es 2
El grado de nodo B es 3
El grado de nodo C es 2
El grado de nodo Des 1
El grado de nodo E es 0
Grado del árbol es 3

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

ÁRBOLES BINARIOS
Definición 1:
Un árbol binario es un árbol en el que cada nodo no puede tener mas
de dos hijos o descendientes. Es un árbol de grado 2.
Definición 2:
Un árbol binario es un conjunto finito de nodos, el cual puede ser vacío
o un conjuntoque consta de un nodo raíz enlazado a dos árboles
binarios disjuntos denominados subárbol izquierdo y subárbol derecho.

Figura 3 :Árboles Binarios

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA
En un árbol binario los hijos se conocen como hijo izquierdo e hijo
derecho
Un nodo que no tiene hijos se denomina hoja. En lafigura 4 B, C
son hojas.
El nodo raíz se dice que está en el nivel O en el árbol. Los nodos B y
C están en el nivel 1. (figura 4)
Altura del árbol se define como el nivel más alto del árbol. En la
figura 4 la altura del árbol es 2.

Figura 4 :Árbol Binario

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA
Un árbol binario estábalanceado (equilibrado) si cada nodo tiene
exactamente dos hijos o no tiene hijos y si cada hoja está al mismo
nivel.

Figura 5 :Árbol Binario Equilibrado

Figura 6 :Árbol Binario no Equilibrado

Ing. M.Sc. Fulbia Torres
Asignatura: Estructuras de Datos
Barquisimeto 2006

ÁRBOLES BINARIOS
TERMINOLOGIA
Los subárboles izquierdo y derecho de un árbol binario deben ser
subconjuntos...