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

public class ArborescenceBinaire {
  
/////////////////////////////////////////////////

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

  static class Noeud {
    Noeud pere = null;
    Noeud filsDroit = null;
    Noeud filsGauche = null; };

/* Creation d'une arborescence                 */

  static Noeud generationAleatoire(double prb,double inc) {
    Noeud n;
    if ( Math.random() < prb ) {
      n = null; }
      else {
      n = new Noeud();
      n.filsDroit = generationAleatoire(prb+inc,inc);
      if ( n.filsDroit != null )
        n.filsDroit.pere = n;
      n.filsGauche = generationAleatoire(prb+inc,inc);
      if ( n.filsGauche != null )
        n.filsGauche.pere = n; }
    return n;
  }

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

  static int taille(Noeud n) {
    int nb;
    if ( n == null ) {
      nb = 0; }
      else {
      nb = 1 + taille(n.filsDroit)
             + taille(n.filsGauche); }
    return nb;
  }

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

  static int profondeur(Noeud n) {
    int prf;
    int prfd;
    int prfg;
    if ( n == null ) {
      prf = 0; }
      else {
      prfd = profondeur(n.filsDroit);
      prfg = profondeur(n.filsGauche);
      if ( prfd > prfg ) {
        prf = 1 + prfd; }
        else {
        prf = 1 + prfg; } }
    return prf;
  }
/////////////////////////////////////////////////
  
/* Programme principal                         */

  public static void main(String [] args) {
    Noeud racine;
    double probabilite;
    double increment;
    Ecran.afficher("Increment de probabilite ? ");
    increment = Clavier.saisirDouble();
    racine = generationAleatoire(0.0,increment);
    Ecran.sautDeLigne();
    Ecran.afficherln("Taille     : ",taille(racine));
    Ecran.afficherln("Profondeur : ",profondeur(racine));
  }
}