Informática
Algoritmos de búsqueda
Introducción.
Una tabla o un archivo es un grupo de elementos, cada uno de los cuales se llama registro. Hay una llave asociada a cada registro, que se usa para diferenciar unos de otros. La asociacion entre un registro y su llave puede ser simple o compleja. En la forma mas simple, la llave esta contenida dentro del registro en un tramo a una distancia especifica del principio del mismo. Una llave de ese tipo es la llave interna o incluida.
En este trabajo, se veran las tecnicas de busqueda secuencial ordenada/desordenada, secuecial idexada, binaria e interpolacion. En cada una se mencionan su descripcion, sus venajas/desventajas, y algunas aplicaciones, por supuesto tambien se eran sus respectivos algritmos, ¿pero que es un algoritmo de busqueda?.
Un algoritmo de busqueda es un algoritmo que acepta un argumento a y trata de encontrar un registro cuya llave sea a. El algoritmo puede dar como resultado el registro entero o, lo que es mas comun, un apuntador a dicho registro.
Si la busqueda es infructuosa, con mucha frecuencia, es deseable agregar un nuevo registro con dicho argumento como llave. Un algoritmo que haga esto se le llama tabla busqueda o diccionario.
La busqueda en la cual toda la tabla esta de manera frecuente en la memoria principal se le llama busqueda interna, mientras que la busqueda en la que la mayor parte de la table esta en la memoria auxiliar se llama busqueda externa.
PARTE I:
Técnica Secuencial Ordenada/Desordenada.
1.1 Descripción de la técnica.
La búsqueda es el proceso de localizar un registro (elemento) con un valor de llave particular. La búsqueda termina exitosamente cuando se localiza el registro que contenga la llave buscada, o termina sin éxito, cuando se determina que no aparece ningún registro con esa llave.
Normalmente un archivo secuencial se almacena en bloques, en un orden secuencial simple de los registros. La organización física del archivo en una cinta o disco se corresponde exactamente con la ubicación lógica del archivo. En este caso, el procedimiento para ubicar los nuevos registros en un archivo de pila separado, llamado archivo de registro (log file) o archivo de transacciones. Periódicamente, se realiza una actualización por lotes que mezcla el archivo de registro con el archivo maestro para producir un nuevo archivo en secuencia correcta de claves.
Búsqueda secuencial, también se le conoce como búsqueda lineal. Supongamos una colección de registros organizados como una lista lineal. El algoritmo básico de búsqueda secuencial consiste en empezar al inicio de la lista e ir a través de cada registro hasta encontrar la llave indicada (k), o hasta al final de la lista.
La situación óptima es que el registro buscado sea el primero en ser examinado. El peor caso es cuando las llaves de todos los n registros son comparados con k (lo que se busca). El caso promedio es n/2 comparaciones.
Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.
1.2 Ventajas de la técnica.
Es el algoritmo más simple de búsqueda y no requiere ningún proceso previo de la tabla, ni ningún conocimiento sobre la distribución de las llaves. La búsqueda secuencial es el área del problema donde previamente existían mejores algoritmos.
Es el mejor metodo de busqueda para registros desordenados y revisa nodo por nodo sin brincar ninguno ( es muy seguro)
Muestreo de acceso:
Este método consiste en observar que tan frecuentemente se solicita cada registro y ordenarlos de acuerdo a las probabilidades de acceso detectadas.
Movimiento hacia el frente:
Este esquema consiste en que la lista de registros se reorganicen dinámicamente. Con este método, cada vez que búsqueda de una llave sea exitosa, el registro correspondiente se mueve a la primera posición de la lista y se recorren una posición hacia abajo los que estaban antes que el.
Transposición:
Este es otro esquema de reorganización dinámica que consiste en que, cada vez que se lleve a cabo una búsqueda exitosa, el registro correspondiente se intercambia con el anterior. Con este procedimiento, entre mas accesos tenga el registro, mas rápidamente avanzara hacia la primera posición. Comparado con el método de movimiento al frente, el método requiere mas tiempo de actividad para reorganizar al conjunto de registros . Una ventaja de método de transposición es que no permite que el requerimiento aislado de un registro, cambie de posición todo el conjunto de registros. De hecho, un registro debe ganar poco a poco su derecho a alcanzar el inicio de la lista.
Ordenamiento:
Una forma de reducir el numero de comparaciones esperadas cuando hay una significativa frecuencia de búsqueda sin éxito es la de ordenar los registros en base al valor de la llave. Esta técnica es útil cuando la lista es una lista de excepciones, tales como una lista de decisiones, en cuyo caso la mayoría de las búsquedas no tendrán éxito. Con este método una búsqueda sin éxito termina cuando se encuentra el primer valor de la llave mayor que el buscado, en lugar de la final de la lista.
1.3 Desventajas de la técnica.
Este método de búsqueda es muy lento, pero si los datos no están en orden es el único método que puede emplearse para hacer las búsquedas. Si los valores de la llave no son únicos, para encontrar todos los registros con una llave particular, se requiere buscar en toda la lista.
Si los registros a los que se accede con frecuencia no estan al principio del archivo, la cantidad promedio de comparaciones aumenta notablemente dado que se requiere mas tiempo para recuperar dichos regisros.
Para las aplicaciones interactivas que incluyen peticione s o actualizaciones de registros individuales, los archivos secuenciales ofrecen un rendimiento pobre.
Definitivamente, la busqueda secuencial es el metodo menos eficiente; porque se basa en comparar el valor que se desea buscar con cada uno de los valores del archivo.
1.4 Principales Aplicaciones.
Los archivos secuenciales son típicamente utilizados en aplicaciones de proceso de lotes Y son óptimos para dichas aplicaciones si se procesan todos los registros. La organización secuencias de archivos es la única que es fácil de usar tanto en disco como en cinta.
Un ejemplo claro para utilizar esta tecnica de busqueda es cuando se tiene una base de datos no muy grande en un negocio pequeño donde los registros mas usados son llamados con frecuencia , es aquí donde esta tecnica es fuerte, ya que se aplica a un patron de busqueda pequeño, sencillo y manejable; es decir como si fuera una descripcion, es uno tras otro.
Ejemplo: numero de cliente nombre apellido direccion curp
1.5 Codificación.
void sequential_search(int x[100], int search_num)
{
int index = 0;
while((index < 100) && (search_num != x[index]))
{ // Loop while the number is not found and while more elements remain.
if(x[index] != search_num)
{ // If current element is not the one for which we are
index++; // searching, increment subscript index.
}
}
return(index);
}
PARTE II:
Técnica de Búsqueda Secuencial Indexada.
2.1 Descripción de la técnica.
Un método popular para superar las desventajas de los archivos secuenciales es el del archivo secuencias indexado; pero implica un aumento en la cantidad de espacio requerida.
Funciona de la siguiente manera:
Se reserva una taba auxiliar llamada indice ademas del archivo ordenado mismo. Cada elemento en el indice consta de una llave kindex y un apuntador al registro en el archivo que corresponde a kindex. Los elementos en el indice al igual que los elementos en el archivo, deben estar ordenados en la llave. Si el indice es de un octavo del tamaño del archivo, se representa en el indice cada octavo registra el archivo.
Si el indice comienza a crecer tanto que se vuelve ineficaz se puede usar un indice secundario que funciona casi de la misma forma que el indice principal, solo que apunta a este, no a la tabla principal la busqueda empieza con una exploracion por el indice secundario; esto nos lleva a un subarreglo en el indice principal; despues el procesamiento continua normalmente. Un ejemplo de lo anterior es la siguiente figura.
2.2 Ventajas de la técnica.
Permite procesar el archivo secuencialmente por orden lógico y también procesarlo al azar.
La ventaja real del método secuencial indexado es que los elementos en la tabla pueden ser examinados en forma secuencial si todos los registros en el archivo deben ser accesados, pero sin embargo, el tiempo de búsqueda para algún elemento en particular se reduce considerablemente. La búsqueda secuencial se realiza en la tabla de índices que es más pequeña en lugar de la tabla más grande. Una vez que se ha encontrado un índice correcto, se hace una segunda búsqueda secuencial únicamente en la parte reducida de la tabla que contiene los registros.
La organización secuencial indexado es conveniente para archivos con mediana volatilidad, actividad variable y tamaño relativamente estable.
Las eliminaciones de una tabla secuencial indexada se pueden hacer fácilmente mediante la asignación de banderas a las entradas que son eliminadas. Durante la búsqueda secuencial a través de la tabla, se ignoran las entradas que han sido eliminadas.
2.3 Desventajas de la técnica.
Pero implica un aumento en la cantidad de espacio requerida, porque se ocupa un indice y “se pone a un lado además del fichero clasificado a sí mismo”.
La inserción en una tabla secuencial indexada es un poco más difícil debido a que puede qe no exista espacio entre dos entradas en la tabla, siendo necesario mover un gran número de elementos en la tabla.
El uso de una lista ligada (indice) da una gran sobrecarga de espacio y tiempo para los apuntadores que se utilizan en la busqueda de registros.
Los registros deben ser de longitud fija. El archivo debe estar soportado por una memoria de masa tal como el disco; no se utiliza en cinta magnética. A veces todo el archivo debe estar presente en línea.
2.4 Principales Aplicaciones.
Un uso en la cual esta busqueda se aplica, es donde se presenta el ingreso de datos (registros) sin ningun tipo de orden especifico; pero en cada determinado momento su campo llave es almacenado en un indice, en el cual esas llaves estan ordenadas de menor a mayor o de mayor a menor dependiendo el uso que se le de. De esta manera, para agilizar la busqueda de un registro en particular se accesa a ese registro por medio de su campo llave alacenado en el indice.
Un ejemplo de nuestra vida diaria y donde se aplica esta busqueda es en un negocio mediano (negocio de carnes frias , refaccionaria), ya que aquí se necesita una busqueda eficiente con una sola clave de acceso y otorgandonos la informacion requerida.
2.5 Codificación.
Algoritmo de Búsqueda Secuencial Indexada:
PROCEDURE B_S_INDEXADA(llave:integer; var pocis:integer);
var
i,n:integer;
f:boolean;
begin
f:=false;
i:=1;
while (i<llave) then
f:= true;
else
inc(i);
if i=1 then
linf:=1
else
linf:=pindex[i-1];
if f then
lsup:=pindex[i]-1
else
lsup:=n;
j:=linf; f:=false;
while(j<=lsup) ands (not f) do
if k[j]="llave" then f:="true"
else
inc(j);
if f then posic:="j"
else
posic:="0;"
end;
KINDEX. Arreglo de llaves en la tabla índice. PINDEX. Arreglo de punteros a los registros actuales del archivo. N. Tamaño del archivo. TAMINDEX. Tamaño de la tabla índice. Primero busca el rango de llaves en el que puede encontrar posiblemente la llave indicada, después busca secuencialmente en cada una de ellas hasta encontrarla o no, en caso de que no exista.
PARTE III:
Técnica de Búsqueda Binaria.
3.1 Descripción de la técnica.
Si los datos que se buscan están clasificados en un determinado orden, el método citado anteriormente se denomina búsqueda binaria.
La búsqueda binaria utiliza un método de `divide y vencerás'para localizar el valor deseado. Con este método se examina primero el elemento central de la lista; si éste es el elemento buscado, entonces la búsqueda ha terminado.
En caso contrario, se determinar si el elemento buscado será en la primera o la segunda mitad de la lista y a continuación se repite este porceso, utilizando el elemento central de esa sublista.
Se puede aplicar tanto a datos en listas lineales como en árboles binarios de búsqueda. Los prerrequisitos principales para la búsqueda binaria son:
-
La lista debe estar ordenada en un orden específico de acuerdo al valor de la llave.
-
Debe conocerse el número de registros.
Algoritmo:
Se compara la llave buscada con la llave localizada al centro del arreglo.
Si la llave analizada corresponde a la buscada fin de búsqueda si no.
Si la llave buscada es menor que la analizada repetir proceso en mitad superior, sino en la mitad inferior.
El proceso de partir por la mitad el arreglo se repite hasta encontrar el registro o hasta que el tamaño de la lista restante sea cero , lo cual implica que el valor de la llave buscada no esta en la lista.
El esfuerzo máximo para este algoritmo es de log2n. El mínimo de 1 y en promedio ½ log2 n.
3.2 Ventajas de la técnica.
La búsqueda binaria es un método eficiente siempre que el vector esté ordenado. En la práctica, esto suele suceder, pero no siempre. Por esta razón la búsqueda binaria exige una ordenación previa del archivo.
La búsqueda binaria proporciona un medio para reducir el tiempo requerido para buscar en una lista. Este método, sin embargo, exige que los datos estén ordenados.
Es mas rapido por su recursividad, su mayor ventaja es con los archivos extensos.
El codigo del procedimiento de esta busqueda es corto en comparacion con las demas tecnicas de busqueda.
En esencia, con una sola comparacion eliminamos la mitad de la tabla; este es el metodo mas eficiente de buscar en una lista ordenada sin emplear tablas o indices adicionales.
3.3 Desventajas de la técnica.
La búsqueda binaria tiene, sin embargo, inconvenientes a resaltar:
El archivo debe estar ordenado y el almacenamietno de un archivo ordenado suele plantear problemas en las inserciones y eliminaciones de elementos.
No revisa todos los elementos del archivo, requiere que todos los elementos esten ordenados
Esta busqueda mas de uno o dos accesos si el archivo es enorme;y mantener ese archivo ordenado es muy costoso.
3.4 Principales Aplicaciones.
Ejemplo: Árbol Binario de Búsqueda:
Se distinguen 2 casos triviales con solución directa: árbol vacío (elemento no encontrado) o raíz del árbol.
Solución:
Cuando el elemento no se encuentra en la raíz, dividimos el árbol en 2 subarboles (izquierda y derecha) y aplicamos ABB, sobre aquel que nos interese (al estar ordenado solo debemos ir por una de las ramas).
La combinación de resultados es trivial: la solución del subproblema es también la del problema global.
Supongamos la lista:
1231
1473
1545
1834
1892
1898 elemento central
1983
2005
2446
2685
3200
Si está buscando el elemento 1983, se examina el número central 1898 en la sexta posición. Ya que 1983 es mayor que 1898, se desprecia la primera sublista y nos centramos en la segunda
1983
2005
2446 elemento central
2685
3200
El número central de esta sublista es 2446 y el elemento buscado es 1983 menos que 2446; eliminamos la segunda sublista y nos queda
1983
2005
Como no hay término centralm elegimos el término inmediatamente anterior al término central, 1983, que es el buscado.
Se han necesitado tres comparaciones, mientras que la búsqueda secuencial hubiese necesitado siete.
3.5 Codificación.
void binary_search(int x[100], int lowerbound, int upperbound, int search_num)
{
int search_pos;
int compare_count = 1; // Variable used to count the comparisons.
// Calculate initial search position.
search_pos = (lowerbound + upperbound) / 2;
while((x[search_pos] != search_num) && (lowerbound <= upperbound))
{
compare_count++;
if(x[search_pos] > search_num) // If the value in the search
{ // position is greater than the number
upperbound = search_pos - 1; // for which we are searching, change
} // upperbound to the search position
else // minus one.
{ // Else, change lowerbound to search
lowerbound = search_pos + 1; // position plus one.
}
search_pos = (lowerbound + upperbound) / 2;
}
if(lowerbound <= upperbound)
{
cout << "A binary search found the number in "
<< compare_count << " comparisons.\n";
}
else
{
cout << "Number not found by binary search after "
<< compare_count << " comparisons.\n";
}
}
PARTE IV:
Técnica de Búsqueda por Interpolación.
4.1 Descripción de la técnica.
Este método se puede aplicar solamente a tablas o archivos ordenados. Como su nombre lo indica se trata de llegar al elemento buscado por medio de la interpolación lineal. El procedimiento es recursivo; como en el caso de la búsqueda binaria, en cada paso se van modificando los límites, disminuyendo el intervalo, hasta llegar al elemento buscado.
Si se determina que la clave buscada XX se encuentra dentro del intervalo INTABLA de la tabla, y que la variación en ese intervalo de la clave es INCLAVE, la siguiente posición a probar es:
PX = PI + ENTERO ((XX-XI) * (INTABLA / INCLAVE))
El algoritmo es similar al de búsqueda binaria, la diferencia está en que en vez de dividir el área en mitades, se delimita por medio de los valores resultantes de la interpolación.
En búsqueda binaria el espacio se corta siempre adentro a medias, las garantías de lo que desea el funcionamiento logarítmico. Sin embargo, durante la búsqueda encontramos un valor que esté muy cerca del número z de la búsqueda, parece más razonable continuar la búsqueda en esa area envez de ocultor e ir a la media punta siguiente.
En detalle, si z es muy pequeño, debemos comenzar la búsqueda en alguna parte en el principio de la secuencia en vez de la punta intermedia Considere la manera que abrimos un libro cuando estamos buscando para cierta página. Diga que la página es 200 y el libro parece de 800 paginas. La paginación 200 es así alrededor de la marca de un cuarto, y nosotros utilizamos este conocimiento como indicación de donde abrir el libro. No golpearemos probablemente la paginación 200 en el primer intento; suponga que conseguimos la paginación 250 en lugar de otro. Ahora cortamos la búsqueda a un rango de 250 paginas, y la paginación deseada está en alrededor la marca de 80 por ciento entre la paginación 1 y 250. Ahora intentamos ir detrás de un quinto de la manera corta. Podemos continuar este proceso hasta que conseguimos bastante cercanos a la paginación 200, de que que podemos mover de un tirón una pagina al mismo tiempo. Ésta es exactamente la idea detrás de la búsqueda de la interpolación. En vez de cortar el espacio de la búsqueda por una mitad fija, la cortamos por una cantidad que se parezca la más probable tener éxito.
El funcionamiento de la búsqueda de la interpolación depende no solamente de la talla de la secuencia, pero también de la entrada de información misma. Hay entradas de información para los chequeos de la búsqueda de interpolación del deseado en cada número en la secuencia. Sin embargo, la búsqueda de la interpolación es muy eficiente para las entradas de información que consisten en elementos relativamente uniformemente distribuidos (las paginaciones de un libro, por supuesto, se distribuyen uniformemente). Puede ser mostrado que el número medio de comparaciones se realizó por la búsqueda de interpolación, donde el promedio asume el control todas las secuencias posibles, es 0 (logn del registro). Aunque éste se parece ser un orden de la mejora magnitud concluída de el funcionamiento de la búsqueda binaria ( debido al logaritmo adicional).
4.2 Ventajas de la técnica.
La búsqueda de interpolación, es una búsqueda mucho mejor que la binaria en la práctica porque, a menos que no sea muy grande, el valor de log2n es bastante pequeño que el logaritmo de él no es mucho más pequeño.
Incluso a pesar de qe el calclo es de algun modo mas complejo, una busqueda con interpolacion puede proporcionar una mejoria importante a nuestra busqueda binaria en grandes conjuntos de datos con claves distribuidas de modo uniforme.
4.3 Desventajas de la técnica.
La búsqueda de la interpolación requiere una aritmética más elaborada, a parte que los calculos que se necesitan para esta busqueda son muy lentos.
Para lograr esta busqueda se requieren llaves, multiplicaciones y divisiones complejas, es decir, calculos de nivel alto.
4.4 Principales Aplicaciones.
En aplicaciones matematicas donde se busquen approximaciones de alguna ecuacion, se utiliza este metodo pero sin su recursividad solo hace su primera para conseguir las approx.
Tambien tiene las mismas aplicaciones que la busqueda binaria ya que son casi iguales.
4.5 Codificación.
#define MEDIO (x) ( ((x) + 1)/2 )
#define NO_ ENCONTRADO -1
int bus_bin (int datos [], int tamaño, int clave)
{
int delta,mitad;
delta =tamaño / 2;
while (clave := datos[mitad] ) {
if (delta ==0)
return (NO_ENCONTRADO);
else if(clave>datos[mitad]);
mitad + = medio (delta);
else
mitad -= MEDIO (delta);
delta=delta/2;
}
return (mitad);
}
Conclusiones de las tecnicas de Busqueda.
Nosotros concluimos que ningun tipo de busquda es mala y a la vez ninguna es buena, ya que depende el uso dado, asi es como se demuestra en que casos es mejor una que otra.
Como la busqueda binaria que es la mas rapida, pero que a su vez no sirve si los elementos del arreglo no estan acomodados en orden ascendente al contrario de la Secuencial que apezar de que es mas lenta trabaja aunque los elementos esten revueltos.
La función para abrir y cerrar un archivo en cualquiera de las técnicas de búsqueda es el siguiente:
Fopen (parámetros , forma de abrir, +r)
Fseek (parámetros, variable en donde lees, cantidad)
Fread ( parámetros)
Fclose ( parámetros)
Esta función sirve para cualquiera de las 4 técnicas de búsqueda.
PROGRAMA DE BUSQUEDA BINARIA EN UNA ARBOL.
Codigo fuente programa de búsqueda binaria en un arbol
#include <stdio.h>
#include <stdlib.h>
/* Binary Tree Structure template */
typedef struct binary_tree
{
char letter;
struct binary_tree *left;
struct binary_tree *right;
} TREE;
/* Function declarations */
TREE *fillTree(TREE *);
void insert(char, TREE **);
void menu(TREE *);
void displayInfo();
void inorder(TREE *);
void preorder(TREE *);
void postorder(TREE *);
int search(TREE *, char, int);
void freeTree(TREE *);
int deleteNode(TREE *, char);
/* Begin main function */
void main()
{
TREE *root=NULL;/* Create the root pointer */
root=fillTree(root);/* Fill the tree */
menu(root);/* Pass menu root, and enjoy */
}
/* Begin fillTree function */
TREE *fillTree(TREE *root)
{
FILE *fin=fopen("btree.dat","r"); /* Open data file & create FILE ptr */
char letter;
while(fscanf(fin,"%c",&letter)!=EOF)/* Fill tree letter by letter */
insert(letter, &root);
return root;
}
/* Begin insert function */
void insert(char newLetter, TREE **root)
{
TREE *process;
if(*root == NULL){
process = (TREE *)malloc(sizeof(TREE));
if(process!= NULL){
process->letter = newLetter;
process->left = NULL;
process->right = NULL;
*root = process;
}
else
printf("Out of memory, can't insert letter.\n");
}
else{
if(newLetter < (*root)->letter) insert(newLetter, &((*root)->left));
else insert(newLetter, &((*root)->right));
}
}
/* Begin menu function */
void menu(TREE *root)
{
int choice, result, count;
char target, process;
displayInfo();
while((scanf("%d",&choice)!=8)){
switch(choice){
case 1: /* Traverse BST inorder */
puts("");
inorder(root);
displayInfo();
break;
case 2: /* Traverse BST in preorder */
puts("");
preorder(root);
displayInfo();
break;
case 3: /* Traverse BST in postorder */
puts("");
postorder(root);
displayInfo();
break;
case 4: /* Search BST for a node */
count=0;
puts("");
printf("\nEnter target to search for: ");
flushall(); /* Clear input buffer */
scanf("%c",&target);
result=search(root, target, count);
if(result==-1) printf("\nTarget does not exist.");
else
printf("\nTarget %c found in %2d searches.\n", target, result);
displayInfo();
break;
case 5: /* Count height of a node */
count=0;
puts("");
printf("\nEnter character to count height of: ");
flushall(); /* Clear input buffer */
scanf("%c",&target);
result=search(root, target, count);
if(result==-1) printf("\nTarget does not exist.");
else
printf("\nCharacter %c has a height of %2d.", target, result-1);
displayInfo();
break;
case 6: /* Insert node into BST */
puts("");
printf("\nEnter character to insert into binary search tree: ");
flushall(); /* Clear input buffer */
scanf("%c",&process);
insert(process,&root);
printf("\nThe character %c was inserted.", process);
displayInfo();
break;
case 7: /* delete node from BST */
puts("");
printf("\nEnter character to delete from binary search tree: ");
flushall(); /* Clear input buffer */
scanf("%c",&process);
result=deleteNode(root, process);
if(result==0) printf("\nCharacter doesn't exist.");
else printf("\nCharacter %c deleted.", process);
displayInfo();
break;
case 8: /* Au Revoir! */
printf("\nHave a nice day. Goodbye.");
freeTree(root);
break;
default:/* Let user know they made an invalid choice */
puts("");
printf("Invalid selection\n\n");
displayInfo();
break;
} /* End switch */
}/* End while */
}
/* Begin displayInfo function */
void displayInfo()
{
printf("\n\n");
puts("--------------------------------------------------");
puts(" Binary Search Tree Menu Options ");
puts("--------------------------------------------------");
printf("\n");
printf("\t 1 Display inorder traversal\n");
printf("\t 2 Display preorder traversal\n");
printf("\t 3 Display postorder traversal\n");
printf("\t 4 Search for a given node\n");
printf("\t 5 Count the height of a given node\n");
printf("\t 6 Insert a node onto the tree\n");
printf("\t 7 delete a node from the tree\n");
printf("\t 8 Quit program\n");
printf("\n");
printf("Enter your selection: ");
}
/* Begin inorder function */
void inorder(TREE *root)
{
if(root->left!=NULL) inorder(root->left);
printf("%c",root->letter);
if(root->right!=NULL) inorder(root->right);
}
/* Begin preorder function */
void preorder(TREE *root)
{
printf("%c",root->letter);
if(root->left!=NULL) preorder(root->left);
if(root->right!=NULL) preorder(root->right);
}
/* Begin postorder function */
void postorder(TREE *root)
{
if(root->left!=NULL) postorder(root->left);
if(root->right!=NULL) postorder(root->right);
printf("%c",root->letter);
}
/* Begin search function */
int search(TREE *root, char target, int count)
{
if(root==NULL) return -1; /* Target doesn't exist */
count++;
if(root->letter==target) return count;/* Target found */
if(target > root->letter)
return search(root->right, target, count);
if(target < root->letter)
return search(root->left, target, count);
return 007;/* Bond, James Bond */
}
/* Begin freeTempTree function */
void freeTree(TREE *root)
{
if(root!=NULL){/* As long as root isn't null, recursively */
freeTree(root->left); /* travel tree in postorder freeing the */
freeTree(root->right); /* nodes as you go. */
free(root);
}
}
/* Begin deleteNode function */
int deleteNode(TREE *T_ptr, char target)
{
intrt_child = 0, lft_child = 0;
TREE *ptr = T_ptr, *parent = T_ptr, *S = T_ptr, *save = T_ptr;
/*-----------------------------------------------+
|Find the node
+-----------------------------------------------*/
while (ptr != NULL && ptr->letter != target) {
parent = ptr;
if (target < ptr->letter) ptr = ptr->left;
else ptr = ptr->right;
}
if (ptr == NULL) return 0;/* Nothing to delete */
else if (S->letter == target && (S->left == NULL || S->right == NULL))
S = (S->left == NULL) ? S->right : S->left;
else
/*-----------------------------------------------+
| delete a node without a left child
+-----------------------------------------------*/
if (ptr->left == NULL)
if (target < parent->letter) parent->left = ptr->right;
else parent->right = ptr->right;
/*-----------------------------------------------+
| delete a node without a right child
+-----------------------------------------------*/
else if (ptr->right == NULL)
if (target < parent->letter) parent->left = ptr->left;
else parent->right = ptr->left;
/*--------------------------------------------------------------+
| delete a node with both chidren--use RsmallestS subtree.
+--------------------------------------------------------------*/
else {
save = ptr;
parent = ptr;
if ((ptr->left) >= (ptr->right)) {
ptr = ptr->left; /* delete from left subtree.*/
while (ptr->right != NULL) {
rt_child = 1;
parent = ptr;
ptr = ptr->right;
}
save->letter = ptr->letter;
if (rt_child) parent->right = ptr->left;
else parent->left = ptr->left;
}
else { /* delete from right subtree.*/
ptr = ptr->right;
while (ptr->left != NULL) {
lft_child = 1;
parent = ptr;
ptr = ptr->left;
}
save->letter = ptr->letter;
if (lft_child) parent->left = ptr->right;
else parent->right = ptr->right;
}
}
free(ptr);
return 1; /* Indicates successful deletion */
}
Bibliografia.
-
Tenenbaum Aaron, Augenstein Moshe. Data Structures.Prentice-Hall (1981)
-
Thurber Kenneth, Patton Peter C. Data Structures and Computer Architecture. Lexington Books(1977)
-
Magidin Matluk Mario, Estructuras de Datos. Ed. Trillas (1991) 1era ed.
-
Manber Udi, Introduction to Algorithms Addison-Wesley (1989)
-
Wirth Niklaus, Algorithms and Data Structures. Prentice-Hall (1986)
-
Joyanes Aguilar Luis, Fundamentos de programación. Algoritmos y estructura de datos. McGraw-Hill(1988)
-
Sisa Alberto Jaime, Estructuras de información. McGraw-Hill(1989)
-
Manber Udi, Introduction to Algoritms, A Creative Approach. Addison-Wesley(1989)
-
Arranz Ramonet Antonio, Administración de datos y archivos por computadora. Limusa(1987)
-
Joyanes Aguilar Luis, Fundamentos de programación. Algoritmos y estructura de datos. McGraw-Hill(1988)
-
Enciclopedia del lenguaje C.
-
Francisco Javier Ceballos, serie enciclopedia, año1997
Referencias:
18
Descargar
| Enviado por: | Pochitoke |
| Idioma: | castellano |
| País: | México |
Todos los derechos reservados.