5.1.1 Clasificacion de arboles

Árbol binario

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo siempre tiene un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario"). Si algún hijo tiene como referencia a null, es decir que no almacena ningún dato, entonces este es llamado un nodo externo. En el caso contrario el hijo es llamado un nodo interno. Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman. 

Un árbol ordenado es aquel en el que las ramas  de los nodos del árbol están  ordenadas. Los árboles ordenados de grado 2 son de especial interés puesto que  representan una de las estructuras de  datos más importantes en computación, conocidas como  árboles binarios. En un árbol binario cada nodo puede tener como máximo dos subárboles y  siempre es necesario distinguir entre el subárbol izquierdo y el subárbol derecho.

Formalmente podemos definir un árbol binario de tipo T como una estructura homogénea que es la concatenación de un elemento de tipo T, llamada raíz, con dos árboles binarios disjuntos. Una forma  particular de árbol binario puede ser la estructura vacía. 

Los árboles binarios  se clasifican en cuatro tipo que son : distintos, similares, equivalentes y completos. Cuando dos  árboles binarios se dice que son similares si tiene la misma estructura y son equivalentes  si son similares  y contienen la misma información. En caso contrario  se dice que  estos árboles son distintos. Un arbol binario esta equilibrado  si la altura de los dos subárboles  de cada nodo del arbol  se diferencia en una unidad como máximo. 

El procedimiento de arbol binarios equilibrados es mas sencillo que los árboles no equilibrados. 

Se define un árbol  completo  (lleno)  como  un  árbol  en  el  que  todos  sus  nodos, excepto los del ultimo nivel, tienen dos hijos ; el subárbol izquierdo y el subárbol derecho.

 Se puede calcular el numero de nodos de un arbol binario completo de altura h, aplicando la siguiente formula  

Un árbol binario t es un conjunto finito de nodos tales que

1. t es vacío
2. t consiste de un nodo r, llamado raíz de t y dos árboles disyuntos t₁ y t₂ llamados subárboles izquierdo y subárbol derecho.

Figura 6.2. Árboles binariosa) subárbol derecho vacío.

b) subárbol izquierdo vacío. c) un árbol binario.

Dos árboles son distintos cuando sus estructuras son diferentes. en la figura 6.2. todos los árboles son distintos.

Dos árboles son similares cuando sus estructuras son idénticas pero la información de los nodos es diferente.

Dos árboles son equivalentes cuando son similares y además tienen la misma información.

Figura 6.3. a) árboles distintos. b) árboles equivalentes

 Árboles Binarios Completos

Un árbol binario es completo cuando todos los nodos de un árbol, excepto los del ultimo nivel tienen dos hijos: subárbol izquierdo y subárbol derecho.

Figura 6.4. Árboles Binarios

El numero de nodos en un árbol binario completo de altura h es:

nodos: 2^h - 1.

Conversión de Árboles No Binarios a Binarios

Debido a que los árboles binarios son estructuras muy estudiadas, por esta razón en muchas aplicaciones se convierten árboles no binarios en árboles binarios. para realizar la conversión se siguen las siguientes reglas:

1. Los nodos hermanos se enlazan en forma horizontal.
2. El nodo raíz se enlaza en forma vertical con el subárbol izquierdo.
3. Se gira la estructura resultante 450.

Ejemplo: