Estructuras I Práctica 4

///EJERCICIO 1
/*
1 - C D
2 - A B C D
3 - B C D
4 - E
*/


///EJERCICIOS 3 AL 7

#include <stdio.h>
#include <stdlib.h>

typedef enum {
  BTREE_RECORRIDO_IN,
  BTREE_RECORRIDO_PRE,
  BTREE_RECORRIDO_POST
} BTreeOrdenDeRecorrido;

typedef struct _BTNodo {
  int dato;
  struct _BTNodo *left;
  struct _BTNodo *right;
} BTNodo;

typedef BTNodo *BTree;

///INICIO DE COSAS AUXILIARES

static void imprimir_entero(int data) {
  printf("%d ", data);
}

int maximo (int a, int b){
    return (a > b)? a : b;
}

typedef struct _Cola {
    BTree puntero;
    struct _Cola *anterior, *siguiente;
} *Cola;

Cola cola_new(){
    return NULL;
}

int cola_is_empty (Cola cola){
    return (cola == NULL)? 1 : 0;
}

BTree cola_front (Cola cola){
    return cola -> puntero;
}

Cola cola_enqueue (Cola cola, BTree dato){
    Cola nuevoNodo = (Cola) malloc (sizeof(struct _Cola));
    nuevoNodo -> puntero = dato;

    if (cola == NULL){
        nuevoNodo -> siguiente = nuevoNodo -> anterior = nuevoNodo;
        return nuevoNodo;
    }

    nuevoNodo -> siguiente = cola;
    nuevoNodo -> anterior = cola -> anterior;
    cola -> anterior -> siguiente = nuevoNodo;
    cola -> anterior = nuevoNodo;
    return cola;
}

Cola cola_dequeue (Cola cola){
    if(cola == NULL)
        return NULL;

    if (cola -> siguiente == cola){
        free(cola);
        return NULL;
    }

    cola -> siguiente -> anterior = cola -> anterior;
    cola -> anterior -> siguiente = cola -> siguiente;

    Cola aux = cola -> siguiente;
    free(cola);
    return aux;
}

void swap (BTree* left, BTree* right){
  BTree auxiliar = *left ;
  *left = *right;
  *right = auxiliar;
}

void btree_suma_extra_aux(int dato, int* acumulador){
    (*acumulador) += dato;
}

void btree_cantNodos_extra_aux(int dato, int* acumulador){
    (*acumulador)++;
}

///FIN DE COSAS AUXILIARES




BTree btree_crear() {
  return NULL;
}

void btree_destruir(BTree nodo) {
  if (nodo != NULL) {
    btree_destruir(nodo->left);
    btree_destruir(nodo->right);
    free(nodo);
  }
}

BTree btree_unir(int dato, BTree left, BTree right) {
  BTree nuevoNodo = malloc(sizeof(BTNodo));
  nuevoNodo->dato = dato;
  nuevoNodo->left = left;
  nuevoNodo->right = right;
  return nuevoNodo;
}

int btree_suma (BTree arbol){
    return (arbol != NULL) ? arbol -> dato + btree_suma(arbol -> left) + btree_suma(arbol -> right) : 0;
}

int btree_cantNodos (BTree arbol){
    return (arbol != NULL) ? 1 + btree_cantNodos(arbol -> left) + btree_cantNodos(arbol -> right) : 0;
}

int btree_altura (BTree arbol){
    return (arbol != NULL) ? 1 + maximo(btree_altura(arbol -> left), btree_altura(arbol -> right)) : 0;
}

void btree_recorrer(BTree arbol, BTreeOrdenDeRecorrido orden, void (*FuncionVisitante) (int) ){
    if (arbol != NULL){
        if (orden == BTREE_RECORRIDO_PRE){
            FuncionVisitante(arbol -> dato);
            btree_recorrer(arbol -> left, orden, FuncionVisitante);
            btree_recorrer(arbol -> right, orden, FuncionVisitante);
        }

        if (orden == BTREE_RECORRIDO_IN){
            btree_recorrer(arbol -> left, orden, FuncionVisitante);
            FuncionVisitante(arbol -> dato);
            btree_recorrer(arbol -> right, orden, FuncionVisitante);
        }

        if (orden == BTREE_RECORRIDO_POST){
            btree_recorrer(arbol -> left, orden, FuncionVisitante);
            btree_recorrer(arbol -> right, orden, FuncionVisitante);
            FuncionVisitante(arbol -> dato);
        }
    }
}

