Arbre binaire ordonnée, une façon de les stockée et de les représenté, comme sur une feuille de papier

Soyez le premier à donner votre avis sur cette source.

Snippet vu 18 320 fois - Téléchargée 26 fois

Contenu du snippet

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;

/**

  • 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(); } }

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

A voir également

Ajouter un commentaire Commentaires
Messages postés
4
Date d'inscription
mercredi 17 novembre 2004
Statut
Membre
Dernière intervention
12 décembre 2004

ce code est très intéressant,néanmoins te serais-t-il possible d'effectuer la même opération "ajout" en proposant à celui qui exécute le programme d'entrer au clavier un nombre que lui aurait choisi et de choisir une taille saisie au clavier pour l'arbre.
Si tu peux améliorer ceci se serait génial, j'ai essayé de le faire mais j'ai besoin d'utiliser un gros package jar pour cela.
Si tu peux le faire en utilisant un nombre de méthodes minimales se serait bien.

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.