Trabajos de ingenieria sistemas

Árbol binario

1

Árbol 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 hijoes 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.

Definición de teoría de grafos
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 unpar 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 binariosUn árbol binario sencillo de tamaño 9 y altura 3, con un nodo raíz cuyo valor es 2.

• 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 doshijos (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 puntA el puntero que apunta al árbol de tipo tArbol: struct celda { telemento dato; struct celda *izdo, *dcho; }; typedef struct celda*arbolbin; Estructura con arreglo indexado: typedef struct tArbol {

Árbol binario int clave; int 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ícitaa 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 enpreorden. La estructura para este caso sería por tanto: int árbol[NUMERO_DE_NODOS];

2

Recorridos sobre árboles binarios
Recorridos en profundidad
El método de este recorrido es tratar de encontrar de la cabecera a la raíz en nodo de unidad binaria. Ahora pasamos a ver la implementación de los distintos recorridos: Recorrido en preorden En este tipo de recorrido se realiza cierta acción (quizássimplemente 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. Otra forma para entender el recorrido con este metodo seria seguir el orden: nodo raiz, nodo izquierda, nodo derecha. En el árbol de la figura el recorrido en preorden sería: 2, 7, 2, 6, 5, 11, 5, 9 y 4. void...