/* Manipulations sur une arborescence binaire  */
/*   - Calcul du nombre de noeuds              */
/*   - Calcul de la profondeur                 */

public class Arborescence {
  
/////////////////////////////////////////////////

/* Structure de stockage d'un noeud            */
/* d'arborescence                              */

  static class Noeud {
    int pere = -1;
    int filsDroit = -1;
    int filsGauche = -1; };

/* Creation d'une arborescence                 */

  static Noeud [] generation() {
    Noeud [] t = new Noeud[19];
    for ( int i = 0 ; i < 19 ; i++ )
      t[i] = new Noeud();
    t[0].filsDroit = 1;
    t[0].filsGauche = 3;
    t[1].pere = 0;
    t[1].filsDroit = 2;
    t[2].pere = 1;
    t[3].pere = 0;
    t[3].filsDroit = 4;
    t[3].filsGauche = 5;
    t[4].pere = 3;
    t[4].filsDroit = 6;
    t[4].filsGauche = 7;
    t[5].pere = 3;
    t[5].filsDroit = 8;
    t[5].filsGauche = 9;
    t[6].pere = 4;
    t[7].pere = 4;
    t[8].pere = 5;
    t[8].filsGauche = 10;
    t[9].pere = 5;
    t[9].filsDroit = 11;
    t[9].filsGauche = 12;
    t[10].pere = 5;
    t[11].pere = 9;
    t[11].filsDroit = 13;
    t[11].filsGauche = 14;
    t[12].pere = 9;
    t[12].filsDroit = 15;
    t[12].filsGauche = 16;
    t[13].pere = 11;
    t[14].pere = 11;
    t[15].pere = 12;
    t[16].pere = 12;
    t[16].filsDroit = 17;
    t[16].filsGauche = 18;
    t[17].pere = 16;
    t[18].pere = 16;
    return t;
  }

/* Creation d'une arborescence aleatoire       */
/* n: Le nombre de noeuds                      */
/* p: La probabilite qu'un noeud ait 2 fils    */
/* A chaque iteration de croissance, un noeud  */
/* est choisi au hasard parmi les feuilles     */
/* et un ou deux fils lui sont crees           */
/* en fonction de la probabilite p             */

  static Noeud [] generationAleatoire(int n,double p) {
    Noeud [] t = new Noeud[n];
    for ( int i = 0 ; i < n ; i++ )
      t[i] = new Noeud();
    int nbn = 1;
    while ( nbn < n ) {
      int nn = 0;
      do {
        nn = ((int) (Math.random()*10e9))%nbn; }
      while ( ( t[nn].filsDroit != -1 ) || ( t[nn].filsGauche != -1 ) );
      if ( ( Math.random() < p ) && ( nbn < n-1 ) ) {
        t[nn].filsDroit = nbn;
        t[nbn].pere = nn;
        nbn += 1;
        t[nn].filsGauche = nbn;
        t[nbn].pere = nn;
        nbn += 1; }
        else {
        if ( Math.random() < 0.5 ) {
          t[nn].filsDroit = nbn;
          t[nbn].pere = nn;
          nbn += 1; }
          else {
          t[nn].filsGauche = nbn;
          t[nbn].pere = nn;
          nbn += 1; } } }
    return t;
  }

/* Calcul du nombre de noeuds                  */
/* d'une arborescence                          */

  static int taille(Noeud [] tn,int n) {
    int nb;
    if ( n == -1 ) {
      nb = 0; }
      else {
      nb = 1 + taille(tn,tn[n].filsDroit)
             + taille(tn,tn[n].filsGauche); }
    return nb;
  }

/* Calcul de la profondeur d'une arborescence  */

  static int profondeur(Noeud [] tn,int n) {
    int prf;
    int prfd;
    int prfg;
    if ( n == -1 ) {
      prf = 0; }
      else {
      prfd = profondeur(tn,tn[n].filsDroit);
      prfg = profondeur(tn,tn[n].filsGauche);
      if ( prfd > prfg ) {
        prf = 1 + prfd; }
        else {
        prf = 1 + prfg; } }
    return prf;
  }

/* Affichage des noeuds d'une arborescence     */

  static void affichage(Noeud [] tn,int n) {
    if ( n != -1 ) {
      Ecran.formater("%4d",n);
      Ecran.formater("%4d",tn[n].filsDroit);
      Ecran.formater("%4d",tn[n].filsGauche);
      Ecran.formater("%4d\n",tn[n].pere);
      affichage(tn,tn[n].filsDroit);
      affichage(tn,tn[n].filsGauche); }
  }

/* Affectation de son pere a chaque noeud      */
/* d'une arborescence                          */

  static void affectationPeres(Noeud [] tn,int n,int p) {
    tn[n].pere = p;
    if ( tn[n].filsDroit != -1 ) {
      affectationPeres(tn,tn[n].filsDroit,n); }
    if ( tn[n].filsGauche != -1 ) {
      affectationPeres(tn,tn[n].filsGauche,n); }
  }

/* Affectation de son pere a chaque noeud      */
/* d'une arborescence                          */

  static void affectationPeres2(Noeud [] tn,int n,int p) {
    if ( n != -1 ) {
      tn[n].pere = p;
      affectationPeres2(tn,tn[n].filsDroit,n);
      affectationPeres2(tn,tn[n].filsGauche,n); }
  }
/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    { Noeud [] arborescence = generation();
      Ecran.sautDeLigne();
      Ecran.afficherln("Taille     : ",taille(arborescence,0));
      Ecran.afficherln("Profondeur : ",profondeur(arborescence,0));
      affichage(arborescence,0);
      Ecran.afficherln("Affectation des peres");
      for ( int i = 0 ; i < arborescence.length ; i += 1 ) {
        arborescence[i].pere = -2; }
      affectationPeres(arborescence,0,-1);
      affichage(arborescence,0); }
    { Noeud [] arborescence = generationAleatoire(200,1.0);
      Ecran.sautDeLigne();
      Ecran.afficherln("Taille     : ",taille(arborescence,0));
      Ecran.afficherln("Profondeur : ",profondeur(arborescence,0)); }
  }
}