sábado, 15 de noviembre de 2008

UNIVERSIDAD DE PANAMÁ
FACULTAD DE INFORMÁTICA ELECTRÓNICA Y COMUNICACIÓN

BUSQUEDA DE ÁRBOLES BINARIO
PROYECTO # 1
II SEMESTRE

PRESENTADO A:
PROF. DONNA ROPER


PREPARADO POR:
GIL, YAREMIS 8-783-1762
PEREZ, LUIS 8-795-1687

FECHA DE ENTREGA:
11 DE NOVIEMBRE 2008



INTRODUCCIÓN


En el siguiente proyecto estaremos hablando que son la búsqueda de árboles binarios su definición y su formación desde que empiezan hasta donde terminan, conociendo sus nodos, el grado de un árbol, la determinación de su altura. Teniendo en cuenta que todo árbol empieza desde la raíz y desde allí la formación de sus hojas, sus características más cocidas, su búsqueda así como el recorrido del un árbol binario en sus tres formas que son: inorden, preorden y posorden.
También les presentamos como insertar un árbol binario, el procedimiento adecuado de borrado de un árbol, su definición y ejemplo aplicado en lenguaje c++.















CONCEPTO DE ÁRBOLES BINARIOS

Un árbol es una estructura jerárquica no lineal en la que cada nodo puede apuntar a uno o varios nodos. Compuesta por un dato y varios árboles.
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 dos hijos (subárboles). Se conoce el nodo de la izquierda como hijo izquierdo y el nodo de la derecha como hijo derecho.
Árbol binario


CARACTERÍSTICAS DE ÁRBOLES BINARIOS

Orden: es el número potencial de hijos que puede tener cada elemento de árbol. De este modo, diremos que un árbol en el que cada nodo puede apuntar a otros dos es de orden dos, si puede apuntar a tres será de orden tres, etc.
Grado: el número de hijos que tiene el elemento con más hijos dentro del árbol. En el árbol del ejemplo, el grado es tres, ya que tanto 'A' como 'D' tienen tres hijos, y no existen elementos con más de tres hijos.
Nivel: se define para cada elemento del árbol como la distancia a la raíz, medida en nodos. El nivel de la raíz es cero y el de sus hijos uno. Así sucesivamente. En el ejemplo, el nodo 'D' tiene nivel 1, el nodo 'G' tiene nivel 2, y el nodo 'N', nivel 3.
Altura: la altura de un árbol se define como el nivel del nodo de mayor nivel. Como cada nodo de un árbol puede considerarse a su vez como la raíz de un árbol, también podemos hablar de altura de ramas. El árbol del ejemplo tiene altura 3, la rama 'B' tiene altura 2, la rama 'G' tiene altura 1, la 'H' cero, etc.
Se añade un puntero: a cada nodo que apunte al nodo padre. De este modo podremos avanzar en dirección a la raíz, y no sólo hacia las hojas.
Nodo raíz: es donde se parte el desarrollo de un árbol.
Peso: Es el número de nodos del árbol sin contar la raíz.
· Longitud de camino: Es el número de arcos que deben ser recorridos para llegar desde la raíz al nodo X. Por definición la raíz tiene longitud de camino 1, y sus descendientes directos longitud de camino 2 y así sucesivamente.
· Hoja: Se le llama hoja o terminal a aquellos nodos que no tienen ramificaciones (hijos).
· Nodo anterior: Es un nodo que no es raíz ni terminal.
Hijo: X es hijo de Y, sí y solo sí el nodo X es apuntado por Y. También se dice que X es descendiente directo de Y.
· Padre: X es padre de Y sí y solo sí el nodo X apunta a Y. También se dice que X es antecesor de Y.
RECORRIDO DE LOS ÁRBOLES BINARIOS:
El recorrido en un árbol binario permite rescatar los datos en formas diferentes. Aunque existen varias maneras de hacerlo, aquí se verán las más conocidas: inorden, preorden, postorden.
Una de los recorridos más usados (inorden) es el que rescata los datos en forma ordenada (de menor a mayor).
La técnica que usualmente se usa para hacer el recorrido, es ir almacenando los datos en una estructura lineal: Cola, Lista o Pila.
Ø inorden: recorrer en inorden el subárbol izquierdo, visitar el elemento de la raíz y luego recorrer en inorden el subárbol derecho.
Ø preorden: visitar el elemento de la raíz, recorrer en preorden el subárbol izquierdo y luego recorrer en preorden el subárbol derecho.
Ø postorden: recorrer en postorden el subárbol izquierdo, luego recorrer en postorden el subárbol derecho y finalmente visitar el elemento de la raíz.

