ARBRE BINAIRE ORDONNÉE, UNE FAÇON DE LES STOCKÉE ET DE LES REPRÉSENTÉ, COMME SUR UNE FEUILLE DE PAPIER

package arbre;

/**
 * Arbre binaire
 */
public class ArbreBinaire
{
  //Fils droit et gauche
  private ArbreBinaire gauche,droit;
  //Donnée du noeud
  private Object donnee;

  /**
   * Construit un arbre binaire vide
   */
  public ArbreBinaire()
  {
  }

  /**
   * Construit un arbre binaire à une feuille dont la donnée est en paramètre
   */
  public ArbreBinaire(Object donnee)
  {
    this.donnee=donnee;
  }

  /**
   * Renvoie vrai si l'arbre est vide
   */
  public boolean estVide()
  {
    return donnee==null;
  }

  /**
   * Met une donnée dans le noeud
   */
  public void setDonnee(Object donnee)
  {
    if(donnee!=null)
      this.donnee=donnee;
  }

  /**
   * Récupère la donnée du noeud
   */
  public Object getDonnee()
  {
    return donnee;
  }

  /**
   * Renvoie vrai si le noeud est une feuille
   */
  public boolean estFeuille()
  {
    return (gauche==null)&&(droit==null);
  }

  /**
   * Donne un fils droit
   */
  public void setDroit(ArbreBinaire arbreBinaire)
  {
    droit=arbreBinaire;
  }

  /**
   * Donne un fils gauche
   */
  public void setGauche(ArbreBinaire arbreBinaire)
  {
    gauche=arbreBinaire;
  }

  /**
   * Retourne le fils droit
   */
  public ArbreBinaire getDroit()
  {
    return droit;
  }

  /**
   * Retourne le fils gauche
   */
  public ArbreBinaire getGauche()
  {
    return gauche;
  }

  /**
   * Retourne la profondeur de l'arbre <BR>
   * -1 si l'arbre est vide
   */
  public int getProfondeur()
  {
    //Cas vide
    if(estVide())
      return -1;
    //Cas feuille
    if(estFeuille())
      return 0;
    //On initialise les valeurs des fils droit et gauche
    int g=0;
    int d=0;
    //On calcul la prfondeur du fils gauche
    if(gauche!=null)
      g=gauche.getProfondeur();
    if(g<0)
      g=0;
    //On calcul la prfondeur du fils droit
    if(droit!=null)
      d=droit.getProfondeur();
    if(d<0)
      d=0;
    //On renvoie la profondeur
    return Math.max(g,d)+1;
  }

  //Ajoute l'arbre
  private void ajoute(ArbreBinaire ab)
  {
    if(ab==null)
      return;
    if(ab.estVide())
      return;
    ajouteDonne(ab.donnee);
    ajoute(ab.gauche);
    ajoute(ab.droit);
  }

  /**
   * Renvoie le nombre de noeud dans l'arbre
   */
  public int getNombre()
  {
    //Cas vide
    if(estVide())
      return 0;
    //Cas feuille
    if(estFeuille())
      return 1;
    //On initialise les valeurs des fils droit et gauche
    int g=0;
    int d=0;
    //On calcul lnombre de noeud du fils gauche
    if(gauche!=null)
      g=gauche.getNombre();
    //On calcul lnombre de noeud du fils droit
    if(droit!=null)
      d=droit.getNombre();
    //On renvoie le nombre de noeuds
    return d+g+1;
  }

  /**
   * Ajoute une donnée de façon équilibrée
   */
  public void ajouteDonne(Object donnee)
  {
    //Si la donnée est null, elle n'est pas ajoutée
    if(donnee==null)
      return;
    //Si l'abre est vide, alors la donnée est mise à la racine
    if(this.donnee==null)
    {
      this.donnee=donnee;
      return;
    }
    //Si on a pas de fils gauche, alors la donnée est mise à gauche
    if(gauche==null)
    {
      gauche=new ArbreBinaire(donnee);
      return;
    }
    //Si on a pas de fils droit, alors la donnée est mise à droite
    if(droit==null)
    {
      droit=new ArbreBinaire(donnee);
      return;
    }
    //Si la gauche à moins de noued que la droite, alors on ajoute à gauche, sinon à droite
    if(gauche.getNombre()<=droit.getNombre())
      gauche.ajouteDonne(donnee);
    else
      droit.ajouteDonne(donnee);
  }

