Definición:
Un Árbol Binario es un conjunto de finito de Elementos, de nombre Nodos de forma que:
El Árbol Binario es Vació si no tiene ningún elemento en él.
El Árbol Binario contiene un Nodo Raíz y los dos que parten de él, llamados Nodo Izquierdo y Nodo Derecho.
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 subárbol izquierdo y derecho del subárbol en cuestión.
Cada nodo se representa gráficamente de la siguiente manera:
Clasificación de Arboles Binarios:
Existen cuatro tipos de árbol binario:
A. B. Distinto.
A. B. Similares.
A. B. Equivalentes.
A. B. Completos.
Descripción de los Arboles Binarios:
A. B. DISTINTO: Cuando en sus estructuras la distribución de nodos y arcos son diferentes.
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. EQUIVALENTES: 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
El Recorrido «Pre-Orden
» (raíz, izquierdo, derecho) lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en la Raíz, después viaje a través del Nodo Izquierdo y después a través del Nodo Derecho.
El Recorrido «In-Orden»
(izquierdo, raíz
, derecho) lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después la Raíz y finalmente viaja a través del Nodo Derecho.
El recorrido «Postorden»
(izquierdo, derecho, raíz) lo recorre de la siguiente manera, viaje a través del Árbol Binario desplegando el Contenido en el Nodo Izquierdo después el Nodo Derecho y finalmente viaja a través de la Raíz.
En general, la diferencia entre preorden, inorden y postorden es cuándo se recorre la raíz. En los tres, se recorre primero el sub-árbol izquierdo y luego el derecho.
En preorden, la raíz se recorre antes que los recorridos de los subárboles izquierdo y derecho
En inorden, la raíz se recorre entre los recorridos de los árboles izquierdo y derecho, y
En postorden, la raíz se recorre después de los recorridos por el subárbol izquierdo y el derecho
Preorden (antes), inorden (en medio), postorden (después).
ESTRUCTURA DE DATOS 