void btree_recorrer_extra(BTree arbol, void (*FuncionVisitanteExtra) (int, void*) , void *extra){
    if(arbol != NULL){
        FuncionVisitanteExtra(arbol -> dato, extra);
        btree_recorrer_extra(arbol -> left, FuncionVisitanteExtra, extra);
        btree_recorrer_extra(arbol -> right, FuncionVisitanteExtra, extra);
    }
}

int btree_suma_extra(BTree arbol){
    int resultado = 0;
    btree_recorrer_extra(arbol, btree_suma_extra_aux, &resultado);
    return resultado;
}

int btree_cantNodos_extra(BTree arbol){
    int cantidad = 0;
    btree_recorrer_extra(arbol, btree_cantNodos_extra_aux, &cantidad);
    return cantidad;
}

///btree_altura() no se puede hacer con estructura de función

void btree_recorrer_bfs(BTree arbol, void (*FuncionVisitante) (int) ){
    Cola queue = cola_new();
    queue = cola_enqueue(queue, arbol);
    BTree auxiliar = cola_front(queue);
    while(cola_is_empty(queue) == 0){
      auxiliar = cola_front(queue);
      queue = cola_dequeue(queue);
        if (auxiliar != NULL){
            FuncionVisitante(auxiliar -> dato);
            queue = cola_enqueue(queue, auxiliar -> left);
            queue = cola_enqueue(queue, auxiliar -> right);
        }
    }
}

void btree_mirror (BTree arbol){
  if (arbol != NULL){
    swap( &(arbol -> left) , &(arbol -> right) );
    btree_mirror (arbol -> left);
    btree_mirror (arbol -> right);
  }
}



int main() {
  BTree ll = btree_unir(1, btree_crear(), btree_crear());
  BTree l = btree_unir(2, ll, btree_crear());
  BTree r = btree_unir(3, btree_crear(), btree_crear());
  BTree raiz = btree_unir(4, l, r);

  printf("Preorder: ");btree_recorrer(raiz, BTREE_RECORRIDO_PRE, imprimir_entero);
  printf("\nInorder: ");btree_recorrer(raiz, BTREE_RECORRIDO_IN, imprimir_entero);
  printf("\nPostorder: ");btree_recorrer(raiz, BTREE_RECORRIDO_POST, imprimir_entero);
  printf("\nBFS: ");btree_recorrer_bfs(raiz, imprimir_entero);


  printf("\n\n\nSuma: %d\nCantidad:%d\nAltura:%d\n", btree_suma(raiz), btree_cantNodos(raiz), btree_altura(raiz));
  printf("\n\nAhora usando la funcion recorrer_extra(). \n");
  printf("Suma: %d\nCantidad:%d\n", btree_suma_extra(raiz), btree_cantNodos_extra(raiz));


  btree_mirror(raiz);
  printf("\nBFS: ");btree_recorrer_bfs(raiz, imprimir_entero);


  btree_destruir(raiz);

  return 0;
}




///EJERCICIO 8

#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE 128

typedef struct Tree{
  int datos[MAX_TREE];
  int nelems;
} *CBTree;
///Tienen 127 nodos, arranco a contar en datos[1];



///Cosillas auxiliares
typedef struct _SNodo {
  int dato;
  struct _SNodo *sig;
} SNodo;

typedef SNodo *SList;
typedef SList Pila;


Pila pila_new() {
  return NULL;
}

int pila_is_empty(Pila pila) {
  return pila == NULL;
}

int pila_top (Pila pila){
    return pila -> dato;
}

Pila pila_push(Pila pila, int dato) {
  Pila nuevoNodo = malloc(sizeof(SNodo));
  nuevoNodo -> dato = dato;
  nuevoNodo -> sig = pila;
  return nuevoNodo;
}