  /**
   * Retire la donnée, si elle existe
   */
  public void retire(Object donnee)
  {
    //Si la donnée est null, elle n'est pas retirée
    if(donnee==null)
      return;
    //Si l'abre est vide, alors rien à faire
    if(this.donnee==null)
      return;
    //Si la donnée est à la racine
    if(donnee.equals(this.donnee))
    {
      ArbreBinaire g=gauche;
      if(g!=null)
        g.retire(donnee);
      ArbreBinaire d=droit;
      if(d!=null)
        d.retire(donnee);
      donnee=null;
      gauche=null;
      droit=null;
      ajoute(g);
      ajoute(d);
      return;
    }
    //Si on a un fils gauche, on la retire de la gauche
    if(gauche!=null)
      gauche.retire(donnee);
    //Si on a un fils droit,  on la retire de la droite
    if(droit!=null)
      droit.retire(donnee);
  }
}

------------
package arbre;

/**
 * Arbre binaire ordonnée, les valeurs supérieurs à droite, les inférieurs à gauche, on ne peut pas stokée deux fois la même valeure
 */
public class ArbreBinaireOrdonne
{
  //Arbre binaire de stockage
  private ArbreBinaire arbre=new ArbreBinaire();

  /**
   * Crée un arbre binaire ordonée vide
   */
  public ArbreBinaireOrdonne()
  {
  }

  /**
   * Renvoie vrai si l'arbre est vide
   */
  public boolean estVide()
  {
    return arbre.estVide();
  }

  /**
   * Renvoie vrai si l'arbre est une feuille
   */
  public boolean estFeuille()
  {
    return arbre.estFeuille();
  }

  /**
   * Récupére la donnée de la racine
   */
  public Comparable getDonnee()
  {
    return (Comparable)arbre.getDonnee();
  }

  /**
   * Ajoute une donnée
   */
  public void ajoute(Comparable donnee)
  {
    if(donnee==null)
      return;
    add(donnee);
  }

  //Ajoute une donnée
  private void add(Comparable donnee)
  {
    //Arbre parcouru pour recherché ou mettre la donnée
    ArbreBinaire ab=arbre;
    do
    {
      //Si l'arbre est vide alors on met la donnée à la racine
      if(ab.estVide())
      {
        ab.setDonnee(donnee);
        return;
      }
      //Si la donnée est la donnée de la racine, on arrête, pas deux fois la même donnée
      if(donnee.compareTo(ab.getDonnee())==0)
        return;
      //Si la donnée est inférieure à la racine, alors on regarde à gauche, sinon à droite
      if(donnee.compareTo(ab.getDonnee())<0)
      {
        //On récupére le fils gauche
        ArbreBinaire g=ab.getGauche();
        //Si le fils gauche n'existe pas, alors le fils gauche devient une feuille ayant la donnée
        if(g==null)
        {
          g=new ArbreBinaire(donnee);
          ab.setGauche(g);
          return;
        }
        //Si le fils gauche est vide, alors le fils gauche devient une feuille ayant la donnée
        if(g.estVide())
        {
          g.setDonnee(donnee);
          return;
        }
        //L'arbre de recherche devient le fils gauche
        ab=g;
      }
      else
      {
        //On récupére le fils droit
        ArbreBinaire d=ab.getDroit();
        //Si le fils droit n'existe pas, alors le fils droit devient une feuille ayant la donnée
        if(d==null)
        {
          d=new ArbreBinaire(donnee);
          ab.setDroit(d);
          return;
        }
        //Si le fils droit est vide, alors le fils droit devient une feuille ayant la donnée
        if(d.estVide())
        {
          d.setDonnee(donnee);
          return;
        }
        //L'arbre de recherche devient le fils droit
        ab=d;
      }
    }while(true);
  }

  //Ajoute un arbre binaire
  private void ajoute(ArbreBinaire ab)
  {
    //Si l'abre binaire est null, rien a ajouter
    if(ab==null)
      return;
    //Si l'abre binaire est vide, rien a ajouter
    if(ab.estVide())
      return;
    //On ajoute la donnée de la racine
    add((Comparable)ab.getDonnee());
    //Si le fils gauche existe, on ajoute le fils gauche
    ArbreBinaire g=ab.getGauche();
    if(g!=null)
      ajoute(g);
    //Si le fils droit existe, on ajoute le fils droit
    ArbreBinaire d=ab.getDroit();
    if(d!=null)
      ajoute(d);
  }

  /**
   * Renvoie un arbre binaire ordoné contenant la partie gauche de l'arbre
   */
  public ArbreBinaireOrdonne getGauche()
  {
    //Si l'arbre est vide ou est une feuille, alors il n'a pas de partie gauche
    if(arbre.estVide()||arbre.estFeuille())
      return null;
    if(arbre.getGauche()==null)
      return null;
    //On récupère la partie gauche
    ArbreBinaireOrdonne abo=new ArbreBinaireOrdonne();
    abo.arbre=arbre.getGauche();
    return abo;
  }

  /**
   * Renvoie un arbre binaire ordoné contenant la partie droite de l'arbre
   */
  public ArbreBinaireOrdonne getDroit()
  {
    //Si l'arbre est vide ou est une feuille, alors il n'a pas de partie droite
    if(arbre.estVide()||arbre.estFeuille())
      return null;
    if(arbre.getDroit()==null)
      return null;
    //On récupère la partie droite
    ArbreBinaireOrdonne abo=new ArbreBinaireOrdonne();
    abo.arbre=arbre.getDroit();
    return abo;
  }

  /**
   * Renvoie la profondeur de l'arbre
   */
  public int getProfondeur()
  {
    return arbre.getProfondeur();
  }

  /**
   * Effectue une opération qui renvoie un arbre un peu plus équlibré, afin d'optimiser la recherche
   */
  public ArbreBinaireOrdonne equilibre()
  {
    //Si l'arbre est vide ou une feuille, il n'y a rien a faire
    if(estVide()||estFeuille())
      return this;
    //On cacul le nombre de noeud à droite et à gauche
    int g=0;
    int d=0;
    ArbreBinaire ga=arbre.getGauche();
    ArbreBinaire dr=arbre.getDroit();
    if(ga!=null)
      g=ga.getNombre();
    if(dr!=null)
      d=dr.getNombre();
    //Si le branche droite et la gauche on un nombre égale, à une unité prés, de noued, alors on va tenter d'optimiser chaqu'une des branches
    if(Math.abs(g-d)<2)
    {
      //On créé un arbre temporaire de travail
      ArbreBinaireOrdonne abo=new ArbreBinaireOrdonne();
      //On lui donne la même racine
      abo.add(getDonnee());
      //On récupére la version équilibré de la partie gauche
      ArbreBinaireOrdonne gauche=getGauche();
      if(gauche!=null)
        gauche=gauche.equilibre();
      //On récupére la version équilibré de la partie droite
      ArbreBinaireOrdonne droit=getDroit();
      if(droit!=null)
        droit=droit.equilibre();
      //On ajoute, si elle existe, la partie gauche ainsi calculée à l'arbre temporaire
      if(gauche!=null)
        abo.arbre.setGauche(gauche.arbre);
      //On ajoute, si elle existe, la partie droite ainsi calculée à l'arbre temporaire
      if(droit!=null)
        abo.arbre.setDroit(droit.arbre);
      //On renvoie l'arbre temporaire
      return abo;
    }
    //S'il il y a plus de noeud à gauche qu'a droite, alor on va prendre le fils gauche comme racine, et ajoutée la racine et partie droite
    if(g>d)
    {
      //On récupére la partie gauche
      ArbreBinaireOrdonne abo=getGauche();
      //On y ajoute la racine
      abo.add(getDonnee());
      //On y ajoute la partie droite
      abo.ajoute(dr);
      //On renvoie le résultat
      return abo;
    }
    //On récupére la partie droite
    ArbreBinaireOrdonne abo=getDroit();
    //On y ajoute la racine
    abo.add(getDonnee());
    //On y ajoute la partie gauche
    abo.ajoute(ga);
    //On renvoie le résultat
    return abo;
  }

