Estrucutura de datos

Solo disponible en BuenasTareas
  • Páginas : 6 (1320 palabras )
  • Descarga(s) : 0
  • Publicado : 19 de diciembre de 2010
Leer documento completo
Vista previa del texto
Estructuras No Lineales

Concepto Árbol
Árbol general: Es una estructura jerárquica aplicada sobre una colación de elementos u objetos llamados nodos, uno de los cuales es conocido como raíz y en conjunto tienen una relación o parentesco entre ellos
Árbol binario: Es un conjunto Finito de nodos en el cual cada nodo tiene como máximo 2 subárbols, llamados sub árbol izquierdo y derecho.Clasificación De Arboles
Árbol binario formal:
1.- t es vacio en cuyo caso se llama árbol nulo
2.- T Tiene un nodo Distinguido de R llamado raíz de T, y los restantes nodos de T forman un par ordenado de arboles binarios T1 que es el subárbol izquierdo y T2 el subárbol derecho.
Clasificación de arboles binarios:
1.-arbol binario distinto: Se dice que un árbol es distinto cuando suestructura grafica es diferente.
2.-arbol binario similar.- Se dice que un árbol es similar cuando su estructura grafica es idéntica pero la información que contiene entre sus nodos es diferente.
3.-arbol binario equivalente.-Son aquellos que su estructura grafica es idéntica pero además la información entre sus nodos.
4.-arbol binario completo.-Son aquellos que todos sus nodos excepto el ultimonivel tienen sus dos hijos.
5.-arbol binario lleno: Es aquel que tiene su numero máximo de posibles nodos.

Operaciones Basicas Arboles Binarios
Operaciones de árboles.
Las operaciones comunes en árboles son:
• Enumerar todos los elementos.
• Buscar un elemento.
• Dado un nodo, listar los hijos (si los hay).
• Borrar un elemento.
• Eliminar un subárbol (algunas veces llamadapodar).
• Añadir un subárbol (algunas veces llamada injertar).
• Encontrar la raíz de cualquier nodo.

Creacion Arboles Binarios
Hasta el momento se ha visto la declaración y recorrido de un árbol binario. Sin embargo no se ha estudiado ningún método para crearlos. A continuación se estudia un método para crear un árbol binario que no tenga claves repetidas partiendo de su recorrido enpreorden e inorden, almacenados en sendos arrays.
Antes de explicarlo se recomienda al lector que lo intente hacer por su cuenta, es sencillo cuando uno es capaz de construir el árbol viendo sus recorridos pero sin haber visto el árbol terminado.
Partiendo de los recorridos preorden e inorden del árbol de la figura 1 puede determinarse que la raíz es el primer elemento del recorrido en preorden. Eseelemento se busca en el array inorden. Los elementos en el array inorden entre izq y la raíz forman el subárbol izquierdo. Asimismo los elementos entre der y la raíz forman el subárbol derecho. Por tanto se tiene este árbol:
 

A continuación comienza un proceso recursivo. Se procede a crear el subárbol izquierdo, cuyo tamaño está limitado por los índices izq y der. La siguiente posición en elrecorrido en preorden es la raíz de este subárbol. Queda esto:

El subárbol b tiene un subárbol derecho, que no tiene ningún descendiente, tal y como indican los índices izq y der. Se ha obtenido el subárbol izquierdo completo de la raíz a, puesto que b no tiene subárbol izquierdo:

 
Después seguirá construyéndose el subárbol derecho a partir de la raíz a.
La implementación de laconstrucción de un árbol partiendo de los recorridos en preorden y en inorden.
Insercion Arboles Binarios

La inserción tampoco es complicada. Es más, resulta practicamente idéntica a la búsqueda. Cuando se llega a un árbol vacío se crea el nodo en el puntero que se pasa como parámetro por referencia, de esta manera los nuevos enlaces mantienen la coherencia. Si el elemento a insertar ya existeentonces no se hace nada.
void insertar(tarbol **a, int elem)
{
if (*a == NULL) {
*a = (arbol *) malloc(sizeof(arbol));
(*a)->clave = elem;
(*a)->izq = (*a)->der = NULL;
}
else if ((*a)->clave < elem) insertar(&(*a)->der, elem);...
tracking img