Árbol binario

Árbol binario Concepto: En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo puede tener un hijo izquierdo y un hijo derecho. No pueden tener más de dos hijos (de ahí el nombre "binario").

Árbol binario. A los arboles ordenados de grado dos se les conoce como arboles binarios ya que cada nodo del árbol no tendrá más de dos descendientes directos. Las aplicaciones de los arboles binarios son muy variadas ya que se les puede utilizar para representar una estructura en la cual es posible tomar decisiones con dos opciones en distintos puntos.

La representación gráfica de un árbol binario es la siguiente:

Representación en memoria

Hay dos formas tradicionales de representar un árbol binario en memoria:

• Por medio de datos tipo punteros también conocidos como variables dinámicas o listas.
• Por medio de arreglos.
• Sin embargo la más utilizada es la primera, puesto que es la más natural para tratar este tipo de estructuras.
• Los nodos del árbol binario serán representados como registros que contendrán como mínimo tres campos. En un campo se almacenará la información del nodo. Los dos restantes se utilizarán para apuntar al subarbol izquierdo y derecho del subarbol en cuestión.

Algoritmo de creación

Procedimiento crear (q:nodo)

• inicio
• mensaje("Rama izquierda?")
• lee(respuesta)
• si respuesta = "si" entonces
• new(p)
• q(li) <-- nil
• crear(p)
• en caso contrario
• q(li) <-- nil
• mensaje("Rama derecha?")
• lee(respuesta)
• si respuesta="si" entonces
• new(p)
• q(ld)<--p
• crear(p)
• en caso contrario
• q(ld) <--nil
• fin
• INICIO
• new(p)
• raiz<--p
• crear(p)
• FIN

Clasificación

Existen cuatro tipos de árbol binario:.

• A. B. Distinto.
• A. B. Similares.
• A. B. Equivalentes.
• A. B. Completos.

A. B. distinto

Se dice que dos árboles binarios son distintos cuando sus estructuras son diferentes.

Ejemplo:

A. B. similares

Dos árboles binarios son similares cuando sus estructuras son idénticas, pero la información que contienen sus nodos es diferente.

Ejemplo:

A. B. equibalentes

Son aquellos árboles que son similares y que además los nodos contienen la misma información.

Ejemplo:

A. B.completos

Son aquellos árboles en los que todos sus nodos excepto los del ultimo nivel, tiene dos hijos; el subárbol izquierdo y el subárbol derecho.

Recorrido de un árbol binario

Hay tres maneras de recorrer un árbol: en inorden, preorden y postorden. Cada una de ellas tiene una secuencia distinta para analizar el árbol como se puede ver a continuación:

Inorden

• Recorrer el subarbol izquierdo en inorden.
• Examinar la raíz.
• Recorrer el subarbol derecho en inorden.

Preorden

• Examinar la raíz.
• Recorrer el subarbol izquierdo en preorden.
• recorrer el subarbol derecho en preorden.

Posorden

• Recorrer el subarbol izquierdo en postorden.
• Recorrer el subarbol derecho en postorden.
• Examinar la raíz.

Ejemplo de los diferentes recorridos en un árbol binario.

• Inorden: GDBHEIACJKF
• Preorden: ABDGEHICFJK
• Postorden: GDHIEBKJFCA

Arboles enhebrados

Existe un tipo especial de árbol binario llamado enhebrado, el cual contiene hebras que pueden estar a la derecha o a la izquierda. El siguiente ejemplo es un árbol binario enhebrado a la derecha.

• Árbol enhebrado a la derecha. Este tipo de árbol tiene un apuntador a la derecha que apunta a un nodo antecesor.
• Árbol enhebrado a la izquierda. Estos arboles tienen un apuntador a la izquierda que apunta al nodo antecesor en orden.

Árboles en montón

Esta sección consiste en transformar un bosque en un árbol binario. Entenderemos como bosque a un conjunto normalmente ordenado de dos o más árboles generales.

La serie de pasos que debemos seguir para lograr la conversión de un bosque en un árbol binario es la siguiente:

• Enlazar horizontalmente las raíces de los distintos árboles generales.
• Enlazar los hijos de cada nodo en forma horizontal (los hermanos).
• Enlazar verticalmente el nodo padre con el hijo que se encuentra más a la izquierda. Además debe eliminarse el vínculo de ese padre con el resto de sus hijos.
• Debe rotarse el diagrama resultante aproximadamente 45 grados hacia la izquierda y así se obtendrá el árbol binario correspondiente.

Fuente

• Arboles binarios. Disponible en: www.monografias.com

• Arboles binarios. Disponible en: www.utm.mx

• es.wikipedia.org.