Trabajos

Solo disponible en BuenasTareas
  • Páginas : 5 (1116 palabras )
  • Descarga(s) : 4
  • Publicado : 19 de mayo de 2010
Leer documento completo
Vista previa del texto
 Árboles binarios.
Los árboles de grado 2 tienen una especial importancia. Se les conoce con el nombre de árboles binarios. Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formada por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz. 
En los apartados que siguen se considerarán únicamente árbolesbinarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cadanodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
Ejemplo:

 
Operaciones básicas.- Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol. Esta operación se considera entonces como un parámetro de una taré másgeneral que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol. 
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del procesodel siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5, 9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, ordencentral y postorden.
Preorden: Raíz, subárbol izquierdo y subárbol derecho.
Orden central: Subarbol izquierdo, raíz, subarbol derecho.
Postorden: Subarbol izquierdo, subarbol derecho, raíz.

Ejemplo:
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa

-------------------------------------------------
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 árbol binario lleno es un árbol en el que cada nodo tiene ceroo 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 aprofundidad 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 puededeclararse 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:
-------------------------------------------------
typedef struct tArbol
-------------------------------------------------
{
-------------------------------------------------
int clave;...
tracking img