nero/bianco

/*
Esempio A

        3
       /  \
      4    -1
          /  \
         2    -1
        /     /
       8     7
Nodi centrali attesi = 3:
key 1° nodo -> 3
key 2° nodo -> -1
key 3° nodo -> -1
       */
/*
Esempio B
                 -1
                 / \
            ->  2   3  <-
                    /
                   0  <-
                  / \
                 5   4
*/
#include <stdio.h>
#include <stdlib.h>

struct node{
  int key;
  struct node * p;
  struct node * left;
  struct node * right;
};

typedef struct node * Node;

Node newnode(int);
void visitPreOrder(Node);
void visitSimmetrica(Node);
void visitPostOrder(Node);
void esProp1(Node, int);
void esProp2(Node, int*);
Node costruzioneEs12();
int contaNodiCentrali(Node, int, int*);

int main(){
  int numFoglie;
  int sumCammino = 0;
  int nodiCentrali;
  Node /*es12,*/ esB;
  /*es12 = costruzioneEs12();*/
  esB = newnode(-1);
  esB->left = newnode(2);
  esB->right = newnode(3);
  esB->right->left = newnode(0);
  esB->right->left->left = newnode(5);
  esB->right->left->right = newnode(4);

  /* ******************************** */
  /*printf("\n*** Esercizio anno 2012    ***\n");*/
  /*visitPreOrder(es12);*/
  /*visitSimmetrica(es12);*/
  /*visitPostOrder(es12);*/

  /*printf("\n*** Esercizio propedeutico 1°   ***\n");
  esProp1(root, sumCammino);*/

  /*printf("\n*** Esercizio propedeutico 2   ***\n");
  esProp2(root, &numFoglie);
  printf("Le foglie dell'albero sono: %d\n", numFoglie);
  */

  /*printf("\n*** Esercizio propedeutico 2   ***\n");
  esProp2(root, &numFoglie);
  printf("Le foglie dell'albero sono: %d\n", numFoglie);*/

  /*viewPreOrder(es12);*/
  /*viewSimmetrica(es12);*/
  /*viewPostOrder(es12);*/

  /*printf("\n*** Esercizio 12   ***\n");
  viewSimmetrica(es12);
  printf("\n");
  esProp1(es12, sumCammino);*/
  /* ******************************** */
  /* ******************************** */
  printf("\n*** Esercizio anno 2014   ***\n");
  /*visitPreOrder(esB);*/
  visitSimmetrica(esB);
  /*visitPostOrder(esB);*/
  nodiCentrali = contaNodiCentrali(esB, sumCammino, &numFoglie);
  printf("Nell' esB i nodi centrali sono: %d", nodiCentrali);
  /* ******************************** */
  printf("\nThe end\n");
  return 0;
}

Node costruzioneEs12(){
  Node radice = (Node) malloc(sizeof(struct node));
  radice->p = NULL;
  radice->key = 3;
  radice->left = (Node) malloc(sizeof(struct node));
  radice->left->p = radice;
  radice->left->key = 4;
  radice->left->left = NULL;
  radice->left->right = NULL;
  radice->right = (Node) malloc(sizeof(struct node));
  radice->right->p = radice;
  radice->right->key = -1;
  radice->right->left = (Node) malloc(sizeof(struct node));
  radice->right->left->p = radice->right;
  radice->right->left->key = 2;
  radice->right->right = (Node) malloc(sizeof(struct node));
  radice->right->right->p = radice->right;
  radice->right->right->key = -1 ;
  radice->right->right->right = NULL;
  radice->right->left->left =  (Node) malloc(sizeof(struct node));
  radice->right->left->left->p = radice->right->left;
  radice->right->left->left->key = 8;
  radice->right->left->left->left = NULL;
  radice->right->left->left->right = NULL;
  radice->right->right->left = (Node) malloc(sizeof(struct node));
  radice->right->right->left->key = 7 ;
  radice->right->right->left->p = radice->right->right->left;
  radice->right->right->left->left = NULL;
  radice->right->right->left->right = NULL;
  return radice;
}



Node newnode(int value){
  Node node  =  (Node) malloc(sizeof(struct node));
  node->key  =  value;
  node->p = NULL;
  node->left  =  NULL;
  node->right  =  NULL;
  return node;
}



void visitPreOrder(Node n){
  if (n!=NULL)
  {
    printf("%d\n", n->key);
    visitPreOrder(n->left);
    visitPreOrder(n->right);
  }
}

void visitSimmetrica(Node n){
  if (n!=NULL)
  {
    visitSimmetrica(n->left);
    printf("%d\n", n->key);
    visitSimmetrica(n->right);
  }
}

void visitPostOrder(Node n){
  if (n!=NULL)
  {
    visitPostOrder(n->left);
    visitPostOrder(n->right);
    printf("%d\n", n->key);
  }
}


/* *** Eserciz propedeutici  *** */
void esProp1(Node n, int sum){
  if(n==NULL)
    return;
  /*else if(n->left==NULL && n->right==NULL)
  {
    printf("%d\n", sum+n->key);
    return;
  }*/
  else
  {
    esProp1(n->left, sum+n->key);
    esProp1(n->right, sum+n->key);
    printf("%d\n", sum+n->key);
    return;
  }
}

/* *** Esercizio propedeutico 2 *** */
void esProp2(Node n, int *num){
  int numSx, numDx;
  numSx = *num;
  numDx = *num;
  if(n==NULL)
  {
    *num = 0;
  }
  else if(n->left==NULL && n->right==NULL)
  {
    *num = 1;
  }
  else
  {
    esProp2(n->left, &numSx);
    esProp2(n->right, &numDx);
    *num = numSx+numDx;
  }
}

int contaNodiCentrali(Node r, int sum, int* foglie){
  int nodi, nodiSx, nodiDx, numFSx, numFDx;
  if(r==NULL){
    *foglie=0;
    return 0;
  }
  else if(r->left==NULL && r->right==NULL){
    *foglie = 1;
    if(sum+r->key == 1)
      return 1;
    return 0;
  }
  else{
    nodiDx = contaNodiCentrali(r->left,sum+r->key, &numFSx);
    nodiSx = contaNodiCentrali(r->right,sum+r->key, &numFDx);
    *foglie = numFSx+numFDx;
    nodi = nodiSx + nodiDx;
    if(sum + r->key == *foglie)
      nodi++;
    return nodi;
  }
}