sábado, 19 de enero de 2008

Insertar En Un Arbol en lenguaje C

Desarrolle una función iterativa llamada "inserta", a la que pasándole la dirección de un puntero a la raíz de un árbol binario de búsqueda y un entero realice la inserción del entero en el árbol. En el árbol no se admiten valores repetidos. La función devuelve 1 si lo inserta y 0 si ya está. Para crear un nodo en memoria dinámica emplee la función malloc.

struct NodoArbol {
int dato; //Almacena el dato
struct NodoArbol* izq; //Apunta al subarbol izquierdo (valores menores)
struct NodoArbol* der; //Apunta al subarbol derecho (valores mayores)
};

typedef struct NodoArbol TNodoArbol, *PNodoArbol;

int inserta(PNodoArbol *a, int dat)
{
PNodoArbol padre = NULL;
PNodoArbol actual = *a;
//Buscar el dato en el árbol, manteniendo un puntero al nodo padre
while(!(actual==NULL) && dat != actual->dato) {
padre = actual;
if(dat < actual->dato) actual = actual->izq;
else if(dat > actual->dato) actual = actual->der;
}
//Si se ha encontrado el elemento, regresar sin insertar
if(!(actual==NULL)) return 0;
//Si padre es NULL, entonces el árbol estaba vacío, el nuevo nodo será
//el nodo raiz
if(padre==NULL) {
*a = (TNodoArbol *)malloc(sizeof(TNodoArbol));
(*a)->dato = dat;
(*a)->izq = (*a)->der = NULL;
return 1;
}
//Si el dato es menor que el que contiene el nodo padre, lo insertamos
//en la rama izquierda
else if(dat < padre->dato) {
actual = (TNodoArbol *)malloc(sizeof(TNodoArbol));
padre->izq = actual;
actual->dato = dat;
actual->izq = actual->der = NULL;
return 1;
}
//Si el dato es mayor que el que contiene el nodo padre, lo insertamos
//en la rama derecha
else if(dat > padre->dato) {
actual = (TNodoArbol *)malloc(sizeof(TNodoArbol));
padre->der = actual;
actual->dato = dat;
actual->izq = actual->der = NULL;
return 1;
}
return 0;
}