  /**
   * Renvoie vrai si la donnée est dans l'arbre
   */
  public boolean dedans(Comparable donnee)
  {
    //Arbre de parcours
    ArbreBinaire ab=arbre;
    do
    {
      //Si l'arbre est vide, la donnée ne peut pas y être
      if(ab.estVide())
        return false;
      //Si la donnée est la racine, alors on la trouvé
      if(donnee.compareTo(ab.getDonnee())==0)
        return true;
      //Si la donnée est inférieure à la racine, on recherche dans la partie gauche, sinon dans la partie droite
      if(donnee.compareTo(ab.getDonnee())<0)
      {
        //On récupère la partie gauche
        ArbreBinaire g=ab.getGauche();
        //Si il n'y a pas de partie gauche, alors la donnée ,n'est pas dans l'arbre
        if(g==null)
          return false;
        //Si la partie gauche est vide, alors la donnée ,n'est pas dans l'arbre
        if(g.estVide())
          return false;
        //On va cherché dans la partie gauche
        ab=g;
      }
      else
      {
        //On récupère la partie droite
        ArbreBinaire d=ab.getDroit();
        //Si il n'y a pas de partie droite, alors la donnée ,n'est pas dans l'arbre
        if(d==null)
          return false;
        //Si la partie droite est vide, alors la donnée ,n'est pas dans l'arbre
        if(d.estVide())
          return false;
        //On va cherché dans la partie droite
        ab=d;
      }
    }while(true);
  }

  /**
   * Retire la donnee, si' elle existe
   */
  public void retire(Comparable donnee)
  {
    arbre.retire(donnee);
  }
}
----------------------
package arbre;

import javax.swing.JComponent;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Color;
import java.awt.Font;
import java.awt.FontMetrics;

/**
 * Composant dessinant un arbre binaire ordonée
 */
public class ComposantArbreBinaireOrdonne extends JComponent
{
  //Arbre binaire ordoné dessiné
  private ArbreBinaireOrdonne arbre=new ArbreBinaireOrdonne();
  //Dimension par défaut
  private Dimension dimension=new Dimension(200,200);

  /**
   * Crée le composant
   */
  public ComposantArbreBinaireOrdonne()
  {
    setForeground(Color.black);
    setBackground(Color.white);
    setFont(new Font("Dialog",Font.PLAIN,10));
    setPreferredSize(dimension);
  }

  /**
   * Ajoute une donnée à l'arbre
   */
  public void ajoute(Comparable donnee)
  {
    arbre.ajoute(donnee);
  }

  //Hauteur du texte en pixel
  private int hauteurTexte(FontMetrics fm)
  {
    return fm.getHeight();
  }

  //Largeur de la chaine en pixel
  private int largeurTexte(FontMetrics fm,String chaine)
  {
    return fm.stringWidth(chaine);
  }

  //Décalage qu'il faut appliquer pour positioné le texte en hauteur
  private int decalageTexte(FontMetrics fm)
  {
    return fm.getAscent();
  }

  //Ecrit la chaine centre selon x, à la hauteur y
  private void ecrireCentrer(int x,int y,String chaine,Graphics g,FontMetrics fm)
  {
    int lg=largeurTexte(fm,chaine);
    g.drawString(chaine,x-lg/2,y+decalageTexte(fm));
  }

