package ab;                                                        // juin 04 //
import iv.FileAttente;

/** Implémentation d'arbres binaires et de plusieurs représentations. */
public class ArbreBinaire {
  /*private*/ protected Object racine; // protected pour énumérations
  /*private*/ protected ArbreBinaire gauche,droit;// sous-arbres gauche et droit

  /** Crée un arbre binaire composé d'un seul noeud (cad une feuille). */
  public ArbreBinaire(Object racine) { this.racine=racine;}

  /** Crée un arbre binaire composé de la racine spécifiée et des deux
   *  sous-arbres spécifiés */
  public ArbreBinaire(Object racine, ArbreBinaire gauche, ArbreBinaire droit) {
    this(racine);
    this.gauche=gauche;
    this.droit=droit;
    }

   /** Crée un arbre binaire composé de la racine spécifiée et du sous-arbre
    *  spécifié (qui sera les sous-arbre droit). */
  public ArbreBinaire(Object racine, ArbreBinaire droit) {
   this(racine, null,droit);
   }

   /** Crée un arbre binaire vide de la hauteur spécifiée. */                 //
  public ArbreBinaire(int n) {                                                //
   this("");                                                                  //
   if (n>1) { this.racine="";                                                 //
              this.gauche = new ArbreBinaire(n - 1);                          //
              this.droit = new ArbreBinaire(n-1);                             //
              }                                                               //
  }                                                                           //


  /** Teste si cet Arbre binaire est une feuille. */
  public boolean feuille() {
    return this.gauche == null && this.droit == null ;
    }

  /** Renvoie une représentation indentée de cet arbre binaire, c'est-à-dire :
   *  pour chaque sous-arbre il y a passage à la ligne et une indentation
   *  proportionnelle à la profondeur de ce sous-arbre. */
   public String toString() { return this.toString("");}
   /** Renvoie une représentation indentée de cet arbre binaire indentée de plus
    *  de la chaine spécifiée. */
   public String toString(String indent) {
      String s= indent;
      s+=this.racine;
      indent += "   ";
      if (!(this.gauche==null)) s+="\n"+this.gauche.toString(indent);
      if (!(this.droit==null)) s+="\n"+this.droit.toString(indent);
      return s;
      }

   /** Renvoie une représentation préfixe de cet arbre binaire,
    *  c'est-à-dire dans l'ordre :
    *  racine puis sous-arbres gauche puis droit préfixés. */
   public String formePrefixe() {
     String s = ""+this.racine;
     if (this.gauche != null) s+=" "+ this.gauche.formePrefixe();
     if (this.droit != null) s+= " "+this.droit.formePrefixe();
     return s;
     }

  /** Renvoie une représentation postfixe de cet arbre binaire,
  *  c'est-à-dire dans l'ordre :
  *  sous-arbres gauche puis droit postfixés puis racine. */
  public String formePostfixe() {
    String s = "";
    if (this.gauche != null) s+= this.gauche.formePostfixe();
    if (this.droit != null) s+= this.droit.formePostfixe();
    s+=" "+this.racine;
    return s;
    }

   /** Renvoie une représentation infixe de cet arbre binaire,
    *  c'est-à-dire dans l'ordre :
    *  sous-arbre gauche infixe puis racine puis sous-arbre droit infixe. */
   public String formeInfixe() {
     String s="";
     if (this.gauche != null) s+= this.gauche.formeInfixe();
     s+=" "+this.racine;
     if (this.droit != null) s+= this.droit.formeInfixe();
     return s ;
     }

    /** Renvoie une représentation infixe de cet arbre binaire dans laquelle
     *  chaque sous-arbre est entouré de parenthèses sauf les feuilles. */
    public String formeInfixePar() {
      boolean par = false;
      if (! this.feuille()) par = true;
      String s="";
      if (par) s+= " (";
      if (this.gauche != null) s+= this.gauche.formeInfixePar();
      s+=" "+this.racine;
      if (this.droit != null) s+= this.droit.formeInfixePar();
      if (par) s+=" )";
      return s ;
      }

    /** Renvoie une représentation par niveau de cet arbre binaire,           //
     *  c'est-à-dire dans l'ordre :                                           //
     *  racine puis noeuds de niveau 1, puis 2, etc ... . */                  //
    public String formeParNiveau() {                                          //
      FileAttente f = new FileAttente();                                      //
      f.rentrer(this);                                                        //
      String s="";                                                            //
      while (! f.vide()) {                                                    //
        ArbreBinaire a = (ArbreBinaire) f.premier();                          //
        s+= a.racine+" ";                                                     //
        f.sortir();                                                           //
        if (a.gauche != null) f.rentrer(a.gauche);                            //
        if (a.droit != null) f.rentrer(a.droit);                              //
        }                                                                     //
      return s;                                                               //
      }                                                                       //

    /** Renvoie une représentation de cet arbre binaire par niveaux séparés   //
     *  par la marque spécifiée. */                                           //
    public String formeParNiveauxSepares(Object marque) {                     //
      FileAttente f = new FileAttente();                                      //
      f.rentrer(marque);                                                      //
      f.rentrer(this);                                                        //
      String s="";                                                            //
      while (! f.vide()) {                                                    //
        Object o = f.premier();                                               //
        f.sortir();                                                           //
        if (f.vide()) s+= marque;                                             //
        else if (o instanceof ArbreBinaire) {                                 //
                ArbreBinaire a = (ArbreBinaire) o;                            //
                if (a.gauche != null) f.rentrer(a.gauche);                    //
                if (a.droit != null) f.rentrer(a.droit);                      //
                s+= a.racine+" ";                                             //
                }                                                             //
              else {f.rentrer(o);s+=o;}                                       //
              }                                                               //
      return s;                                                               //
      }                                                                       //
               

      //
      // Représentations
      //                  pré/post/infixes/par niveau
      // utilisant des énumérations
      //


    public String formePrefixeEn() {
      String s = "";
      for (EnumerationPrefixe e = new EnumerationPrefixe(this);
                                           e.hasMoreElements();)
         s+=e.nextElement()+" ";
         return s;
         }



     public String formePostfixeEn() {
       String s = "";
       for (EnumerationPostfixe e = new EnumerationPostfixe(this);
                                              e.hasMoreElements();)
         s+=e.nextElement()+" ";
         return s;
         }
     public String formeInfixeEn() {
       String s="";
       for (EnumerationInfixe e = new EnumerationInfixe(this);
                                          e.hasMoreElements();)
         s+=e.nextElement()+" ";
         return s ;
         }
     public String formeInfixeParEn() {
       String s="";
       for (EnumerationInfixePar e = new EnumerationInfixePar(this);
                                                e.hasMoreElements();)
         s+=e.nextElement()+" ";
         return s ;
         }


      public String formeParNiveauEn() {                                      //
        String s="";                                                          //
        for (EnumerationParNiveau e = new EnumerationParNiveau(this);         //
                                                e.hasMoreElements();)         //
         s+=e.nextElement()+" ";                                              //
         return s ;                                                           //
      }                                                                       //

      public String formeParNiveauxSeparesEn(Object marque) {                 //
        String s="";                                                          //
        for (EnumerationParNiveauxSepares e =                                 //
                           new EnumerationParNiveauxSepares(this,marque);     //
                   e.hasMoreElements();)                                      //
         s+=" "+e.nextElement();                                              //
         return s ;                                                           //
      }                                                                       //

}