Pila pila_pop(Pila pila){
    if(pila != NULL){
        Pila aEliminar = pila;
        pila = pila -> sig;
        free(aEliminar);
    }
    return pila;
}

void imprimir_entero (int entero){
  printf("%d  ", entero);
}

///Fin de cosillas auxiliares

CBTree cbtree_crear(){
    CBTree nuevo = (CBTree) malloc (sizeof(struct Tree));
    nuevo -> nelems = 0;
    return nuevo;
}

void cbtree_destruir(CBTree arbol){
    free(arbol);
}

int cbtree_nelementos(CBTree arbol){
  return arbol -> nelems;
}

void cbtree_insertar(CBTree arbol, int dato){
    if (cbtree_nelementos(arbol) < MAX_TREE - 1){
      arbol -> nelems ++;
      arbol -> datos[arbol -> nelems] = dato;
    }
}


///Recorre en inorder.
void cbtree_recorrer (CBTree arbol, void (*FuncionVisitante) (int) ){
  int auxiliar, flag = 0;
  Pila stack = pila_new();
  stack = pila_push(stack, 1);
  if(cbtree_nelementos(arbol) > 0){
    while( ! pila_is_empty(stack) ){
      auxiliar = pila_top(stack);
      stack = pila_pop(stack);
      if (auxiliar != -1){
        if(flag)
          FuncionVisitante(arbol -> datos [auxiliar]);
        else{
          if ( auxiliar * 2 + 1 <= cbtree_nelementos(arbol))
            stack = pila_push (stack, auxiliar * 2 + 1);
          else
            stack = pila_push (stack, -1);

          stack = pila_push (stack, auxiliar);

          if ( auxiliar * 2 <= cbtree_nelementos(arbol))
            stack = pila_push (stack, auxiliar * 2);
          else
            stack = pila_push (stack, -1);
        }
        flag = 0;
      }

      else flag = 1;
    }
  }
}

void cbtree_recorrer_bfs (CBTree arbol, void (*FuncionVisitante) (int) ){
  int elementos = cbtree_nelementos(arbol);
  for(int i = 1; i <= elementos; i++)
    FuncionVisitante(arbol->datos[i]);
}


int main() {
  CBTree arbol = cbtree_crear();
  (cbtree_nelementos(arbol) == 0) ? printf("Arranca vacio \n\n") : printf("Error \n\n");

  for (int i = 1; i <= 8; i++)
    cbtree_insertar(arbol, i);

  cbtree_recorrer(arbol, imprimir_entero);
  printf("\n\n");

  cbtree_recorrer_bfs(arbol, imprimir_entero);
  printf("\n\n");

  cbtree_destruir(arbol);
  return 0;
}





///EJERCICIOS 9 AL 13

#include <stdio.h>
#include <stdlib.h>

typedef struct _BTNodo {
  int dato;
  struct _BTNodo *left;
  struct _BTNodo *right;
} *BSTree;
///Criterio: Menor o igual a la izquierda. Mayor a la derecha.

int maximo (int a, int b){
    return (a >= b)? a : b;
}

void swap (int *a, int *b){
  int aux = *a; *a = *b; *b = aux;
}



BSTree bstree_crear(){
  return NULL;
}

BSTree bstree_insertar_auxiliar(BSTree arbol, BSTree nuevo){
  if (arbol == NULL)
    return nuevo;

  if (nuevo -> dato <= arbol -> dato)
    arbol -> left = bstree_insertar_auxiliar(arbol -> left, nuevo);
  else
    arbol -> right = bstree_insertar_auxiliar(arbol -> right, nuevo);

  return arbol;
}

BSTree bstree_insertar (BSTree arbol, int dato){
  BSTree nuevo = (BSTree) malloc (sizeof(struct _BTNodo));
  nuevo -> dato = dato;
  nuevo -> left = nuevo -> right = NULL;
  return bstree_insertar_auxiliar(arbol, nuevo);
}

BSTree bstree_direccion_minimo(BSTree arbol){
  BSTree auxiliar = arbol;
  for(; auxiliar -> left != NULL; auxiliar = auxiliar -> left);
  return auxiliar;
}