Como Buscar árboles:
La búsqueda consiste acceder a la raíz del árbol, si el elemento a localizar coincide con éste la búsqueda ha concluido con éxito, si el elemento es menor se busca en el subárbol izquierdo y si es mayor en el derecho. Si se alcanza un nodo hoja y el elemento no ha sido encontrado se supone que no existe en el árbol. Cabe destacar que la búsqueda en este tipo de árboles es muy eficiente, representa una función logarítmica. La búsqueda de un elemento en un ABB (Árbol Binario de Búsqueda) se puede realizar de dos formas, iterativa o recursiva.
Como Borra árboles:
Borrar un nodo sin hijos ó nodo hoja: simplemente se borra y se establece a nulo el apuntador de su padre.
Borrar un nodo con un subárbol hijo: se borra el nodo y se asigna su subárbol hijo como subárbol de su padre.
Borrar un nodo con dos subárboles hijo: la solución está en reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden y posteriormente borrar este nodo. Su predecesor en inorden será el nodo más a la derecha de su subárbol izquierdo (mayor nodo del subarbol izquierdo), y su sucesor el nodo más a la izquierda de su subárbol derecho (menor nodo del subarbol derecho). En la siguiente figura se muestra cómo existe la posibilidad de realizar cualquiera de ambos reemplazos
Como insertar árboles:
La inserción es similar a la búsqueda, por tanto también es posible una versión iterativa con los mismos resultados que una recursiva. Se procede de la siguiente forma, si el árbol pasado como parámetro está vacío se crea un nuevo nodo para él cuyo contenido correspondiente sería el elemento a insertar. Si no lo está, se comprueba si el elemento dado es menor que el de la raíz del árbol con lo que se inserta en el subárbol izquierdo, o mayor, insertándose en el subárbol derecho. Se observa que de este modo las inserciones se realizan en las hojas, es la forma más simple de llevar a cabo esta tarea, aunque no la única. Además, permite mantener la estructura (forma) del árbol anterior a la inserción.






EJEMPLO APLICADO



1. Búsqueda de arboles:
Ejemplo de versión iterativa en el lenguaje de programación C, suponiendo que estamos buscando una clave alojada en un nodo donde está el correspondiente "dato" que precisamos encontrar:data Buscar_ABB(abb t,clave k) { abb p; dato e; e=NULL; p=t; if (!estaVacio(p)) { while (!estaVacio(p) && (p->k!=k) ) { if (k <>k) { p=p->l; } if (p->k < p="p-">r; } } if (!estaVacio(p) &&(p->d!=NULL) ) { e=copiaDato(p->d); } } return e;}
2. Para insertar árboles: void insertar(tArbol **a, int elem){ if (*a == NULL) { *a = (tArbol *) malloc(sizeof(tArbol)); (*a)->clave = elem; (*a)->hIzquierdo = NULL; (*a)->hDerecho = NULL; } else if ((*a)->clave <>hDerecho, elem); else if ((*a)->clave > elem) insertar(&(*a)->hIzquierdo, elem);}

Para borrar árboles:
void borrar(tArbol **a, int elem){ void reemplazar(tArbol **a, tArbol **aux); tArbol *aux; if (*a == NULL) return; if ((*a)->clave <>hDerecho, elem); else if ((*a)->clave > elem) borrar(&(*a)->hIzquierdo, elem); else if ((*a)->clave == elem) { aux = *a; if ((*a)->hIzquierdo == NULL) *a = (*a)->hDerecho; else if ((*a)->hDerecho == NULL) *a = (*a)->hIzquierdo; else reemplazar(&(*a)->hIzquierdo, &aux); free(aux); }} void reemplazar(tArbol **a, tArbol **aux){ if ((*a)->hDerecho == NULL) { (*aux)->clave = (*a)->clave; *aux = *a; *a = (*a)->hIzquierdo; } else reemplazar(&(*a)->hDerecho, aux);}




Recorido de árboles:

#include
#include

/* declaración de tipos */

typedef int TipoC;
typedef int TipoA;

/* archivos necesarios */

#include "tadCola.h"
#include "tadArbin.h"
#include "funcArbin.h"

/* función específica de comparación que
será pasada como parámetro a la función
insertarArbin */

int mayor(int a , int b)
{
return a > b;
}

int main()
{

Arbin a = arbinVacio();
Cola c = inicCola();

int arr[] = { 60, 30 , 80, 10 , 50 , 55 };

/* Se insertan los datos en el árbol*/

for(int i = 0; i < a =" insertarArbin(a,arr[i],mayor);" aux =" infoCola(c);" raiz =" raizArbin(a);" raiz =" raizArbin(a);" raiz =" raizArbin(a);">izq);
destruirArbin(a->der);
free(a);
}
}









































CONCLUSIÓN





En este proyecto podemos concluir que en la búsqueda de un árbol binario se debe llevar un orden empezando desde la raíz.
Se debe tener en cuenta y tener presente las partes en que están formados los árboles binarios sus nodos, hojas u hijos.
Al igual que los demás problemas en c++ un árbol tiene igual semejanza.
Concluimos también que para poder resolver un árbol binario se identificar primeros sus partes y que se quiere realizar, ya sea, una búsqueda, una inserción, o un borrado, etc.

No hay comentarios: