import java.io.*;
import java.lang.*;
import java.util.*;

public class Arbre {

  // \esc{De'claration d'un arbre, voir page \pageref{prog:declaration-arb}}
  int      contenu;
  Arbre    filsG;
  Arbre    filsD;

  Arbre (int v, Arbre a, Arbre b) {
      this.contenu = v;
      this.filsG = a;
      this.filsD = b;
  }

  public static Arbre nouvelArbre (int v, Arbre a, Arbre b) {
  // \esc{Ajouter dans un arbre, voir page \pageref{prog:ajouter-arb}}

      return new Arbre (v, a, b);
  }

  static void imprimer (Arbre a, int tab) {
  // \esc{Impression d'un arbre, voir page \pageref{prog:imprimer-arb}} 

    if (a != null) {
      System.out.print (leftFormatted (3, a.contenu + "") + "     "); 
        imprimer (a.filsD, tab + 8);
        if (a.filsG != null) {
            System.out.println ();
            for (int i = 1; i <= tab; ++i)
                System.out.print (" ");
        }
        imprimer (a.filsG, tab);
    }
  }

  static String leftFormatted (int size, String s) {

    StringBuffer t = new StringBuffer (s);
    for (int i = s.length(); i < size; ++i)
        t = t.append(" ");
    return new String (t);
  }

  static void imprimerArbre (Arbre a) {
    imprimer (a, 0);
    System.out.println ();
  }

  static int taille (Arbre a) {
  // \esc{Taille d'un arbre, voir page \pageref{prog:taille-arbre}} */

    if (a == null)
        return 0;
    else
        return 1 + taille (a.filsG) + taille (a.filsD);
  }

  static Arbre recherche (int v, Arbre a) {
  // \esc{Arbre de recherche, voir page \pageref{prog:recherche-arb-recherche}} 
    Arbre      r;

    r = null;
    if (a == null || v == a.contenu)
         return a;
    else
         if (v < a.contenu)
             return recherche (v, a.filsG);
         else
             return recherche (v, a.filsD);
  }

  static Arbre ajouter (int v, Arbre a) {

    if (a == null)
        a = nouvelArbre (v, null, null);
    else if (v <= a.contenu)
        a.filsG = ajouter (v, a.filsG);
    else
        a.filsD = ajouter (v, a.filsD);
    return a;
  }


  public static void main(String args[]) {

    Arbre a5, a7;
    a5 = nouvelArbre (12, nouvelArbre (8, nouvelArbre (6, null, null), null),
                          nouvelArbre (13, null, null));
    a7 = nouvelArbre (20, nouvelArbre (3, nouvelArbre (3, null, null), a5),
                          nouvelArbre (25, nouvelArbre (21, null, null),
                                           nouvelArbre (28, null, null)));
    imprimerArbre (a7);
    System.out.println (taille (a7));
    System.out.println ("------------------------");

    Arbre a = ajouter (20, ajouter (10, ajouter (5, ajouter (15, 
              ajouter (30, ajouter (25, null))))));

    imprimerArbre (a);
    System.out.println ("--------------");
    imprimerArbre (recherche (30, a));
    System.out.println ("--------------");
    imprimerArbre (recherche (25, a));
    System.out.println ("--------------");
    imprimerArbre (recherche (5, a));
    System.out.println ("--------------");
    imprimerArbre (recherche (7, a));
  }
}