BSTree bstree_eliminar (BSTree arbol, int dato){
    BSTree auxiliar = arbol, padre = NULL, auxiliar2;
    BSTree* puntero = NULL;
    while(auxiliar != NULL && auxiliar -> dato != dato){
        padre = auxiliar;
        if(dato <= auxiliar -> dato){
            auxiliar = auxiliar -> left;
            puntero = &(padre -> left);
        }
        else{
            auxiliar = auxiliar -> right;
            puntero = &(padre -> right);
        }
    }

    if(auxiliar == NULL)
        return arbol;

    if(auxiliar -> left == NULL){
        if(auxiliar -> right == NULL){
            if(padre == NULL){
                free(auxiliar);
                return NULL;
            }
            *puntero = NULL;
            free(auxiliar);
            return arbol;
        }
        if(padre == NULL){
            auxiliar2 = auxiliar -> right;
            free(auxiliar);
            return auxiliar2;
        }
        *puntero = auxiliar -> right;
        free(auxiliar);
        return arbol;
    }
    if(auxiliar -> right == NULL){
         if(padre == NULL){
            auxiliar2 = auxiliar -> left;
            free(auxiliar);
            return auxiliar2;
        }
        *puntero = auxiliar -> left;
        free(auxiliar);
        return arbol;
    }

    auxiliar2 = bstree_direccion_minimo(auxiliar -> right);
    swap(&(auxiliar->dato), &(auxiliar2->dato));
    if(auxiliar -> right == auxiliar2){
            auxiliar->right = auxiliar2 -> right;
            free(auxiliar2);
            return arbol;
    }
    for(auxiliar = auxiliar -> right; auxiliar -> left != auxiliar2; auxiliar = auxiliar -> left);

    auxiliar -> left = auxiliar2 -> right;
    free(auxiliar2);
    return arbol;
}

int bstree_contiene (BSTree arbol, int dato){
    if(arbol == NULL)
        return 0;

    if (arbol -> dato == dato)
        return 1;

    if (dato < arbol -> dato)
        return bstree_contiene(arbol -> left, dato);

    return bstree_contiene (arbol -> right, dato);
}

int bstree_nelementos (BSTree arbol){
    return (arbol != NULL)? 1 + bstree_nelementos(arbol -> left) + bstree_nelementos(arbol -> right) : 0;
}

int bstree_altura (BSTree arbol){
    return (arbol != NULL)? 1 + maximo(bstree_altura(arbol -> left), bstree_altura(arbol -> right)) : 0;
}

void bstree_recorrer(BSTree arbol, void (*FuncionVisitante) (int) ){
    if (arbol != NULL){
            FuncionVisitante(arbol -> dato);
            bstree_recorrer(arbol -> left, FuncionVisitante);
            bstree_recorrer(arbol -> right, FuncionVisitante);
        }
}

///Para imprimir en orden, se usa inorder.
void bstree_imprimir(BSTree arbol){
    if(arbol != NULL){
        bstree_imprimir(arbol -> left);
        printf("%d  ", arbol -> dato);
        bstree_imprimir(arbol -> right);
    }
}

void lbstree_concatenar (BSTree lista, BSTree nodo){
    BSTree auxiliar = lista;
    for(; auxiliar -> right != NULL; auxiliar = auxiliar -> right);
    auxiliar -> right = nodo;
}


BSTree bstree_listify (BSTree arbol){
    if (arbol == NULL)
      return NULL;

    arbol -> left = bstree_listify (arbol -> left);
    arbol -> right = bstree_listify (arbol -> right);

    if (arbol -> left == NULL)
      return arbol;

    lbstree_concatenar (arbol -> left, arbol);
    return arbol -> left;
}

BSTree lbstree_acceder (BSTree arbol, int posicion){
    BSTree auxiliar = arbol;
    for(int i = 0; auxiliar != NULL && i < posicion; auxiliar = auxiliar -> right, i++);
    return auxiliar;
}

BSTree lbstree_treeify (BSTree lista, int cant_nodos){
    if(cant_nodos == 0)
      return NULL;

    BSTree auxiliar = lbstree_acceder (lista, cant_nodos/2);
    auxiliar -> left = lbstree_treeify(lista, cant_nodos/2);
    auxiliar -> right = lbstree_treeify(auxiliar -> right, cant_nodos - cant_nodos/2 - 1);
    return auxiliar;
}

