Plan

UNIVERSIDAD DE PANAMÁ

FACULTAD DE INFORMATICA, ELECTRÓNICA

Y COMUNICACIÓN

ESCUELA DE INGENIERIA EN ELECTRÓNICA Y COMUNICACIÓN

CURSO DE PROGRAMACIÓN II.

Codificación de Algoritmos

Árboles Binarios de Búsqueda y Árboles Balanceados.

Presentado Por:

Barría, Irving
8-779-1124

GRUPO: 2,1 A

A CONSIDERACIÓN DE:

Profesor Álvaro Pino

FECHA:8 de Julio de 2003

© FIEC – UP
PROGRAMA 1.
Árboles Binarios Sencillos y Árboles Binarios de Búsqueda.

El siguiente programa presenta las operaciones básicas en un árbol binario: inserción, eliminación y búsqueda, además que es posible determinar si un árbol cargado en memoria es o no un árbol binario de búsqueda. Se utilizan los algoritmos de CARGA, recorridos dePREORDEN, INORDEN y POSTORDEN, BÚSQUEDA BINARIA y ELIMINACIÓN. A continuación, el código en lenguaje C:

#include
#include
#include "aurum_1.h"

#define true 1
#define false 0

// Definición de la Estructura

struct nodo {
struct nodo *R;
struct nodo *L;
char data;
};

// Definición de la Estructura para la pila

struct stack {struct nodo *elem;
struct stack *link;
};

typedef struct nodo Branch;
typedef struct stack Stack;
typedef short int boolean;

// Función de Asignación de Memoria

Branch *createBranch(void)
{
Branch *tempMemAlloc;

if((tempMemAlloc = ( Branch *)malloc(sizeof( Branch ))) == NULL)
{
printf("\n No hay suficiente memoria...");printf("\n Presione cualquier tecla para terminar.");
getch();
exit(EXIT_FAILURE);
}

tempMemAlloc->L = tempMemAlloc->R = NULL;

return tempMemAlloc;
}

// Algoritmo de INSERTA BINARIO

void insert(Branch *actual, Branch *toinsert)
{
if(toinsert->data < actual->data)
{
if(actual->L == NULL)
actual->L = toinsert;
else
insert(actual->L,toinsert);
}
else if(toinsert->data > actual->data)
{
if(actual->R == NULL)
actual->R = toinsert;
else
insert(actual->R, toinsert);
}
else
{
printf("\n El dato ya se encuentra en el árbol.\n");
free(toinsert);
}
}

// Función de Creación de Árbol Binario de Búsqueda

Branch *binarysearchTree(void)
{
Branch*root = NULL, *Temp = NULL;

root = createBranch();

printf("\n Introduzca el dato del nodo raíz: ");
root->data = getchar();
fflush(stdin);

while(decide(" Desea insertar un nuevo elemento?") == 1)
{
Temp = createBranch();
printf("\n Introduzca el elemento: ");
scanf("%c", &Temp->data);
fflush(stdin);

insert(root, Temp);
}return root;
}

// Función de Creación de Árbol Binario Sencillo

void makeTree(Branch *actual)
{
printf("\n Escriba un Caracter: ");
actual->data = getchar();
fflush(stdin);

printf(" Crear subárbol por la izquierda de %c?", actual->data);
if(decide("") == 1)
{
actual->L = createBranch();
makeTree(actual->L);
}

printf(" Crearsubárbol por la derecha de %c?", actual->data);
if(decide("") == 1)
{
actual->R = createBranch();
makeTree(actual->R);
}

return;
}

// Función de apilamiento de Nodos

Stack *stackInsert(Branch *toStack, Stack *top)
{
Stack *newOnStack;

if((newOnStack = ( Stack *)malloc(sizeof( Stack ))) == NULL)
{
printf("\n No hay suficientememoria...");
printf("\n Presione cualquier tecla para terminar.");
getch();
exit(EXIT_FAILURE);
}

newOnStack->link = top;
newOnStack->elem = toStack;
top = newOnStack;

return top;
}

// Función SACA PILA

Branch *deleteStack(Stack **top)
{
Branch *toReturn = NULL;
Stack *toDelete = NULL;

if(*top)
{
toDelete =...