pero tiene un error
(pero no compila)
#include "bool.h"
#include<stdio.h>
#define DEBUG 1
// NOTA: faltan implementar las rotaciones
// dobles; por ahora no balancea bien
// un nodo de ruteo no cuenta duplicados
#define NO_VALIDO -1
#ifdef DEBUG
int next = 0;
#endif
struct nodo_de_arbol {
char dato;
int altura;
int contador;
#ifdef DEBUG
int id;
#endif
struct nodo_de_arbol* padre;
struct nodo_de_arbol* izq; // hijo
struct nodo_de_arbol* der; // otro hijo
};
typedef struct nodo_de_arbol nodo;
void borra(nodo* n) {
if (n == NULL) {
return;
} else {
borra(n->izq);
borra(n->der);
free(n);
}
return;
}
void muestra(nodo* n) {
if (n == NULL) {
return; // caso base de recursion
} else {
muestra(n->izq);
#ifdef DEBUG
if (n->izq != NULL && n->der != NULL) {
printf("[%c, %d <%d / %d, %d>] ",
n->dato, n->altura, n->id,
n->izq->id, n->der->id);
} else {
printf("(%c, %d <%d> #%d) ",
n->dato, n->altura, n->id,
n->contador);
}
#else
if (n->izq == NULL && n->der == NULL) {
printf("%c[%d] ", n->dato, n->contador);
}
#endif
muestra(n->der);
}
return;
}
void balancea(nodo* n, nodo** raiz) {
int ai, ad, max, min, aalt, balt;
nodo* t = NULL;
nodo* u = NULL;
nodo* v = NULL;
nodo* a = NULL;
nodo* b = NULL;
nodo* p = NULL;
nodo* x1 = NULL;
nodo* x2 = NULL;
if (n == NULL) {
#ifdef DEBUG
printf("Ya topamos con la raiz.\n");
#endif
return;
}
if (n->izq == NULL ||
n->der == NULL) {
#ifdef DEBUG
printf("No se puede sin hijos.\n");
#endif
return;
}
t = n; // nodo actual
assert(t != NULL);
#ifdef DEBUG
printf("Checando balance en %c (alt. %d).\n",
t->dato, t->altura);
#endif
u = n->izq; // hijo izquierdo
assert(u != NULL);
v = n->der; // hijo derecho
assert(v != NULL);
ai = u->altura;
ad = v->altura;
#ifdef DEBUG
printf("Hijos %c (alt. %d) y %c (alt. %d).\n",
u->dato, ai, v->dato, ad);
#endif
max = (ai > ad) ? ai : ad;
min = (ai > ad) ? ad : ai;
if (max + 1 != t->altura) {
t->altura = max + 1; // actualizar altura
}
if (max - min > 1) { // balancear
p = t->padre; // padre del actual
#ifdef DEBUG
printf("%c a altura %d requiere balanceo.\n",
t->dato, t->altura);
printf("Entrando tenemos:\n");
if (p != NULL) {
printf("p = %d, ", p->id);
} else {
printf("p = NULL, ");
}
printf("t = %d, \n", t->id);
printf("u = %d, v = %d, \n",
u->id, v->id);
#endif
if (ai <= ad - 2) { // si hay demasiada altura a la der // => voltear "peso" hacia la izq.
a = v->izq;
b = v->der;
assert(a != NULL);
assert(b != NULL);
aalt = a->altura;
balt = b->altura;
#ifdef DEBUG
printf("a = %d, b = %d, \n",
a->id, b->id);
#endif
if (aalt <= balt) { // rotacion simple izq printf("Simple izquierda.\n"); if (p != NULL) { // v debe reemplazar a t como hijo if (p->izq == t) {
p->izq = v;
} else { // era derecho
p->der = v;
}
} else {
// v es ahora raiz
*raiz = v;
}
// el padre de t sera padre de v
v->padre = p;
// printf("Arreglado hacia arriba.\n");
// v ahora es hijo izq de t
// t es padre de v
v->izq = t;
t->padre = v;
// el hijo der de t no cambia
// printf("Arreglado entre t y v.\n");
// a va a ser hijo derecho de t
// t va a ser padre de a
t->der = a;
a->padre = t;
// printf("Arreglado entre a y t.\n");
#ifdef DEBUG
if (p != NULL) {
printf("v = %d es hijo de p = %d,\n",
v->id, p->id);
}
printf("t = %d = %d es hijo de v = %d,\n",
t->id, v->izq->id, v->id);
printf("a = %d = %d es hijo de t = %d\n",
a->id, t->der->id, t->id);
printf("b = %d = %d es hijo de v = %d,\n",
b->id, v->der->id, v->id);
printf("u = %d = %d es hijo de t = %d.\n",
u->id, t->izq->id, t->id);
#endif
// para ni u ni b nada cambia
} else {
printf("Simple derecha-izquierda.\n");
x1 = a->izq;
assert(x1 != NULL);
x2 = a->der;
assert(x2 != NULL);
if (p != NULL) {
if (p->izq == t) {
p->izq = a; // w
} else { // era der.
p->der = a;
}
} else { // t era raiz
*raiz = a; // avisar main
}
v->padre = a;
a->der = v;
t->padre = a;
a->izq = t;
v->izq = x2;
x2->padre = v;
t->der = x1;
x1->padre = t;
}
} else if (ai >= ad + 2) {
// voltear hacia la derecha
a = u->izq;
b = u->der;
assert(a != NULL);
assert(b != NULL);
aalt = a->altura;
balt = b->altura;
if (aalt >= balt) {
printf("Simple derecha.\n");
if (p != NULL) {
if (p->izq == t) {
p->izq = u;
} else { // era derecho
p->der = u;
}
} else {
// cambiando la raiz para ser u
*raiz = u;
}
u->padre = p;
// printf("Arreglado hacia arriba.\n");
u->der = t;
t->padre = u;
// printf("Arreglado entre t y u.\n");
t->izq = b;
b->padre = t;
// printf("Arreglado entre b y t.\n");
} else { // (aalt < balt) printf("Doble izquierda derecha.\n"); x1 = b->izq;
assert(x1 != NULL);
x2 = b->der;
assert(x2 != NULL);
if (p != NULL) {
if (p->izq == t) {
p->izq = b; // w
} else { // era der.
p->der = b;
}
} else { // t era raiz
*raiz = b; // avisar main
}
u->padre = b;
b->izq = u;
t->padre = b;
b->der = t;
u->der = x1;
x1->padre = u;
t->izq = x2;
x2->padre = t;
}
}
if (p != NULL) {
balancea(p, raiz);
}
} else {
#ifdef DEBUG
printf("%c esta bien (%d vs. %d).\n",
n->dato, ai, ad);
#endif
// siempre checa hasta la raiz
balancea(n->padre, raiz);
}
return;
}
bool agrega(char dato, nodo* arbol, nodo** n) {
nodo* nuevo;
nodo* reemplazo;
char ruteo;
if (arbol == NULL) {
// caso especial de no tener nada aun
nuevo = (nodo*)malloc(sizeof(nodo));
nuevo->contador = 1;
#ifdef DEBUG
nuevo->id = next++;
#endif
nuevo->altura = 1; // como hoja
nuevo->dato = dato;
nuevo->padre = NULL;
nuevo->izq = NULL;
nuevo->der = NULL;
*n = nuevo; // nueva raiz
return TRUE;
} else {
if (arbol->izq == NULL &&
arbol->der == NULL) { // si es hoja
if (arbol->dato == dato) {
// iguales; agregar duplicidad
arbol->contador++;
return FALSE;
}
#ifdef DEBUG
printf("Agregando %c en %c.\n",
dato, arbol->dato);
#endif
ruteo = (arbol->dato < dato ? arbol->dato : dato);
nuevo = (nodo*)malloc(sizeof(nodo));
nuevo->contador = 1;
#ifdef DEBUG
nuevo->id = next++;
#endif
nuevo->altura = 1; // como hoja
nuevo->dato = dato;
nuevo->padre = arbol;
nuevo->izq = NULL;
nuevo->der = NULL;
reemplazo = (nodo*)malloc(sizeof(nodo));
reemplazo->contador = arbol->contador;
arbol->contador = NO_VALIDO;
#ifdef DEBUG
reemplazo->id = next++;
#endif
reemplazo->altura = 1; // como hoja
reemplazo->dato = arbol->dato;
reemplazo->padre = arbol;
reemplazo->izq = NULL;
reemplazo->der = NULL;
if (dato < arbol->dato) {
arbol->izq = nuevo;
arbol->der = reemplazo;
} else if (dato > arbol->dato) {
arbol->der = nuevo;
arbol->izq = reemplazo;
}
arbol->dato = ruteo;
arbol->altura = 2;
balancea(arbol->padre, n);
} else {
if (dato <= arbol->dato) {
agrega(dato, arbol->izq, n);
} else { // mayor
agrega(dato, arbol->der, n);
}
}
}
return TRUE;
}
printf("desea elimiar un nodo");
printf("dame al altura del nodo al que desea eliminar");
scanf("%d %d", nodos, alura);
dato = getchar();
if (!isspace(dato)) {
if (eliminar(dato, raiz, &raiz)) {
contador++;}
printf("eliminacion completada");
else {printf("el nodo seleccionado no existe");
if (raiz != NULL) {
printf("\nCon %d nodos, altura %d: \n",
contador, raiz->altura);
int main(int argc, char** args) {
nodo* raiz = NULL;
char dato;
int contador = 0;
do {
dato = getchar(); // lee un caracter
if (!isspace(dato)) {
if (agrega(dato, raiz, &raiz)) {
contador++;
}
if (raiz != NULL) {
printf("\nCon %d nodos, altura %d: \n",
contador, raiz->altura);
muestra(raiz);
printf("\n");
} else {
printf("No hay nada.\n");
}
}
} while (dato != '!'); // parar despues de !
borra(raiz);
return 1;
}
************************************************************************************************PUNTOS EXTRAS
este es el codigo de funciones lo e modificado para que fuera un juego interactivo con el usuario
este es el codigo--->
#include#include #include "bool.h" #include "entrada.h" int suma(int a, int b) { return (a + b); } int resta(int a, int b) { return (a - b); } int multiplica(int a, int b) { return (a * b); } int divide(int a, int b) { return (a / b); } int residuo(int a, int b) { return (a % b); } // tipo de dato para apuntador a funcion typedef int (*rutina)(int, int); typedef void (*otracosa)(char, int); int main(int argc, char** args) { rutina *r = NULL; otracosa* o = NULL; int x, y; char = juego int min = 1; int max = 10; if (argc > 2) { min = atoi(args[1]); max = atoi(args[2]); if (min > max) { printf("Pon primero el minimo.\n"); return; } else if (min <= 0) { printf("Deben ser positivos. Sorry.\n"); return; } } srand(time(0)); // semilla para rng r = (rutina*)malloc(sizeof(rutina)*5); r[0] = &suma; r[1] = &resta; r[2] = &multiplica; r[3] = ÷ r[4] = &residuo; while (TRUE) { printf("dime que cres que va a salir suma, resta, multiplicacion, divison o residuo); printf("dame una opcion", juego); scanf("%d", juego); switch case(juego){ case 0: printf("as elegido suma--- veamos cual es la respuesta") break; case 1: printf("as elegido resta---veamos cual es la respuesta"); break; case 2: printf("as elegido multiplicacion---veamos cual es la respuesta"); break; case 3: printf("as elegido divison---vemaos cual es la respuesta"); break; case 4: printf("as elegido residuo"); break; default: printf("opcion no valida"); break; printf("cres poder ganar"); printf("a jugar se a dicho"); printf("\n); printf("Dame el primer valor:\n"); x = pide_numero(min, max); printf("Dame el segundo valor:\n"); y = pide_numero(min, max); printf("Salio %d.\n", r[rand()%5](x, y)); if(juego = r[rand()%5](x, y)){ printf("felisidades si era lo opcion que seleccionaste");} else {printf("lo sentimos pero perdiste vuelve a intentarlo"); printf("Quieres mas? (s/n): "); if (pide_opcion("sn") == 'n') { break; // ya no } } free(r); // modificado del archivo orginal para que el programa se comvirtiera en un juego con el usuario// return 1; }