int bstree_check_balance (BSTree arbol){
  if (arbol == NULL)
    return 1;

  int diferencia = bstree_nelementos(arbol -> left) - bstree_nelementos (arbol -> right);
  if(diferencia >= -1 && diferencia <= 1)
    return bstree_check_balance(arbol -> left) * bstree_check_balance(arbol -> right);
  return 0;
}

BSTree bstree_balancear (BSTree arbol){
    int cant_nodos = bstree_nelementos(arbol);
    arbol = bstree_listify(arbol);
    arbol = lbstree_treeify(arbol, cant_nodos);
    return arbol;
}

///Supongo que el árbol no es vacío.
int bstree_minimo (BSTree arbol){
    BSTree auxiliar = bstree_direccion_minimo(arbol);
    return auxiliar -> dato;
}

///Supongo que el árbol no es vacío y que la posición es válida.
int bstree_acceder (BSTree arbol, int posicion){
    int cantidad = bstree_nelementos(arbol -> left);
    if(posicion == cantidad)
        return arbol -> dato;

    if(posicion < cantidad)
        return bstree_acceder(arbol -> left, posicion);

    return bstree_acceder(arbol->right, posicion - cantidad - 1);
}



int main() {
    BSTree arbol = bstree_crear();
    printf("En esta linea no deberia haber nada mas:  ");
    bstree_imprimir(arbol);

    bstree_eliminar(arbol, 1);
    arbol = bstree_insertar(arbol, 1);
    arbol = bstree_eliminar(arbol, 2);
    arbol = bstree_eliminar(arbol, 1);
    (arbol == NULL) ? printf("\n\nEl arbol esta vacio. Todo bien.\n\n") : printf("\n\nEsto no deberia pasar.\n\n");

    for(int i=0; i<20; i++)
      if(i%2)
        arbol = bstree_insertar(arbol, 19 - i);
      else
        arbol = bstree_insertar(arbol, 100 - i);

    (bstree_minimo(arbol) == 0) ? printf("Minimo funciona bien.\n\n") : printf("Error en funcion minimo.\n'n");


    bstree_imprimir(arbol); printf("\n");
    (bstree_check_balance(arbol) == 0) ? printf("El arbol no esta balanceado.\n\n\n") : printf("Ya estaba balanceado de arranque.\n");


    for(int i = 0; i < 10; i++)
        printf("El elemento en la posicion %d es %d.\n",2*i, bstree_acceder(arbol, 2*i));



    arbol = bstree_balancear(arbol);
    printf("\n\nLuego de balancear:\n");
    bstree_imprimir(arbol); printf("\n");
    (bstree_check_balance(arbol) == 1) ? printf("El arbol esta balanceado.\n") : printf("Error en el balanceo.\n");


    for(int i=0; i<20; i++)
      if(i%2)
        arbol = bstree_eliminar(arbol, 19 - i);
      else
        arbol = bstree_eliminar(arbol, 100 - i);


    printf("Si esta linea esta vacia, eliminar anda bien: ");
    bstree_imprimir(arbol); printf("\n");




    return 0;
}




///EJERCICIO 14

#include <stdlib.h>
#include <stdio.h>

typedef struct RoseTree{
    int dato;
    void* hijos;
}*RTree;

typedef struct _SNodo{
    RTree puntero;
    struct _SNodo* sig;
}SNodo;

typedef SNodo* SList;

///Cosillas auxiliares

SList slist_crear() {
  return NULL;
}

void slist_destruir(SList lista) {
  SNodo *nodoAEliminar;
  while (lista != NULL) {
    nodoAEliminar = lista;
    lista = lista->sig;
    free(nodoAEliminar);
  }
}

SList slist_agregar_final(SList lista, RTree puntero) {
  SNodo *nuevoNodo = malloc(sizeof(SNodo));
  nuevoNodo->puntero = puntero;
  nuevoNodo->sig = NULL;

  if (lista == NULL)
    return nuevoNodo;

  SList nodo = lista;
  for (;nodo->sig != NULL;nodo = nodo->sig);
  /* ahora 'nodo' apunta al ultimo elemento en la lista */

  nodo->sig = nuevoNodo;
  return lista;
}

