ARBOLES BINARIOS

ARBOLES
Arboles: un árbol es un conjunto finito de uno o más nodos tales que:
a) existe un nodo llamado raíz
b) el resto de los nodos están partidos en n>=0 conjuntos disjuntos T1….Tn los cuales son por sí mismos un árbol. T1…Tn se denominan subárboles de la raíz.

Existen muchos términos que se utilizan cuando se habla de árboles. Consideremos el siguiente árbol:


Arboles Binarios.

Un árbol binario es una estructura de datos muy importante que se utiliza en muchos algoritmos. Este tipo de árbol se caracteriza por el hecho de que cada nodo tiene un máximo de dos hijos. Al utilizar árboles binarios se habla de subárbol de la derecha y subárbol de la izquierda.

Definición: Un Arbol Binario es un conjunto finito de nodos el cual es o bien vacío o consta de una raíz y dos árboles binarios disjuntos llamados subárboles derecho e izquierdo.


Arbol Binario Desviado
Arbol Binario Casi Completo

Lema 1. El máximo número de nodos en el nivel i de un árbol es 2 i-1. El número máximo de nodos que puede tener un árbol de profundidad K es 2k -1, k>0.

Nota: en cualquier nivel los nodos deben numerarse de izquierda a derecha.

Un árbol binario con n nodos y una profundidad k está completo si y solo si sus nodos corresponden a los nodos que estan numerados del 1 a n en un árbol binario completo de profundidad k.

Lema 2. Si se tiene un árbol binario completo de n nodos; representado en forma secuencial entonces para cualquier nodo i, 1>=i>=n tenemos:

a) Padre [i] se encuentra en └ i/2┘ si i≠1. Cuando i=1, el nodo es la raíz y por lo tanto no tiene padre.
b) Hijo_Izq [i] se encuentra en 2i, si 2i<=n. Si 2i>n, entonces no existe hijo izquierdo.
c) Hijo_Der[i] se encuentra en 2i+1, si 2i+1n, entonces no existe hijo derecho.