Cours CNAM par J. Laforgue

Exemple11_ArbreBinaire

Retour

Télécharger

Exemple de creation d'une classe qui gere un arbre binaire
- d'entier
- d'expression arithmetique

Arbre.java

import java.util.*;

// Classe de definition d'un arbre binaire
//
public class Arbre
{
    private Object value;   // Valeur du noeud
    private Arbre gauche;   // Sous-arbre gauche
    private Arbre droit;    // Sous-arbre droit
    
    // Constructeurs
    //
    public Arbre(Object value)
    {
        this.value = value;
    }
    //
    public Arbre(Object value,Arbre g,Arbre d)
    {
        this.value = value;
        gauche = g;
        droit = d;
    }
    //
    public Arbre(Object value,Object og,Object od)
    {
        this.value = value;
        gauche = new Arbre(og);
        droit  = new Arbre(od);
    }

// Retourne la valeur du noeud
    //
    public Object getValue()
    {
        return(value);
    }

// Retourne l'arbre gauche de l'arbre
    //
    public Arbre getGauche()
    {
        return(gauche);
    }

// Retourne l'arbre droit de l'arbre
    //
    public Arbre getDroit()
    {
        return(droit);
    }

// Ajoute un noeud a gauche de l'arbre
    //
    public Arbre addGauche(Object value)
    {
        Arbre n = new Arbre(value);
        gauche = n;
        return n;
    }

// Ajoute un arbre a gauche de l'arbre
    //
    public void setGauche(Arbre n)
    {
        gauche = n;
    }

// Ajoute un noeud a droite de l'arbre
    //
    public Arbre addDroit(Object value)
    {
        Arbre n = new Arbre(value);
        droit=n;
        return n;
    }
    
    // Ajoute un arbre a droite de l'arbre
    //
    public void setDroit(Arbre n)
    {
        droit = n;
    }

// Teste si un noeud est une feuille
    public boolean siFeuille()
    {
        return ( (gauche==null) && (droit==null) );
    }

// Affiche la totalite de l'arbre avec 
    //  indentation
    //
    public void afficher()
    {
        afficherInfixeRec(this,0);
    }
    static public void afficherInfixeRec(Arbre a,int n)
    {
        if (a!=null)
            {
                afficherInfixeRec(a.getGauche(),n+3);
                System.out.println(marge(n)+a.getValue());
                afficherInfixeRec(a.getDroit(),n+3);
            }
    }

// Affiche les noeuds de l'arbre suivant un 
    //  parcours prefixe
    //
    public void afficherPrefixe()
    {
        afficherPrefixeRec(this);
        System.out.println();
    }
    static public void afficherPrefixeRec(Arbre a)
    {
        if (a!=null)
            {
                System.out.print(a.getValue()+" ");
                afficherPrefixeRec(a.getGauche());
                afficherPrefixeRec(a.getDroit());
            }
    }

// Affiche les noeuds de l'arbre suivant un 
    //  parcours suffixe
    //
    public void afficherSuffixe()
    {
        afficherSuffixeRec(this);
        System.out.println();
    }
    static public void afficherSuffixeRec(Arbre a)
    {
        if (a!=null)
            {
                afficherSuffixeRec(a.getGauche());
                afficherSuffixeRec(a.getDroit());
                System.out.print(a.getValue()+" ");
            }
    }

// Retourne la marche de n caract blancs
    //
    static private String marge(int m)
    {
        String s="";
        for(int i=0;i<m;i++)s=s+" ";
        return s;
    }
}

Exemple11.java

// Exemple de creation d'une classe qui gere un arbre binaire
//   - d'entier
//   - d'expression arithmetique
//
public class Exemple11
{
    // Programme principal
    //
    public static void main(String... args)
    {
        System.out.println("Execution de Exemple11");

// Creation d'un arbre d'entier
        //
        Arbre n1 = new Arbre(new Integer(10));
        Arbre n2 = n1.addGauche(5);
        Arbre n3 = n1.addDroit(21);
        Arbre n4 = n2.addGauche(1);
        Arbre n5 = n2.addDroit(7);
        Arbre n6 = n3.addGauche(13);

// Creation d'un autre arbre d'entier
        Arbre r1 = new Arbre(new Integer(100));
        Arbre r2 = r1.addDroit(200);
        r2.addGauche(300);
        r2.addDroit(400);

// Ajout du 2eme arbre a un noeud du 1er
        //
        n3.setDroit(r1);

// Affichages de l'arbre

n1.afficher();
        System.out.println("---------------");

n1.afficherPrefixe();
        System.out.println("---------------");

n1.afficherSuffixe();
        System.out.println("---------------");

// Creation d'un arbre d'expression arithmetique
        //
        Arbre e1 = new Arbre("*",
                             new Arbre("+",3.5,5.5),
                             new Arbre("/",10.0,20.0));
        e1.afficher();

// Resultat : 4.5
        System.out.println("Resultat: "+calculer(e1));

}

// Methode qui calcule une expression arithmetique
    //
    private static double calculer(Arbre a)
    {
        if (a.siFeuille()) return (double)(a.getValue());
        else
            {
                if (a.getValue().equals("*"))
                    return calculer(a.getGauche())*calculer(a.getDroit());
                if (a.getValue().equals("+"))
                    return calculer(a.getGauche())+calculer(a.getDroit());
                if (a.getValue().equals("/"))
                    return calculer(a.getGauche())/calculer(a.getDroit());
                return(0);
            }
    }
}

compil.bat
run.bat

Cours d'Informatique par Jacques LAFORGUE

Retour

Télécharger

Cours d'Informatique
par Jacques LAFORGUE