int slist_longitud (SList lista){
    int contador = 0;
    for (SNodo *nodo = lista; nodo != NULL; nodo = nodo->sig)
        contador++;
    return contador;
}

SList slist_eliminar(SList lista, int posicion) {
    if (lista == NULL || slist_longitud(lista) < posicion || posicion < 0)
        return lista;
    SNodo* pepe;
    if (posicion == 0){
        pepe = lista;
        lista = lista->sig;
        free(pepe);
        return lista;
    }
    int indice = 1;
    SList back = lista;
    for (; indice < posicion; indice++, lista = lista->sig);
    pepe = lista->sig;
    lista->sig = lista->sig->sig;
    free(pepe);
    return back;
}

void* slist_acceder(SList lista, int posicion){
    SList auxiliar = lista;
    for(int i = 0; auxiliar != NULL && i < posicion; auxiliar = auxiliar -> sig, i++);

    if(auxiliar == NULL)
        return NULL;
    return auxiliar -> puntero;
}

///Fin de cosillas auxiliares

RTree rtree_crear (int dato){
    RTree nuevo = (RTree) malloc (sizeof(struct RoseTree));
    nuevo -> dato = dato;
    nuevo -> hijos = NULL;
    return nuevo;
}

void rtree_insertar(RTree padre, RTree hijo){
    padre -> hijos = slist_agregar_final(padre -> hijos, hijo);
}

void rtree_destruir(RTree arbol){
    while(arbol -> hijos != NULL){
        rtree_destruir(slist_acceder(arbol -> hijos, 0));
        arbol -> hijos = slist_eliminar(arbol -> hijos, 0);
    }
    free(arbol);
}

int rtree_nelems(RTree arbol){

    if (arbol == NULL) return 0;

    int contador = 0, posicion = 0;
    void* hijo;
    while( (hijo = slist_acceder(arbol -> hijos, posicion)) != NULL){
        contador += rtree_nelems(hijo);
        posicion++;
    }
    return contador+1;
}

int rtree_buscar(RTree arbol, int dato){
    if (arbol == NULL) return 0;

    if(arbol -> dato == dato)
        return 1;

    void* hijo;
    int posicion = 0;
    while( (hijo = slist_acceder(arbol -> hijos, posicion)) != NULL){
        posicion++;
        if( rtree_buscar(hijo, dato) )
            return 1;
    }
    return 0;
}

///Elimina todas las apariciones del dato.
RTree rtree_eliminar(RTree arbol, int dato){
    if(arbol == NULL) return NULL;

    if(arbol -> dato == dato){
        rtree_destruir(arbol);
        return NULL;
    }

    void* hijo;
    int posicion = 0;
    while( (hijo = slist_acceder(arbol -> hijos, posicion)) != NULL){
        if( rtree_eliminar(hijo, dato) == NULL )
            arbol -> hijos = slist_eliminar(arbol -> hijos, posicion);

        posicion++;
    }
    return arbol;
}

///Imprime en "preorder";
void rtree_imprimir(RTree arbol){
    if (arbol != NULL){
        printf("%d   ",arbol -> dato);

        void* hijo;
        int posicion = 0;
        while( (hijo = slist_acceder(arbol -> hijos, posicion)) != NULL){
            rtree_imprimir(hijo);
            posicion++;
        }
    }
}