  // Dessine le composant
  protected void paintComponent(Graphics g)
  {
    //Vide le composant
    g.setColor(getBackground());
    g.fillRect(0,0,getWidth(),getHeight());
    //Intialise la fonction de mesure,la police et la couleur d'écriture
    FontMetrics fm=getFontMetrics(getFont());
    g.setFont(getFont());
    g.setColor(getForeground());
    //Intialise la position de départ
    int x=0;
    int y=0;
    int larg=getWidth();
    int haut=hauteurTexte(fm);
    //Dessine l'arbre en lui même
    dessine(g,arbre,x,y,larg,haut,fm);
  }

  //Dessine un arbre
  //g : Graphics permétant de dessiner
  //abo : Arbre binair ordonné à dessiner
  //x : abscisse minimale du rectangle de dessin
  //y : ordonée du dessin
  //larg : largeur reservée au dessin
  //haut : hauteur d'une chaine de caractères
  //fm : Mesusreur de chaîne de caractères
  private void dessine(Graphics g,ArbreBinaireOrdonne abo,int x,int y,int larg,int haut,FontMetrics fm)
  {
    //Si l'arbre est null, rien à dessiner
    if(abo==null)
      return;
    //Si l'arbre est vide, rien à dessiner
    if(abo.estVide())
      return;
    //Initialise
    int lg=larg/2;
    int mx=x+lg;
    //Ecrit la racine
    ecrireCentrer(mx,y,abo.getDonnee().toString(),g,fm);
    //Incrèmente y
    y += haut;
    //S'il s'agit d'une feuille, le dessin est terminé
    if(abo.estFeuille())
      return;
    //On dessine, si il existe, le coté gauche
    ArbreBinaireOrdonne gauche=abo.getGauche();
    if(gauche!=null)
    {
      //on dessine un lien entre la racine et la branche gauche
      g.drawLine(mx,y,x+lg/2,y+20);
      //On dessine la branche gauche
      dessine(g,gauche,x,y+20,lg,haut,fm);
    }
    //On dessine, si il existe, le coté droit
    ArbreBinaireOrdonne droit=abo.getDroit();
    if(droit!=null)
    {
      //on dessine un lien entre la racine et la branche droite
      g.drawLine(mx,y,mx+lg/2,y+20);
      //On dessine la branche droite
      dessine(g,droit,mx,y+20,lg,haut,fm);
    }
  }

  /**
   * Donne la dimension optimale au composant
   */
  public void calculDimension()
  {
    //Intialise le mesureuer de chaîne
    FontMetrics fm=getFontMetrics(getFont());
    //Calcul de la hauteur
    int nb=arbre.getProfondeur()+1;
    int haut=hauteurTexte(fm)*nb+20*(nb-1);
    if(haut<100)
      haut=100;
    //Calcul de la largeur
    int larg=0;
    if(!arbre.estVide())
      larg=calculLarg(arbre,fm);
    if(larg<100)
      larg=100;
    //Impose la dimension calculée
    dimension.setSize(larg,haut);
    setPreferredSize(dimension);
    setSize(dimension);
    setMinimumSize(dimension);
    setMaximumSize(dimension);
  }

  //Cacul la largeur minimale d'un arbre
  private int calculLarg(ArbreBinaireOrdonne abo,FontMetrics fm)
  {
    //On intialise avec la largeur de la racine
    int lg=largeurTexte(fm,abo.getDonnee().toString());
    //On calcul largeur de la partie gauche
    int g=0;
    ArbreBinaireOrdonne ga=abo.getGauche();
    if(ga!=null)
      g=calculLarg(ga,fm);
    //On calcul largeur de la partie droite
    int d=0;
    ArbreBinaireOrdonne dr=abo.getDroit();
    if(dr!=null)
      d=calculLarg(dr,fm);
    //On en déduit la rgeur des deux réunis
    int s=2*Math.max(d,g)+5;
    //On renvoie la largeur minimale pour un affichage lisible
    return Math.max(lg,s);
  }

