arboles binarios

Arboles Binarios
Presentación
Edinson Angeles ----> 2013-6117
Ellis P. Martínez ----> 2012-2456

INTRODUCCIÓN
A continuación estaremos profundizando sobre la estructura de datos no lineales llamada
árbol. Esta estructura de datos se utiliza principalmente para representar datos con una
relación jerárquica entre sus elementos, ejemplo Registro, Árboles genealógicos y Tabla de
contenidos. Vamos aprofundizar en un tipo especial de árbol llamado árbol binario, el cual
puede ser implementado fácilmente en la computadora, aunque en un árbol puede parecer
muy restrictivo. También se va a ampliar sobre arboles más generales y puntos con relación
a los arboles binarios. De los cuales veremos arboles binarios de búsqueda, arboles
generales y representación de árboles generales en la computadora ycorrespondencia entre
los arboles generales y arboles binarios.

ÁRBOL BINARIO
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárbol. 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.

A

A

A
B

B

B

C
C

E

D

F

D

E
H

G

A

B

C

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. Un árbol binario se divide en tres subconjuntos:
[R] ------> Nodo Raíz.
[I1, I2,…, In] subárboles izquierdo de R.
[D1, D2,…, Dn] subárboles derecho de R.

No mas de 2
subarboles
por nodo
Estrucruras
de controlde
informacion

recursivos

caracteristicas

Cada nodo
puede tener
0, 1, 2 hijos

Puede
contener de
1 a nn
Cada nodo
puede serla
raiz de un
subarbol

Equilibrio
La distancia de un nodo la nodo raíz determina la eficiencia con la puede ser localizado.
Por ejemplo, dado cualquier nodo de un árbol, a sus hijos se puede acceder siguiendo solo
un camino de bifurcación o de ramas, el que conduce al nododeseado. De modo similar,
los nodo a nivel 2 un árbol solo puede ser accedidos siguiendo solo dos ramas del árbol.
La característica anterior nos conduce a una característica muy importante de un árbol
binario, su balance equilibrio, se calcula su factor de equilibrio. El factor de equilibrio de
un árbol binario es la diferencia en altura entre los subárboles derecho e izquierdo. Si la
altura delsubárbol derecho es hD, entonces el factor de equilibrio del árbol B se determina
por la siguiente formula.

B = hd - hi

Un árbol está perfectamente equilibrado si su equilibrio o balance es cero y sus subárboles
son también perfectamente equilibrados. Dado que esta definición ocurre raramente se
aplica una definición aleatoria. Un árbol binario está equilibrado si la altura de sus
subárbolesdifieren en no más de uno (su factor de equilibrio es -1, 01, +1) y sus subárboles
son también equilibrados.

Árboles binarios completos
Un árbol binario completo de profundidad n es un árbol en el que para cada nivel,
del 0 al nivel n.1 tiene u conjunto lleno de nodos y todos los nodos hoja a nivel n
ocupan las posiciones más a la izquierda del árbol.
Un árbol binario completo que contiene 2nnodos a nivel n es un árbol lleno. Un
árbol lleno es un árbol binario que tiene el máximo número de entradas para su
altura. Esto sucede cuando el último nivel está lleno.

Crear árbol

construir

Es vacío

Raíz
Devuelve el nodo
raiz

Inicia el arbol
como vacio

Crear un arbol con
un elemento raiz y
dos ramas,
izquierda y
derecha que son,
a su vez arboles

Comprueba si el
arbol no tiene
nodo

arIzquierda

Obtiene la rama
subarbol
izquerdo de un
arbol dado

Derecho

Obtiene la rama
subarbol
Derecho de un
arbol dado

Borrar

Elimina del arbol
el nodo con un
alemento
determinado

Pertenece

Determina si un
elemento se
encuentra en el
arbol

Estructura de un árbol binario
La estructura de un árbol binario se construye con nodos. Cada nodo debe contener
el campo dato (datos a almacenar) y dos...