int main(){
    RTree A = rtree_crear(1);
    RTree B = rtree_crear(2);
    RTree C = rtree_crear(3);
    RTree D = rtree_crear(4);
    RTree E = rtree_crear(5);
    RTree E2 = rtree_crear(5);
    RTree F = rtree_crear(6);
    RTree G = rtree_crear(7);
    RTree H = rtree_crear(8);
    RTree I = rtree_crear(9);
    RTree J = rtree_crear(10);

    rtree_imprimir(A);printf("\n");
    printf("ELementos de una hoja: %d \n\n",rtree_nelems(A));


    rtree_insertar(B,E);
    rtree_insertar(B,F);
    rtree_insertar(D,G);
    rtree_insertar(D,H);
    rtree_insertar(D,I);
    rtree_insertar(D,J);
    rtree_insertar(D,E2);
    rtree_insertar(A,B);
    rtree_insertar(A,C);
    rtree_insertar(A,D);

    rtree_imprimir(A);printf("\n");
    printf("ELementos de todo el arbol: %d \n\n\n",rtree_nelems(A));

    (rtree_buscar(A,7))? printf("El 7 esta, ¡hurra!\n") : printf("El 7 no esta, ¡oh, no!\n");
    (! rtree_buscar(A,-1))? printf("El -1 no esta, ¡hurra!\n") : printf("El -1 esta, wat?\n");

    A = rtree_eliminar(A,5);
    printf("\n\n");rtree_imprimir(A);printf("\n");

    A = rtree_eliminar(A,1);
    rtree_imprimir(A);printf("\n");

    return 0;
}





///EJERCICIO 15


#include <stdlib.h>
#include <stdio.h>

typedef struct MulTree{
    int dato;
    struct MulTree* hijo;
    struct MulTree* hermano;
} *MTree;

///Cosillas auxiliares.

typedef struct RoseTree{
    int dato;
    void* hijos;
}*RTree;

typedef struct _SNodo{
    RTree puntero;
    struct _SNodo* sig;
}SNodo;

typedef SNodo* SList;

void* slist_acceder(SList lista, int posicion){
    SList auxiliar = lista;
    for(int i = 0; auxiliar != NULL && i < posicion; auxiliar = auxiliar -> sig, i++);

    if(auxiliar == NULL)
        return NULL;
    return auxiliar -> puntero;
}

SList slist_agregar_final(SList lista, RTree puntero) {
  SNodo *nuevoNodo = malloc(sizeof(SNodo));
  nuevoNodo->puntero = puntero;
  nuevoNodo->sig = NULL;

  if (lista == NULL)
    return nuevoNodo;

  SList nodo = lista;
  for (;nodo->sig != NULL;nodo = nodo->sig);
  /* ahora 'nodo' apunta al ultimo elemento en la lista */

  nodo->sig = nuevoNodo;
  return lista;
}

void rtree_imprimir(RTree arbol){
    if (arbol != NULL){
        printf("%d   ",arbol -> dato);

        void* hijo;
        int posicion = 0;
        while( (hijo = slist_acceder(arbol -> hijos, posicion)) != NULL){
            rtree_imprimir(hijo);
            posicion++;
        }
    }
}

RTree rtree_crear (int dato){
    RTree nuevo = (RTree) malloc (sizeof(struct RoseTree));
    nuevo -> dato = dato;
    nuevo -> hijos = NULL;
    return nuevo;
}

void rtree_insertar(RTree padre, RTree hijo){
    padre -> hijos = slist_agregar_final(padre -> hijos, hijo);
}

void imprimir_entero(int dato){
    printf("%d   ", dato);
}

void contar_nodos(int dato, int* resultado){
    (*resultado)++;
}

void sumar_nodos(int dato, int* resultado){
    *resultado+=dato;
}

///Fin de cosillas auxiliares.


MTree mtree_crear(int dato){
    MTree nuevo = (MTree) malloc(sizeof(struct MulTree));
    nuevo->dato = dato;
    nuevo->hijo = nuevo -> hermano = NULL;
    return nuevo;
}

MTree mtree_agregar_aux(MTree arbol, MTree arbolAAgregar, int posicion){
    if (posicion == 0){
        arbolAAgregar->hermano = arbol;
        return arbolAAgregar;
    }
    if (arbol == NULL)
        return arbolAAgregar;

    arbol->hermano = mtree_agregar_aux(arbol->hermano, arbolAAgregar, posicion-1);
    return arbol;
}

MTree mtree_agregar_n_hijo(MTree padre, MTree hijo, int posicion){
    if (padre == NULL) return hijo;
    if (hijo == NULL) return padre;

    padre->hijo = mtree_agregar_aux(padre->hijo, hijo, posicion);
    return padre;
}