  /**
   * Equilibre l'arbre, permet d'optimiser la recherche et l'affichage
   */
  public void equilibre()
  {
    //Equilibre au maximum
    equilibreMax(getFontMetrics(getFont()));
    //Optimise la dimension
    calculDimension();
    //Redéssine
    repaint();
  }

  //Equilibre au maximum
  private void equilibreMax(FontMetrics fm)
  {
    //On récupére la prochaine étape d'équilbrage
    ArbreBinaireOrdonne abo=arbre.equilibre();
    //Tant que la prochaine étape est mieux que l'état actuel
    while(abo.getProfondeur()<arbre.getProfondeur())
    {
      //L'état actuel de vient cette étape
      arbre=abo;
      //On calcul l'étape d'après
      abo=arbre.equilibre();
    }
  }

  /**
   * Renvoie vrai si l'arbre contient la donnée
   */
  public boolean contient(Comparable donnee)
  {
    return arbre.dedans(donnee);
  }

  /**
   * Retire la donnee, si' elle existe
   */
  public void retire(Comparable donnee)
  {
    arbre.retire(donnee);
  }
}
-------------------
package arbre;

import javax.swing.JFrame;
import java.awt.*;
import java.util.Random;
import javax.swing.JScrollPane;
import javax.swing.JButton;
import java.awt.event.ActionListener;
import java.awt.event.ActionEvent;
import javax.swing.JPanel;
import java.awt.event.WindowEvent;

/**
 * Fait un test
 */
public class Test extends JFrame
{
  private ComposantArbreBinaireOrdonne cabo=new ComposantArbreBinaireOrdonne();
  private Random hazard=new Random();
  public Test()
  {
    getContentPane().setLayout(new BorderLayout());
/*
    cabo.ajoute(new Integer(8));
    cabo.ajoute(new Integer(5));
    cabo.ajoute(new Integer(10));
    cabo.ajoute(new Integer(2));
    cabo.ajoute(new Integer(3));
*/
    for(int i=0;i<12/*3*/;i++)
      cabo.ajoute(new Integer((int)(hazard.nextDouble()*1000)));
    cabo.calculDimension();
    getContentPane().add(new JScrollPane(cabo),BorderLayout.CENTER);
    JButton bouton=new JButton("Equilibre");
    bouton.addActionListener
    (
      new ActionListener()
      {
        public void actionPerformed(ActionEvent ae)
        {
          Thread t=new Thread()
          {
            public void run()
            {
              long lg=System.currentTimeMillis();
              cabo.equilibre();
              lg=System.currentTimeMillis()-lg;
              long s=lg/1000;
              long m=s/60;
              long h=m/60;
              long j=h/24;
              System.out.println("Temps : "+lg+"ms"+" soit "+j+"jour "+(h-j*24)+"h"+(m-h*60)+"m"+(s-m*60)+"s"+(lg-s*1000)+"ms");
              pack();
            }
          };
          t.start();
        }
      }
    );
    JPanel pano=new JPanel(new FlowLayout());
    pano.add(bouton);
    bouton=new JButton("Ajout");
    bouton.addActionListener
    (
      new ActionListener()
      {
        public void actionPerformed(ActionEvent ae)
        {
          cabo.ajoute(new Integer((int)(hazard.nextDouble()*2000-1000)));
          cabo.calculDimension();
          repaint();
          pack();
        }
      }
    );
    pano.add(bouton);
    getContentPane().add(pano,BorderLayout.SOUTH);
    pack();
    setVisible(true);
  }
  protected void processWindowEvent(WindowEvent we)
  {
    if(we.getID()==WindowEvent.WINDOW_CLOSING)
    {
      dispose();
      System.exit(0);
    }
  }
  public static void main(String[] args) throws HeadlessException
  {
    Test test = new Test();
  }
}