Arboles Binarios

Arbol 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.

Aqui les muestro un arbol en dibujo, ubicando la Raiz y los nodos.

Existen diferentes tipos de arboles binarios, aqui les dejo la definicion.
*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).

Recorridos sobre los arboles binarios.
Existen distintos recorridos los cuales vimos hoy en clase.
Explicare cada uno de ellos dando un ejemplo.

Preorden
Este tipo de recorrido se realiza, primeri se imprmi la Raiz, depues el hijo izquierdo(subarbol izquierdo), y por ultimo hijo derecho(subarbol derecho).
Lo correspondiente al recorrido preorden de la imagen anterior sería:

2, 6, 5, 2, 9,11,7, 8, 3.


Postorden
Este tipo de recorrido se realiza, prmiero el hijo izquierdo, hijo derecho y al final la raiz.
Lo correspondiente al recorrido Postorden de la imagen sería:

5, 9, 11, 2, 6, 3, 8, 7, 2.


Inorden.
Este tipo de recorrido se realiza primero hijo izquierdo, raiz, y al final hijo derecho.
Lo correspondiente al recorrido Inorden de la imagen sería:

5, 6, 9, 2, 11, 2, 7, 8, 3.

Amplitud o por niveles.
En este caso se realiza en orden por los distintos niveles del arbol, se comenzara con el nivel 1, que solo es la raiz, seguidamente el nivel 2, el 3 y así sucesivamente.
2, 6, 7, 5, 2, 8, 9, 11, 3.



Karla Garcia