Arboles Binarios

En ciencias de la computación, un árbol binario es una estructura de datos en la cual cada nodo:
No tiene hijos (hoja).
Tiene un hijo izquierdo y un hijo derecho.
Tiene un hijo izquierdo.
Tiene un hijo derecho.
Usos comunes de los árboles binarios son los árboles binarios de búsqueda, los montículos binarios y Codificación de Huffman.

En teoría de grafos, se usa la siguiente definición: «Un árbol binario es un grafo conexo, acíclico y no dirigido tal que el grado de cada vértice no es mayor a 3». De esta forma sólo existe un camino entre un par de nodos.
Un árbol binario con enraizado es como un grafo que tiene uno de sus vértices, llamado raíz, de grado no mayor a 2. Con la raíz escogida, cada vértice tendrá un único padre, y nunca más de dos hijos. Si reusamos el requerimiento de la conectividad, permitiendo múltiples componentes conectados en el grafo, llamaremos a esta última estructura un bosque.
Tipos de árboles binarios [editar]

Un árbol binario es un árbol con raíz en el que cada nodo tiene como máximo dos hijos.
Un árbol binario lleno es un árbol en el que cada nodo tiene cero o dos hijos.
Un árbol binario perfecto es un árbol binario lleno en el que todas las hojas (vértices con cero hijos) están a la misma profundidad (distancia desde la raíz, también llamada altura)
A veces un árbol binario perfecto es denominado árbol binario completo. Otros definen un árbol binario completo como un árbol binario lleno en el que todas las hojas están a profundidad n o n-1, para alguna n.
Un árbol binario es un árbol en el que ningún nodo puede tener más de dos subárboles. 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.


Recorrido en preorden
En este tipo de recorrido se realiza cierta acción (quizás simplemente imprimir por pantalla el valor de la clave de ese nodo) sobre el nodo actual y posteriormente se trata el subárbol izquierdo y cuando se haya concluido, el subárbol derecho


Recorrido en postorden
En este caso se trata primero el subárbol izquierdo, después el derecho y por último el nodo actual

Recorrido en inorden
En este caso se trata primero el subárbol izquierdo, después el nodo actual y por último el subárbol derecho. En un ABB este recorrido daría los valores de clave ordenados de menor a mayor

Recorridos en amplitud (o por niveles)
En este caso el recorrido se realiza en orden por los distintos niveles del árbol. Así, se comenzaría tratando el nivel 1, que sólo contiene el nodo raíz, seguidamente el nivel 2, el 3 y así sucesivamente.

Al contrario que en los métodos de recorrido en profundidad, el recorrido por niveles no es de naturaleza recursiva. Por ello, se debe utilizar una cola para recordar los subárboles izquierdos y derecho de cada nodo.

Métodos para almacenar árboles binarios

Los árboles binarios pueden ser construidos a partir de lenguajes de programación de varias formas. En un lenguaje con registros y referencias, los árboles binarios son construidos típicamente con una estructura de nodos y punteros en la cual se almacenan datos, cada uno de estos nodos tiene una referencia o puntero a un nodo izquierdo y a un nodo derecho denominados hijos. En ocasiones, también contiene un puntero a un único nodo. Si un nodo tiene menos de dos hijos, algunos de los punteros de los hijos pueden ser definidos como nulos para indicar que no dispone de dicho nodo. En la figura adjunta se puede observar la estructura de dicha implementación.

Los árboles binarios también pueden ser almacenados como una estructura de datos implícita en arreglos, y si el árbol es un árbol binario completo, este método no desaprovecha el espacio en memoria. Tomaremos como notación la siguiente: si un nodo tiene un índice i, sus hijos se encuentran en índices 2i + 1 y 2i + 2, mientras que sus padres (si los tiene) se encuentra en el índice(partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.