Exo 8.1

Fichier Arbin.java :

import java.util.Stack;

public interface Arbin {
    Object contenu();
    boolean existeFilsGauche();
    boolean existeFilsDroit();
    Arbin filsGauche();
    Arbin filsDroit();

    Arbin nouveau();
    void fixerContenu(Object c);
    void creerFilsGauche();
    void creerFilsDroit();

    boolean externe();
    void preOrdre(Visiteur traitement, Stack chemin);
    void inOrdre(Visiteur traitement, Stack chemin);
    int hauteur();

    void setPosition(int x, int y);
    int getX();
    int getY();
    int calculerPositions(int marge, int haut);
}

Fichier Visiteur.java :

import java.util.Stack;

public interface Visiteur {
    void visiter(Stack chemin);
}

Exo 8.2

Fichier ArbinAbstrait.java :

import java.util.Stack;

public abstract class ArbinAbstrait implements Arbin {

    public boolean externe() {
        return ! (existeFilsGauche() || existeFilsDroit());
    }

    public String toString() {
        return "<" + contenu() + "," + filsGauche() + "," + filsDroit() + ">";
    }

    public void preOrdre(Visiteur traitement, Stack chemin) {
        chemin.push(this);
        traitement.visiter(chemin);
        if (existeFilsGauche())
            filsGauche().preOrdre(traitement, chemin);
        if (existeFilsDroit())
            filsDroit().preOrdre(traitement, chemin);
        chemin.pop();
    }

    public void inOrdre(Visiteur traitement, Stack chemin) {
        chemin.push(this);
        if (existeFilsGauche())
            filsGauche().inOrdre(traitement, chemin);
        traitement.visiter(chemin);
        if (existeFilsDroit())
            filsDroit().inOrdre(traitement, chemin);
        chemin.pop();
    }

    public void setPosition(int x, int y) {
    }
    public int getX() {
        return -1;
    }
    public int getY() {
        return -1;
    }

    public int calculerPositions(int marge, int haut) {
        if (existeFilsGauche())
            marge = filsGauche().calculerPositions(marge, haut + 1);
        setPosition(marge, haut);
        marge++;
        if (existeFilsDroit())
            marge = filsDroit().calculerPositions(marge, haut + 1);
        return marge;
    }

    public int hauteur() {
        int a, b;
        a = b = 0;
        if (existeFilsGauche())
            a = filsGauche().hauteur();
        if (existeFilsDroit())
            b = filsDroit().hauteur();
        return Math.max(a, b) + 1;
    }
}

Exo 8.3

Fichier Pepiniere.java :

import java.util.Random;

public class Pepiniere {

    public static void arbinTrivial(Arbin a, int min, int max) {
        int mil = (min + max) / 2;
        a.fixerContenu(new Integer(mil));
        if (min < mil) {
            a.creerFilsGauche();
            arbinTrivial(a.filsGauche(), min, mil - 1);
        }
        if (mil < max) {
            a.creerFilsDroit();
            arbinTrivial(a.filsDroit(), mil + 1, max);
        }
    }

    public static void arbinAleatoire(Arbin a, int n, int min, int max) {
        a.fixerContenu(new Integer(entierAleatoire(min, max)));
        if (n > 1) {
            int p = entierAleatoire(0, n - 1);
            if (p > 0) {
                a.creerFilsGauche();
                arbinAleatoire(a.filsGauche(), p, min, max);
            }
            p = n - 1 - p;
            if (p > 0) {
                a.creerFilsDroit();
                arbinAleatoire(a.filsDroit(), p, min, max);
            }
        }
    }

    private static Random alea = new Random();
    private static int entierAleatoire(int min, int max) {
        return (int)(min + alea.nextDouble() * (max + 1 - min));
    }
}

Exo 8.4

Fichier DessinArbin.java :

import java.awt.*;
import java.awt.event.*;

public class DessinArbin extends Panel {
    static final int DX = 10;
    static final int DY = 8;
    static final Color couleurInterne = new Color(200, 255, 200);
    static final Color couleurExterne = new Color(255, 200, 200);

    private Arbin arbre;
    int hauteur, largeur;
    double dx, dy;
    int mx, my;

