/***   FUNZIONI PER GESTIRE  ALBERI BINARI DI RICERCA  DI INTERI  ***/

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

#include "tree.h"




/*

Per rappresentare un albero  occorre definire una variabile  root
di tipo  node* (radice dell'albero).

- se root vale NULL, root rappresenta l'albero vuoto.

- altrimenti, root e'  l'indirizzo al nodo radice dell'albero.

*/




/*** CREAZIONE DI ALBERI ****/

/* Crea un albero  vuoto  */

node *newTree() {
    return NULL;
}


/*   Crea un nuovo nodo contenente il valore n e  restituisce  
     l'indirizzo del nuovo nodo   */

node *newNode(int n){
    node *new;

    new = malloc(sizeof(node));
    if (new==NULL) {// errore malloc() 
      fprintf(stderr, "malloc(): errore allocazione memoria\n");
      exit(-1); // termina il programma restituendo -1 all'ambiente chiamante 
    }
    new->key = n;
    new->left = new->right = new->up = NULL; 
    return new;
}


/* Inserisce un nuovo nodo contenente  n nell'albero  r 
   e  restituisce  l'indirizzo dell'albero ottenuto   */

node *treeInsert(int n, node *r){
    node  *q, *pq;
    if(r==NULL)  // l'albero e' vuoto 
	return newNode(n);
    else{ //  attraversa l'albero fino a trovare il punto di inserimento 
      q = r;
      while(q != NULL){
	pq = q;
	q = (n < q->key) ?  q->left :  q->right;
      }
      //  pq  e' il padre del nuovo nodo 
      q = newNode(n);
      if (n < pq ->key)
	pq->left = q;
      else
	pq->right = q;
      q->up = pq;
      return r;
    }
}

/*** ELIMINAZIONE DI UN NODO ****/

/* Libera la memoria occupata dal nodo p (si assume p!=NULL) */

void freeNode(node *p){
  free(p);
}



/* Cancella  il nodo x  dall'albero r 
   e restituisce la radice dell'albero ottenuto */ 


node *treeDelete(node *x, node *r){
  node *s;  // nodo che deve sostituire x 
  
  
  /***  Trova  il nodo s  che deve sostituire x  ***/
  
  if(x->left==NULL && x->right == NULL)
    /** CASO 1: x non ha figli **/
    s = NULL;
  else if (x->left == NULL || x->right == NULL)
    /** CASO 2:  x  ha un solo figlio   **/
    s = (x->left != NULL) ? x->left : x->right;
  else{ /**  CASO 3: x  ha  due figli   **/
/* s e' il figlio piu' a destra  nel sottoalbero sin. di x */
    s = x->left;
    while(s->right != NULL)
      s = s->right;
 /*  il figlio sin. di s prende il posto di s */
    if(s->up == x) // s e' figlio sin. di x 
      x->left = s->left;
    else  // s e' figlio destro di s->up 
      s->up->right = s->left;
    if (s->left != NULL)
      s->left->up = s->up;
    // i nuovi  figli di s sono i figli di x 
    s->left = x->left;
    if (s->left != NULL)
      s->left->up = s;
    s->right = x->right;
    if (s->right != NULL)
      s->right->up = s;
  }
  
  /***  Il nodo  x e' sostituito da s.
	Se x e' la radice, s diventa la radice del nuovo albero ***/
  
  if(x == r){ // x e' la radice 
    r = s; // nuova radice 
    if(r!= NULL) // il nuovo albero non e' vuoto 
      r->up = NULL;
  }
  else if (x->up->left == x){ // x e' figlio sin. 
    x->up->left = s;
    if(s != NULL) // s non e' vuoto 
      s->up = x->up;
  }
  else{  
    x->up->right = s;
    if(s != NULL) // s non e' vuoto 
      s->up = x->up;
  } 
 
 /***  Eliminazione del nodo x ***/

  freeNode(x); 
  return r;
}










/**** RICERCA ****/

/*   Cerca  un nodo di  valore n nell'albero r. 
     Se il nodo esiste restituisce il suo indirizzo, altrimenti restituisce NULL  */

node *treeFind(int n, node *r){
  while (r!=NULL   &&  r->key != n)
    r = (n < r->key) ? r->left : r->right;
  return r;
}


/* Restituisce l'indirizzo del nodo di valore minimo dell'albero  r */

node* treeMin(node *r){
  for( ; r->left!= NULL; r=r->left);
  return r;     
}

/* Restituisce l'indirizzo del nodo di valore massimo dell'albero  r */

node* treeMax(node *r){
    for( ; r->right!= NULL; r=r->right);
    return r;     
}



/**** STAMPA  DI UN ALBERO  ****/



/* Stampa il valore del nodo p */

void printNode(node  *p){
  printf("%d ", p->key);
}

/* Stampa l'albero di radice r in ordine simmerico */

void printInorder(node *r) { 
  if(r != NULL){
    printInorder(r->left); 
    printNode(r);
    printInorder(r->right); 
  }
}




/* Cancella l'albero di radice r */

void treeDestroy(node * r){
  if(r != NULL){// occorre una strategia postorder 
    treeDestroy(r->left);
    treeDestroy(r->right);
    freeNode(r);
  }
}