Arboles Binarios

Arboles Binarios

Árbol binario

De Wikipedia, la enciclopedia libre

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”). 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.

Tipos de árboles binarios

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. Implementación en C

Un árbol binario puede declararse de varias maneras. Algunas de ellas son:

Estructura con manejo de memoria dinámica, siendo el puntero que apunta al árbol de tipo tArbol:

typedef struct nodo {

    int clave;
    struct nodo *izdo, *dcho;

Nodo;

Estructura con arreglo indexado:

typedef struct tArbol

  int clave;
  tArbol hIzquierdo, hDerecho;
 tArbol;

tArbol árbol[NUMERO_DE_NODOS];

En el caso de un árbol binario casi-completo (o un árbol completo), puede utilizarse un sencillo arreglo de enteros con tantas posiciones como nodos deba tener el árbol. La información de la ubicación del nodo en el árbol es implícita a cada posición del arreglo. Así, si un nodo está en la posición i, sus hijos se encuentran en las posiciones 2i+1 y 2i+2, mientras que su padre (si tiene), se encuentra en la posición truncamiento((i-1)/2) (suponiendo que la raíz está en la posición cero). Este método se beneficia de un almacenamiento más compacto y una mejor localidad de referencia, particularmente durante un recorrido en preorden. La estructura para este caso sería por tanto:

int árbol[NUMERO_DE_NODOS];


Mis sitios nuevos:
Emprendedores
Politica de Privacidad