arbol binario

Árbol binario
Commons-emblem-question book orange.svg
Este artículo o sección necesita referencias que aparezcan en una publicación acreditada, como revistas especializadas, monografías, prensa diaria o páginas de Internet fidedignas. Este aviso fue puesto el 2 de noviembre de 2011.
Puedes añadirlas o avisar al autor principal del artículo en su página de discusión pegando: {{subst:Avisoreferencias|Árbol binario}} ~~~~
Para otros usos de este término, véase Árbol binario (desambiguación).
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.

Índice [ocultar]
1 Definición de teoría de grafos
2 Tipos de árboles binarios
3 Implementación en C
4 Recorridos sobre árboles binarios
4.1 Recorridos en profundidad
4.1.1Recorrido en preorden
4.1.2 Recorrido en postorden
4.1.3 Recorrido en enorden
4.2 Recorridos en amplitud (o por niveles)
4.3 Creación de árboles a partir de los recorridos
5 Métodos para almacenar Árboles Binarios
6 Codificación de árboles n-arios como árboles binarios
7 Véase también
8 Enlaces externos
Definición de teoría de grafos[editar]

Un árbol binario sencillo de tamaño 9, 4niveles y altura 3 (altura = máximo nivel - 1), con un nodo raíz cuyo valor es 2.
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 solo 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 rehusamos 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 árbolbinario lleno es un árbol en el que cada nodo tiene cero o dos hijos, es decir su factor de equilibrio es 0.
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 binariocompleto 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.

Implementación en C[editar]
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),...