void mtree_destruir(MTree arbol){
    if (arbol != NULL){
        mtree_destruir(arbol->hijo);
        mtree_destruir(arbol->hermano);
        free(arbol);
    }
}

///Lo recorro en inorder, lo cual es una especie de postorder en el árbol general.
void mtree_recorrer(MTree arbol, void (*Funcion) (int) ){
    if(arbol != NULL){
        mtree_recorrer(arbol->hijo, Funcion);
        Funcion(arbol->dato);
        mtree_recorrer(arbol->hermano, Funcion);
    }
}

void mtree_recorrer_extra(MTree arbol, void (*Funcion) (int, void*) , void* extra){
    if(arbol != NULL){
        mtree_recorrer_extra(arbol->hijo, Funcion, extra);
        Funcion(arbol->dato, extra);
        mtree_recorrer_extra(arbol->hermano, Funcion, extra);
    }
}

int mtree_cantidad(MTree arbol){
    int resultado = 0;
    mtree_recorrer_extra(arbol, contar_nodos, &resultado);
    return resultado;
}

int mtree_suma(MTree arbol){
    int resultado = 0;
    mtree_recorrer_extra(arbol, sumar_nodos, &resultado);
    return resultado;
}

MTree mtreeify (RTree arbolRosa){
    if (arbolRosa == NULL) return NULL;


    MTree nuevoNodo = mtree_crear(arbolRosa -> dato), punteroHijo;
    int i;
    void* punteroAuxiliar;


    for(i = 0, punteroAuxiliar = NULL; (punteroAuxiliar = slist_acceder(arbolRosa -> hijos, i)) != NULL; i++){
        punteroHijo = mtreeify (punteroAuxiliar);
        mtree_agregar_n_hijo(nuevoNodo, punteroHijo, i);

    }
    return nuevoNodo;
}


int main(){
    MTree A = mtree_crear(1);
    MTree B = mtree_crear(2);
    MTree C = mtree_crear(3);
    MTree D = mtree_crear(4);
    MTree E = mtree_crear(5);
    MTree F = mtree_crear(6);
    MTree G = mtree_crear(7);
    MTree H = mtree_crear(8);
    MTree I = mtree_crear(9);
    MTree J = mtree_crear(10);

    A = mtree_agregar_n_hijo(A,B,0);
    A = mtree_agregar_n_hijo(A,C,1);
    A = mtree_agregar_n_hijo(A,D,2);
    B = mtree_agregar_n_hijo(B,E,0);
    B = mtree_agregar_n_hijo(B,F,1);
    D = mtree_agregar_n_hijo(D,G,0);
    D = mtree_agregar_n_hijo(D,H,1);
    D = mtree_agregar_n_hijo(D,I,2);
    D = mtree_agregar_n_hijo(D,J,3);

    mtree_recorrer(A, imprimir_entero);
    printf("\nCantidad: %d\nSuma: %d\n",mtree_cantidad(A), mtree_suma(A));

    RTree Ar = rtree_crear(1);
    RTree Br = rtree_crear(2);
    RTree Cr = rtree_crear(3);
    RTree Dr = rtree_crear(4);
    RTree Er = rtree_crear(5);
    RTree Fr = rtree_crear(6);
    RTree Gr = rtree_crear(7);
    RTree Hr = rtree_crear(8);
    RTree Ir = rtree_crear(9);
    RTree Jr = rtree_crear(10);

    rtree_insertar(Br,Er);
    rtree_insertar(Br,Fr);
    rtree_insertar(Dr,Gr);
    rtree_insertar(Dr,Hr);
    rtree_insertar(Dr,Ir);
    rtree_insertar(Dr,Jr);
    rtree_insertar(Ar,Br);
    rtree_insertar(Ar,Cr);
    rtree_insertar(Ar,Dr);

    printf("\n\nImprimimos un Rose Tree (\"\"Preorder\"\"): \n");
    rtree_imprimir(Ar);

    MTree convertido = mtreeify(Ar);
    printf("\n\nUna vez convertido a MulTree(\"\"Postorder\"\"): \n");
    mtree_recorrer(convertido, imprimir_entero);

    mtree_destruir(A);
    return 0;
}