    public DessinArbin(Arbin a) {
        arbre = a;
        largeur = arbre.calculerPositions(0, 0);
        hauteur = arbre.hauteur();
        setBackground(Color.white);
    }

    public void paint(Graphics g) {
        if (arbre != null) {
            Dimension d = getSize();
            dx = ((double) d.width) / (largeur + 1);
            dy = ((double) d.height) / hauteur;
            mx = (int) dx;
            my = (int) (dy / 2);
            int a1 = (int)(mx + dx * arbre.getX());
            int b1 = (int)(my + dy * arbre.getY());
            dessiner(arbre, g, a1, b1);
        }
    }

    private void dessiner(Arbin a, Graphics g, int a1, int b1) {
        int a2, b2;
        if (a.existeFilsGauche()) {
            a2 = (int)(mx + dx * a.filsGauche().getX());
            b2 = (int)(my + dy * a.filsGauche().getY());
            g.drawLine(a1, b1, a2, b2);
            dessiner(a.filsGauche(), g, a2, b2);
        }
        if (a.existeFilsDroit()) {
            a2 = (int)(mx + dx * a.filsDroit().getX());
            b2 = (int)(my + dy * a.filsDroit().getY());
            g.drawLine(a1, b1, a2, b2);
            dessiner(a.filsDroit(), g, a2, b2);
        }

        Color c = g.getColor();
        g.setColor(a.externe() ? couleurExterne : couleurInterne);
        g.fillRect(a1 - DX, b1 - DY, 2 * DX, 2 * DY);
        g.setColor(c);
        g.drawRect(a1 - DX, b1 - DY, 2 * DX, 2 * DY);

        String s = a.contenu().toString();
        if (s.length() < 2)
            s = " " + s;
        g.drawString(s, a1 - DX + 3, b1 + DY - 2);
    }
}

Exo 8.5

Fichier ArbinPointe.java :

public class ArbinPointe extends ArbinAbstrait {
    private Object contenu;
    private ArbinPointe filsGauche;
    private ArbinPointe filsDroit;

    public Arbin nouveau() {
        return new ArbinPointe();
    }

    public Object contenu() {
        return contenu;
    }
    public boolean existeFilsGauche() {
        return filsGauche != null;
    }
    public boolean existeFilsDroit() {
        return filsDroit != null;
    }
    public Arbin filsGauche() {
        return filsGauche;
    }
    public Arbin filsDroit() {
        return filsDroit;
    }

    public void fixerContenu(Object c) {
        contenu = c;
    }
    public void creerFilsGauche() {
        filsGauche = (ArbinPointe) nouveau();
    }
    public void creerFilsDroit() {
        filsDroit = (ArbinPointe) nouveau();
    }
}

Exo 8.6

Fichier ArbinPointePlace.java :

 public class ArbinPointePlace extends ArbinPointe {
    private int x;
    private int y;

    public Arbin nouveau() {
        return new ArbinPointePlace();
    }

    public void setPosition(int x, int y) {
        this.x = x;
        this.y = y;
    }
    public int getX() {
        return x;
    }
    public int getY() {
        return y;
    }
}

Exo 8.7

Fichier Principal.java :

import java.util.Stack;
import java.awt.*;

public class Principal {
    public static int n = 40;

    public static void main(String[] args) {
        Arbin a = new ArbinPointePlace();
        Pepiniere.arbinAleatoire(a, n, 0, 99);

            // Pour contrôle:
        a.inOrdre(new AffichageBienIndente(), new Stack());

        Frame cadre = new Frame("Arbre binaire aléatoire - n = " + n);
        cadre.addWindowListener(new WindowAdapter() {
            public void windowClosing(WindowEvent evt) {
                System.exit(0);
            }
        });
        cadre.setSize(600, 450);
        cadre.add(new DessinArbin(a));
        cadre.setVisible(true);

    }
}

class AffichageBienIndente implements Visiteur {
    public void visiter(Stack chemin) {
        for (int i = chemin.size(); i > 0; i--)
            System.out.print(" . ");
        System.out.println( ((Arbin)chemin.peek()).contenu() );
    }
}