Tarea 6. Arboles

Hola. Lo que modifique realemente fue muy sencillo y les mencionare que hice: Aqui deje el codigo que se subio de la ultima clase, el de arboles.c, recibi una asesoria mas, que me ayudó a comprender un poco mas este programa. Cuando nosotros ejecutamos el programa en clase nos manejaba que se ordenaban los datos que se estanban ingresando y los acomodaba de izquierda a derecha, deje como comentario lo que estaba y copie lo mismo abajo, para solo cambiarle la forma en que los acomoda y a la hora de ejecutar el programa lo que hice fue acomodar de derecha a izquierda, segun lo que me mencionaron en la asesoria es que a la hora de ejecutar el programa lo unico que se muestra son los valores de la hojas y que la raiz no, queda de algun modo oculto, que nos los muestra. Quisiera modificar algo mas pero aun necesito entender mas el programa.Aun no encuentro el modo para eliminar.

#include 
#include 
#include 

//#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>) ", 
      n->dato, n->altura, n->id);
    }
#else
    if (n->izq == NULL && n->der == NULL) {
      printf("%c", n->dato);
    }
#endif
    muestra(n->der);
  }
  return;
}
*/


void muestra(nodo* n) {
  if (n == NULL) {
    return; // caso base de recursion
  } else {
    muestra(n->der);
#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>) ", 
      n->dato, n->altura, n->id);
    }
#else
    if (n->izq == NULL && n->der == NULL) {
      printf("%c", n->dato);
    }
#endif
    muestra(n->izq);
  }
  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;

  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 = n->padre; // padre del actual

#ifdef DEBUG
    printf("%c a altura %d requiere balanceo.\n", 
    n->dato, n->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("Rot. simp. izq.\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("Rot. doble req. sin impl.\n");
      }
    } 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("Rot. simp. der.\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 {
 printf("Rot. req. no implementada.\n");
      }
    }
    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;
}

void 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 = 0;
#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;
  } else {
    if (arbol->izq == NULL &&
 arbol->der == NULL) { // si es hoja

#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 = 0;
#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;
      } else {
 // iguales; agregar duplicidad
 arbol->contador++;
 return;
      }

      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;
}

int main(int argc, char** args) {
  nodo* raiz = NULL;
  char dato;

  do {
    dato = getchar(); // lee un caracter
    if (!isspace(dato)) {
      agrega(dato, raiz, &raiz);
      printf("\nArbol actual: ");
      muestra(raiz);
      printf("\n");
    }
  } while (dato != '!'); // parar despues de !
  borra(raiz);

  return 1;
}