Ce code est composé de quatre classes.
ArbreBinaire, stocke des données dans un arbre binaire
ArbreBinaireOrdonne, stocke des données dans un arbre binaire ordonné, cad qu'il n'est stocké qu'une fois les données, que les valeurs inférieures sont à gauche, et les supérieurs à droite
ComposantArbreBinaireOrdonne, qui dessine un ArbreBinaireOrdonne comme on dessine un arbre sur une feuille de papier. C'est à dire la racine au mileu en haut;, les neouds dessous répartis équilibré. Elle contient une méthode equilibre qui équilibre l'arbre.
Test, qui teste le tout et monte un exemple d'utilisation
Source / Exemple :
package arbre;
/**
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);
}
/**
public void setDroit(ArbreBinaire arbreBinaire)
{
droit=arbreBinaire;
}
/**
public void setGauche(ArbreBinaire arbreBinaire)
{
gauche=arbreBinaire;
}
/**
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();
}
/**
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);
/**
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;
/**
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();
}
}
Conclusion :
Ce n'est pas fini, il manque, l'affichage d'ïcones, et d'autres fonctions, je les ferais si çà interesse un ceratin nombre de personne.
JHelp
Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.