Arbre lexicographique

Version imprimable

Bonjour,

Je suis actuellement en train de travailler sur un TP impliquant la création d'un arbre lexicographique, dont voici le sujet http://prevert.upmf-grenoble.fr/Prog/Java/TP7.pdf

Donc j'ai déjà défini les classes noeudA, noeud... et arbre lexicographique comme suit :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 public class NoeudA { private NoeudA alt; public NoeudA(){ } public NoeudA(NoeudA a) { a = alt; } class Noeud extends NoeudA{ privatecharinfo; private NoeudA succ; public Noeud(char c, NoeudA s, NoeudA a) { super(a); c = info; s = succ; } public class NoeudMarque extends NoeudA { public NoeudMarque(NoeudA a){ super(a); } } //pour NoeudVide public class NoeudVide extends NoeudA { static NoeudVide s = new NoeudVide(); protected NoeudVide(){ } public static NoeudVide getInstance(){ returns; } } }
La classe la plus importante est la classe ArbreLexicographique avec toutes les méthodes qu'elle va avoir. Le fait est que j'ai un problème pour écrire ces méthodes.

J'ai donc commencé à écrire la classe arbreLexicographique comme suit :
Code:

1 2 3 4 5 6 public class ArbreLexicographique { private NoeudA racine; public ArbreLexicographique(){ racine = NoeudVide.getInstance(); }
J'ai donc commencé à écrire la méthode appartient qui dit si un mot appartient ou non à l'arbre;
Pour ce faire j'ai besoin d'une autre méthode appartient pour un Nœud cette fois si qui dit si un mot appartient ou non à un Nœud...

J'ai donc commencé à écrire cette méthode dans la classe Nœud comme suit :
Code:

1 2 3 4 5 6 7 8 9 10 11 public boolean appartient(String s){ int l= s.length(); if ((l==1) && (succinstanceof NoeudMarque)){ if(s.charAt(0)==info) returntrue; else return false; } else{ if(existe(s.charAt(0))) returnsucc.appartient(s.substring(1,l)); }
Là je bloque, je sais néanmoins que un Nœud étant défini nœud successeur et un nœud alternatif, cette fonction doit être récursive.

Je crois aussi qu'on aura besoin d'une méthode dans la classe

Nœud qui dit si un caractère existe ou non dans le Nœud
Code:

1 2 3 4 5 6 7 8 9 10 11 public boolean existe (char c) { if (c == info) { return true; // si le caractère informatif du noeud alors c'est bon } else { if (!(succ instanceof NoeudMarque)) { return succ.existe(c); } else { return false; } } }
Voici donc où je bloque je n'arrive pas à concrétiser les méthodes.

Merci d'avance pour votre aide.

C'est plus un problème d'algorithmique que de Java.

Voici des morceaux de code sous-réserve (j'ai rien testé) :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class ArbreLexicographique {
 
    private NoeudA racine; 
 
    public ArbreLexicographique(NoeudA racine) {
        this.racine=racine;
    }
 
    boolean appartient(String s){
        /*
         * Quelles sont les conventions ici ????
         */
        if (s==null) return false;
        if (racine==null) return false;
        if (racine instanceof NoeudVide) return false;
 
        /*
         * Arrêt si la chaine est épuisée
         */
        if (s.length()==0) {
            /*
             * C'est un succès si le noeud est marqué
             */
            return (racine instanceof NoeudMarque);
        }
 
        /*
         * Au moins encore un caractère...
         */
        char c=s.charAt(0);
 
        /*
         * Parcourir les noeuds horizontaux
         */
        NoeudA noeudAPossibles=racine;
        while(!(noeudAPossibles instanceof NoeudVide)) {
            /*
             * Appel reccursif...
             */
            if (noeudAPossibles instanceof Noeud && ((Noeud)noeudAPossibles).getInfo()==c) {
                /*
                 * Appel vers le niveau inférieur
                 */
                return new ArbreLexicographique(((Noeud)noeudAPossibles).getSucc()).appartient(s.substring(1));
            }
            /*
             * Le suivant horizontal 
             */
            noeudAPossibles=noeudAPossibles.getAlt();
        }
 
        return false;
    }
 
    boolean prefixe(String s) {
        //TODO
        return false;
    }
 
    boolean ajout(String s){
//        TODO
        return false;
    }
 
    boolean suppression(String s) {
//        TODO
        return false;
    }
 
    public String toString() {
//        TODO
        return super.toString();
    }
 
    void sauve(String nomFichier) {
//        TODO
    }
 
    void restaure(String nomFichier) {
//        TODO
    }
 
    int nbMots() {
//        TODO
        return 0;
    }
 
    public NoeudA getRacine() {
        return racine;
    }
}

Et les déclarations données selon ton exercice

Le noeud abstrait:

Code:

1
2
3
4
5
6
7
8
9
10
11
abstract class NoeudA {
    private NoeudA alt;
 
    public NoeudA(NoeudA a) {
        this.alt = a;
    }
 
    public NoeudA getAlt() {
        return alt;
    };
}

Le noeud qui sert de marquage (en bleu):

Code:

1
2
3
4
5
class NoeudMarque extends NoeudA {
    public NoeudMarque(NoeudA a) {
        super(a);
    }
}

Le noeud singleton vide (je vois vraiment pas l'utilité...)

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class NoeudVide extends NoeudA {
    private static NoeudVide s = null;
 
    protected NoeudVide() {
        super(null);
    }
 
    public static NoeudVide getInstance() {
        if (s == null) {
            s = new NoeudVide();
        }
        return s;
    }
}

Le noeud pour chaque caractère successif:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Noeud extends NoeudA {
    private char info;
 
    private NoeudA succ;
 
    public Noeud(char c, NoeudA s, NoeudA a) {
        super(a);
        this.succ = s;
        this.info = c;
    }
 
    public NoeudA getSucc() {
        return succ;
    }
 
    public char getInfo() {
        return info;
    };
}

Rebel64 ton code m'as l'air d'être bon, j'ai compris l'idée et je suis entrain d'avancer...

La méthode préfixe est à presque pareil, voici son code

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
boolean prefixe(String s) {
         /*
          * Les cas d'arrêts :
          */
        if(s==null)return false;
        if(racine==null)return false;
        if(racine instanceof NoeudVide) return false;
         /*
          *Si on est en fin de chaîne alors c'est un succès
         */
        if(s.length()==0)return true;
          /*
           * Sinon on a encore au moins un test à faire
           */
        char c = s.charAt(0);
        NoeudA noeudActuel = racine;
 
        while(!(noeudActuel instanceof NoeudVide)){
          /*
           * tant qu'on n'est pas à l'instance du NoeudVide on fait l'appel récursif
           */    
        if((noeudActuel instanceof Noeud)&&((Noeud)noeudActuel).getInfo()==c){
          /*
           * passage au successeur pour tester la présence du caractère suivant
          */
            ArbreLexicographique arbreSucc = new ArbreLexicographique(((Noeud)noeudActuel).getSucc());
            return arbreSucc.prefixe(s.substring(1));
        }
 
        /*
         * passage à l'alternatif
         */
        noeudActuel = noeudActuel.getAlt();
    }
        return false;
    }

10/11/2007, 12h22
rebel64

En effet pour prefix le critère de succès est moins stricte.

Attention à l'indentation du code.

Pour l'ajout :
* Tu dois chercher réccursivement comme pour appartient et prefixe.
Quand le processus réccursif s'arrête (le return false ou return true dans appartient)
* Si le noeud est un marquage ==> pas d'ajout ==> return false;
* Si il reste un morceau de chaine
Alors...il faut insérer le morceau de chaine restant
==> Pour chaque caratères qui reste dans la chaine il faut insérer un Noeud (attention de ne pas te tromper dans les chainages).
Tu peux procéder réccursivement via une méthode privée (insertString) ou itérativement sur chaque caractères.
* En fin ajouter un neud de marquage

j'ai fini la classe boolean ajout en utilisant une méthode privée insertString
la classe ajout :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
	boolean ajout(String s){
 
		/*
		 * Les cas d'arrêt 
		 */
		if(s==null) return false;
		if(racine==null)return false;
		if(racine instanceof NoeudMarque) return false;
		if(racine instanceof NoeudVide) {
			/*
			 * cas où aucun caractère de la chaîne n'est présent dans l'arbre
			 */
			insertString(s);
			return true;
		}
 
		       /*
		        * Si le mot est déjà présent dans l'arbre alors c'est faux, on n'a plus besoin de l'ajouter
		        */
		if(appartient(s)) return false;
 
 
		       /*
		        * Sinon on cherche le morceau qu'il reste à ajouter et on l'ajoute
		        */
		char c = s.charAt(0);
		NoeudA noeudActuel =  racine;
		while(!(noeudActuel instanceof NoeudVide)){
			   /*
			    * on test la présence des caractères succesifs de la chaîne dans l'arbre
			    */
			if(prefixe(""+c)){
			   /*
			    * Si le premier caractère est présent on ajoute le reste de la chaîne a 
			    * l'arbre successseur
			    */
				ArbreLexicographique arbre = new ArbreLexicographique(((Noeud)noeudActuel).getSucc());
				return(arbre.ajout(s.substring(1)));
			}
 
			noeudActuel = noeudActuel.getAlt();
 
		}
 
		return false;
	}

la classe insert String

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
private void insertString(String s){
		/*
		 * Si la chaîne est vide alors on a tout ajouté
		 */
 
		if(s.length()==0){}
		/*
		 * Sinon cherche à quel endroit l'ajouter, c'est à dire le noeud situé à 
		 * l'horizontal dont l'alternatid est vide c'est l'alternatf de ce noeud que l'on va
		 * remplacer par le nouveau noeud
		 */
		NoeudA noeudCherche = racine;
		while(!(noeudCherche instanceof NoeudVide)){
			noeudCherche = noeudCherche.getAlt();
		}
 
 
		/*
		 * Maintenant on définit ce qui va être le nouvel alterntif de 
		 * noeudCherche en utilisant la methode "construit"  de la classe Noeud 
		 */
 
			NoeudA m = ((Noeud)noeudCherche).construit(s);
			/*
			 * maintenant on construit le nouveau noeudCherché en utilisant son alternatif
			 * sous reserve qu'il soit une instance de noeud
			 */
			char c = ((Noeud)noeudCherche).getInfo();
			NoeudA suc = ((Noeud)noeudCherche).getSucc();
			noeudCherche = new Noeud(c, suc, m);
		}

pour faire cette classe j'ai crée une autre méthode dans la classe noeud :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public NoeudA construit(String s){
		//construit un nouveau noeud à partir d'une chaîne
		NoeudMarque m = new NoeudMarque();
		NoeudVide a = new NoeudVide();
		/*
		 * S'il n'y a pas de caractère on retourne un noeudMarque
		 */
		if(s.length()==0) return m;
        /*
         * Sinon il nous en reste encore au moins un a ajouter au nouveau noeud
         */
		char c = s.charAt(0);
		Noeud n = new Noeud(c,construit(s.substring(1)),a);
		return n;
	}

10/11/2007, 20h22
rebel64

Concernant ajout:

Ce n'est pas exactement ce que j'ai voulu dire:

Pour que cette ligne soit valable

Code:

if(racine instanceof NoeudMarque) return false;

il faut que le parcours de ta chaine soit épuisée....

Code:

if (s.length()==0)....

C'est la même démarche que dans appartient SAUF que c'est l'inverse:
Là où on a return false dans appartient, c'est là qu'il faudrait insérer la chaine.
Là où on à return true, ben là la chaine est déjà dans l'arbre...
:cfou:

Je n'ai pas encore lu le reste...à suivre...

Pas facile ...
Voici ce qui me parait douteux:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 boolean ajout(String s){ /* * Les cas d'arrêt */ if(s==null) return false; if(racine==null)return false; if(racine instanceof NoeudMarque) return false; if(racine instanceof NoeudVide) { /* * cas où aucun caractère de la chaîne n'est présent dans l'arbre */ insertString(s); return true; } /* * Si le mot est déjà présent dans l'arbre alors c'est faux, on n'a plus besoin de l'ajouter */ if(appartient(s)) return false; /* * Sinon on cherche le morceau qu'il reste à ajouter et on l'ajoute */ char c = s.charAt(0); NoeudA noeudActuel = racine; while(!(noeudActuel instanceof NoeudVide)){ /* * on test la présence des caractères succesifs de la chaîne dans l'arbre */ if(prefixe(""+c)){ /* * Si le premier caractère est présent on ajoute le reste de la chaîne a * l'arbre successseur */ ArbreLexicographique arbre = new ArbreLexicographique(((Noeud)noeudActuel).getSucc()); return(arbre.ajout(s.substring(1))); } noeudActuel = noeudActuel.getAlt(); } return false; }
Explications:

* Si on arrive à un marquage ET que la chaine est épuisée...
if(racine instanceof NoeudMarque && s.length==0) return false;

* Du coup
if(appartient(s)) return false;
est inutile

* On insère jamais un Noeud (caratère) SUR un noeud vide (carré rouge), mais derrière le précédant du noeud vide... Comme tu n'as pas de chainage arrière dans ton arbre; il manque donc quelques part la notion de noeud précédant pour effectuer l'insertion.
Code:

1 2 3 4 5 6 7 if(racine instanceof NoeudVide) { /* * cas où aucun caractère de la chaîne n'est présent dans l'arbre */ insertString(s); return true; }
* if(prefixe(""+c)) ...??? pourquoi faire appel à prefixe ???

if((noeudActuel instanceof Noeud)&&((Noeud)noeudActuel).getInfo()==c)...devrait convenir ?

* Le dernier

Code:

return false;

doit être remplacer par ...

Code:

return noeudActuel.ajout(s);

Sinon il va manquer des morceaux

Autre remarques:

* Un fois que l'arbre fonctionne il faudrait songer à modifier le test ...

Code:

if((noeudActuel instanceof Noeud)&&((Noeud)noeudActuel).getInfo()==c)

...de façon à insérer les noeuds par ordre alphabétique (et pas en fin de chaine à chaque fois)

* On ne peut pas faire new NoeudVide() car c'est un singleton.

Bon pour une solution...à suivre...
J'espère que c'est pas pour lundi ton truc.J'arrête ici pour le moment...A+

11/11/2007, 01h00
moufmouf

Ok je vois donc que j'ai beaucoup de lacunes à corrigé, je suis entrain de voir tous ça...:cry::cry:
mais je te rassure ce n'est pas pour lundi le truc
11/11/2007, 01h23
moufmouf
Au fait j'ai juste un petit probleme
on ne peut pas faire

Code:

return noeudActuel.ajout(s)

parceqie noeudActuel n'est pas un arbre je l'ai remplacé par ceci

Code:

return new ArbreLexicographique(noeudActuel).ajout(s);

quant au noeudvide est-ce qu'on ne pourrait pas faire appel à un constructeur de NoeudA comme suit :

Code:

new NoeudA()

ce constructeur lui même faisant appel au super constructeur défini ainsi :
Code:

1 2 3 public ArbreLexicographique(){ racine = NoeudVide.getInstance(); }
11/11/2007, 01h29
moufmouf
dsl je viens de me rendre compte que le truc que je propose pour New NoeudVide ne marche pas, j'ai complètement zappé que la classe arbreLexicographique n'était pas la classe mère de NoeudA qui n'as en fait pas de classe mère; je crois que c'est mieux de faire :
Code:

1 2 3 public NoeudA(){ alt = NoeudVide.getInstance(); }
et donc c'est ce new NoeudA() que l'on va placer au lieu de new NoeudVide();
est-ce possible??

je viens de finir la méthode suppression ;
voici :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
boolean suppression(String s) {
// on cherche à supprimer un mot du dictionnaire de l'arbre ; comment faire??
		/*
		 * Quelles sont les conventions ici?? : 
		 */
		if(!(appartient(s)))return false;
		/*
		 * Si la liste est épuisée, alors on vérifie si il ya bien eu suppression de tous les 
		 * éléments, c'est à dire si le noeud est marqué
		 */
		NoeudA noeudActuel= racine;
		if(s.length()==0){
			if(noeudActuel instanceof NoeudMarque){noeudActuel=noeudActuel.getAlt();
			                                       return true;}
			else return false;
		}
 
		/*
		 * Sinon il nous reste alors encore au moins un élément à supprimer
		 */
		char c = s.charAt(0);
		while(!(noeudActuel instanceof NoeudVide)){
			if(noeudActuel instanceof Noeud &&(c==(((Noeud)noeudActuel).getInfo()))){
	          /*
	           * si le noeud qui contient la chaîne "s" n'a qu'une seule branche alors on remplace 
	           * tout simplement ce noeud par son alternatif
	           */
				if(uneBranche(s)){
					noeudActuel=noeudActuel.getAlt();
					return true;
				}
				else {
					ArbreLexicographique arbre = new ArbreLexicographique(((Noeud)noeudActuel).getSucc());
				    return arbre.suppression(s.substring(1));
				}
 
			}
			noeudActuel=noeudActuel.getAlt();
		}
 
		return false;
	}

J'ai donc utilisé une méthode qui dit sile noeud contenant la chaîne n'a qu'une seule branche; c'est à dire si en fait on va simplement enlever ce noeud...

voici :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
private boolean uneBranche(String s){
		/*
		 * méthode qui dit si le noeud contenant la chaîne s n'a qu'une brance
		 */
		/*
		 * Si la chaîne arrive à épuisement et que la racine est un noeud marqué 
		 * alors on a gagné
		 */
		if((s.length()==0)&&racine instanceof NoeudMarque)return true;
		/*
		 * Sinon il reste encore au moins un noeud à vérifié
		 */
		char c =s.charAt(0);
		NoeudA noeudActuel = racine;
		while(!(noeudActuel instanceof NoeudVide)){
 
 
			if(noeudActuel instanceof Noeud &&(c==(((Noeud)noeudActuel).getInfo()))){
				/*
				 * si on est bien sur le noeud contenant la chaîne, on vérifie si son successeur
				 * a un alternatif vide ou pas
				 */
				NoeudA n = ((Noeud)noeudActuel).getSucc();
				if(!(n.getAlt() instanceof NoeudVide))return false;
				else {
					ArbreLexicographique arbre = new ArbreLexicographique(((Noeud)noeudActuel).getSucc());
					return arbre.uneBranche(s.substring(1));
				}
			}
			noeudActuel = noeudActuel.getAlt();
		}
		return false;
	}

14/11/2007, 01h54
rebel64
Bonsoir moufmouf

Bien vu pour

Code:

return new ArbreLexicographique(noeudActuel).ajout(s);

Bien vu aussi, l'idée de supprimer le noeud racine de la dernière branche

Par contre pour le satané singleton de cet exercice...Tu as écris

"donc c'est ce new NoeudA() que l'on va placer au lieu de new NoeudVide();
est-ce possible??"
Code:

1 2 3 public NoeudA(){ alt = NoeudVide.getInstance(); }
* NoeudA est un classe abstraite. Tu ne peux donc pas faire new NoeudA()
* NoeudVide hérite de NoeudA (bizarrement d'ailleur). Il est pas conseillé d'utiliser dans une classe abstraite une classe enfant qui implémente cette abstraction

J'ai tester une méthode pour ajouter les noeuds. Cà te permettra de vérifier ta suppression.

Je vai reprendre classe par classe :

Le noeud abstrait

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * Noeud abstrait
 */
abstract class NoeudA {
	private NoeudA alt;
 
	public NoeudA(NoeudA a) {
		this.alt = a;
	}
 
	protected NoeudA getAlt() {
		return alt;
	}
 
	protected void setAlt(NoeudA alt) {
		this.alt = alt;
	};
 
}

Ses extentions...

Le noeud de marquage ... Il va servir à la fin de mots mais aussi comme racine principale de l'arbre... ( le new NoeudA() que tu voulais faire est en fait un new NoeudMarque() )

Code:

1
2
3
4
5
6
7
8
9
10
class NoeudMarque extends NoeudA {
 
	public NoeudMarque(NoeudA a) {
		super(a);
	}
 
	public NoeudMarque() {
		this(NoeudVide.getInstance());
	}
}

Le vilain singleton vide...Qui n'a jamais de noeud alterne mais qui hérite de NoeudA :? Que faire : setAlt(this) ou setAlt(null) ???

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/**
 * Le singleton vide
 */
class NoeudVide extends NoeudA {
	private static NoeudVide s = null;
 
	protected NoeudVide() {
		super(null);
		// Là je ne sai pas ?????????????????????
		//super.setAlt(this);
	}
 
	/**
         * Pas d'alternative
         * Immutable
         */
	public void setAlt(NoeudA noeudA) {}
 
	public static NoeudVide getInstance() {
		if (s == null) {
			s = new NoeudVide();
		}
		return s;
	}
}

Le noeud de chaque caractère

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Noeud extends NoeudA {
	private char info;
 
	private NoeudA succ;
 
	/**
         * @param c = Caratère de ce noeud
         * @param s = Noeud qui succède à ce caractère
         * @param a = Noeud alternatif
         */
	public Noeud(char c, NoeudA s, NoeudA a) {
		super(a);
		this.succ = s;
		this.info = c;
	}
 
	/**
         * @return Noeud qui succède à ce caractère
         */
	public NoeudA getSucc() {
		return succ;
	}
 
	public void setSucc(NoeudA succ) {
		this.succ = succ;
	};
 
	public char getInfo() {
		return info;
	}
 
}

L'arbre lexicographique. J'ai modifier légèrement prefixe et appartient pour que les caractères soient insérés par ordre alphabétique.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
class ArbreLexicographique {
 
	private NoeudA racine; 
 
	/**
         * Création d'un arbre lexicographie
         * 
         * @param racine
         */
	public ArbreLexicographique(NoeudA racine) {
		/*
		 * On part du principe que la racine ne peut ni être LE noeud vide ni nulle 
		 */
		if (racine==null) throw new NullPointerException();
		this.racine=racine;
	}
 
	/**  
         * @param s = chaine de caractère   
         * @return La chaine appartient à l'arbre ?
         */
	public boolean appartient(String s){
		/*
		 * Quelles sont les conventions ici ????
		 */
		if (s==null) return false;
 
		/*
		 * Arrêt si la chaine est épuisée 
		 * C'est un succès si le noeud est marqué
		 */
		if (s.length()==0) return (racine instanceof NoeudMarque);
 
		/*
		 * Parcourir toutes les alternatives possibles (les noeuds horizontaux)
		 */
		for (NoeudA noeudAPossibles=racine; noeudAPossibles != NoeudVide.getInstance(); noeudAPossibles=noeudAPossibles.getAlt()) {
			/*
			 * Caractère trouvé ?
			 */
			if (noeudAPossibles instanceof Noeud) {
				if (((Noeud)noeudAPossibles).getInfo()==s.charAt(0)) {
					/*
					 * Appel réccursif vers le niveau inférieur
					 */
					return new ArbreLexicographique(((Noeud)noeudAPossibles).getSucc()).appartient(s.substring(1));
				}
				else if (((Noeud)noeudAPossibles).getInfo() > s.charAt(0)) break;
			}
		}
		return false;
	}
 
	/**
         * @param s = chaine de caractère
         * @return La chaine est un préfixe parmis les chaines enregistrées ?
         */
	public boolean prefixe(String s) {
		/*
		 * Quelles sont les conventions ici ????
		 */
		if (s==null) return false;
 
		/*
		 * Arrêt si la chaine est épuisée 
		 * C'est un succès 
		 */
		if (s.length()==0) return true;
 
		/*
		 * Parcourir toutes les alternatives possible (les noeuds horizontaux)
		 */
		for (NoeudA noeudAPossibles=racine; noeudAPossibles!=NoeudVide.getInstance(); noeudAPossibles=noeudAPossibles.getAlt()) {
			/*
			 * Caractère trouvé ?
			 */
			if (noeudAPossibles instanceof Noeud) {
				if (((Noeud)noeudAPossibles).getInfo()==s.charAt(0)) {
					/*
					 * Appel vers le niveau inférieur
					 */
					return new ArbreLexicographique(((Noeud)noeudAPossibles).getSucc()).prefixe(s.substring(1));
				}
				else if (((Noeud)noeudAPossibles).getInfo() > s.charAt(0)) break;
			}	
		}
		return false;
	}
 
	/**
         * Insérer une marque à la racine de cet arbre 
         * @return false = insertion impossible (illogique..)
         */
	private boolean insererMarque() {
		/*
		 * Sinon il faut insérer une marque au noeud du dernier caractère 
		 */
		if (racine instanceof Noeud) {
			((Noeud)racine).setSucc(new NoeudMarque(((Noeud)racine).getSucc()));
			return true;
		}
		/*
		 * Si le noeud est déjà marqué (la chaine existait déjà)
		 * Si c'est le tout premier noeud 
		 * Ici on part du principe qu'on insère pas de chaine "" au top level
		 */
		else {
			return false;
		}
	}
 
	/**
         * Insérer un branche simple derrière la racine
         * @param s = chaine à insérer
         */
	private void insereBrancheAlt(String s) {
		/*
		 * Insérer le premier caractère de le nouvelle branche de caractères entre le précédant et le suivant
		 * !!! C'est délicat !!!
		 */
		Noeud nouvelleRacine = new Noeud(s.charAt(0),new NoeudMarque(),racine.getAlt());
		racine.setAlt(nouvelleRacine);
 
		/*
		 * Ajouter ensuite le reste de la chaine ... itératif ... 
		 */
		for (int i=1;i<s.length();i++) {
			Noeud noeudSuperieur = nouvelleRacine;
			nouvelleRacine = new Noeud(s.charAt(i),new NoeudMarque(),NoeudVide.getInstance());
			noeudSuperieur.setSucc(nouvelleRacine);
		}
	}
 
	/**
         * Ajout d'une chaine à la racine de l'arbre en cours
         * 
         * @param s = Chaine à rajouter
         * @return Chaine ajoutée ?
         */
	public boolean ajout(String s){
		/*
		 * Quelles sont les conventions ici ????
		 */
		if (s==null) return false;
 
		/*
		 * Arrêt si la chaine est épuisée
		 */
		if (s.length()==0) return insererMarque();
 
		/*
		 * Recherche le premier caractère dans les alternatives
		 */
		NoeudA noeudPrecedant = racine;
 
		for (NoeudA noeudCourant=racine;  noeudCourant != NoeudVide.getInstance(); noeudCourant=noeudCourant.getAlt()) {
			/*
			 * Si le caractère existe déjà 
			 */
			if (noeudCourant instanceof Noeud) {
				if (((Noeud)noeudCourant).getInfo()==s.charAt(0)) {
					/*
					 * Appel reccursif vers le niveau inférieur
					 */
					return new ArbreLexicographique(((Noeud)noeudCourant).getSucc()).ajout(s.substring(1));
				}
				else if (((Noeud)noeudCourant).getInfo() > s.charAt(0)) break;
			}
			/*
			 * Noeud alternatif suivant 
			 */
			noeudPrecedant = noeudCourant;
		}
 
		new ArbreLexicographique(noeudPrecedant).insereBrancheAlt(s);
		return true;
	}
 
	boolean suppression(String s) {
//		TODO
		return false;
	}
 
	void sauve(String nomFichier) {
//		TODO
	}
 
	void restaure(String nomFichier) {
//		TODO
	}
 
	int nbMots() {
//		TODO
		return 0;
	}
 
	public NoeudA getRacine() {
		return racine;
	}
 
 
	public String ToString() {
		// TODO
		return super.toString();
	}
 
 
}

Et en fin un petit test sur les ajouts

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public class TestArbre {
 
	/**
         * @param args
         */
	public static void main(String[] args) {
 
		ArbreLexicographique arbreLexicographique = 
			new ArbreLexicographique(new NoeudMarque(NoeudVide.getInstance()));
 
		System.out.println("AI avant ajout: "+arbreLexicographique.appartient("AI"));
		arbreLexicographique.ajout("AI");
		System.out.println("AI après ajout: "+arbreLexicographique.appartient("AI"));
 
		arbreLexicographique.ajout("AIL");
		arbreLexicographique.ajout("AILE");
		arbreLexicographique.ajout("AINE");
		arbreLexicographique.ajout("ALE");
		arbreLexicographique.ajout("BAR");
		arbreLexicographique.ajout("BAS");
 
 
		System.out.println("A : "+arbreLexicographique.appartient("A"));
		System.out.println("AIL : "+arbreLexicographique.appartient("AIL"));
		System.out.println("AILE : "+arbreLexicographique.appartient("AILE"));
		System.out.println("AILES : "+arbreLexicographique.appartient("AILES"));
		System.out.println("AINE : "+arbreLexicographique.appartient("AINE"));
		System.out.println("BAS : "+arbreLexicographique.appartient("BAS"));
		System.out.println("BS : "+arbreLexicographique.appartient("BS"));
		System.out.println("BASE : "+arbreLexicographique.appartient("BASE"));
	}
 
}

J'ai aussi comparer le chainage avec le débugger de eclipse.Ca avais l'air correcte (comme dans l'exercice)

J'espère que çà va t'aider pour la suite...

A bientôt

Bonsoir rebel64,

Merci pour ces ajouts, je suis entrain de voir tout ça en profondeur.
J'avais juste oublié de poster la méthode toString
voici :

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public String toString() {		
		/*
		 * Quelles sont les conventions ici ?? 
		 */
		String c = "";
		if(racine==null) return "";
		if(racine instanceof NoeudVide)return "";
		/*
		 * Passe les conventions, on cherche le mot de la première branche, 
		 * on l'ajoute a la chaîne , on le supprime de l'arbre et on ajoute à la chaîne
		 * la toString() de l'arbre résidu
		 */
		NoeudA noeudPresent = racine;
		while(!(noeudPresent instanceof NoeudVide)){
			if(noeudPresent instanceof Noeud){
				/*
				 * On cherche le premier mot de l'arbre
				 */
				String s = ""; //mot de la première branche
				while(!(noeudPresent instanceof NoeudMarque)){
 
				NoeudA noeudSucc =((Noeud)noeudPresent).getSucc();
				 s+=((Noeud)noeudPresent).getInfo();
				   noeudPresent=noeudSucc;
 
				}
				/*
				 * on crée un nouvel arbre où on a supprimé le premier élément
				 */
				if(suppression(s)){
 
				c+=s+'\n'+toString(); 
				}
			}
			noeudPresent = noeudPresent.getAlt();
 
		}
		       return c;
	}

je crois que la méthode est bonne mais j'ai un petit doute ici :

Code:

1
2
3
4
if(suppression(s)){
 
				c+=s+'\n'+toString(); 
				}

Bonsoir moufmouf

Tu as raison de douter sur cette instruction.
Concernant le toString(), Je te déconseille de modifier ton arbre.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 NoeudA noeudPresent = racine; while(!(noeudPresent instanceof NoeudVide)){ if(noeudPresent instanceof Noeud){ /* * On cherche le premier mot de l'arbre */ String s = ""; //mot de la première branche while(!(noeudPresent instanceof NoeudMarque)){ NoeudA noeudSucc =((Noeud)noeudPresent).getSucc(); s+=((Noeud)noeudPresent).getInfo(); noeudPresent=noeudSucc; } /* * on crée un nouvel arbre où on a supprimé le premier élément */ if(suppression(s)){ c+=s+'\n'+toString(); } } noeudPresent = noeudPresent.getAlt(); } return c;
Pour ne pas perdre le prefixe que tu viens de soigneusement collecter (de la racine jusqu'au noeud marqué)...
Essaie de créer une méthode identique mais avec un paramètre en plus String toString(String prefix) {...} et remplace y les instructions en rouge par:
Code:

1 2 3 4 5 6 String s=prefix; ... /* * ajout du prefix trouvé et procéder réccursivement pour les sous-chaines alternatives qui suivent ce marquage */ c += s+'\n'+new ArbreLexicographiqe(noeudPresent).toString(s);
La méthode toString() devient

Code:

String toString() {return toString("")}:

Cà devrait fonctionner (mais je n'ai pas testé).

14/11/2007, 20h45
rebel64

Je viens de tester toString() avec cette modification. Il y a encore un petit problème. Cà donne bien les chaines alternatives comme prévu, mais çà ne parcours uniquement les listes des alternatives qui débutent avec un noeud de marquage. Les chaines qui on un même préfixe qui ne fait pas partie de la liste des mots manquent.

Je vai corriger çà.
14/11/2007, 21h35
moufmouf

Bonsoir rebel 64
J'ai un doute quant au

Code:

c += s+'\n'+new ArbreLexicographiqe(noeudPresent).toString(s);

Parceque en faisant cette appel , on va obtenir les mots de tous les noeuds de l'arbre et pourtant on ne veut que les mots revenant une seule fois dans l'arbre;
C'est à dire des mots dont la première lettre a un accès direct à la racine; parce qu'on rappel avec un arbre qui a une nouvelle racine; en fait je voulais rappeler avec où on a juste supprimé le premier mot(la première branche)
15/11/2007, 15h48
foufou67

une solution
Une solution
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 import java.util.*; class neuds { int gauche = 0; int droit = 1; public neuds(int gauche, int droit) { this.gauche=gauche ; this.droit = droit ; } }
il suffit de faire le comptage suivant
neuds N, brancge gauche g branche droit d, x fin de la branche
N, Ngd,Nggx,Nggx,Ngggx, Nggdx
Ngddx,Ndddx,Nddgx
et d'associer d<=>1 et g<=>0
on peut faire de la combinatoire pour connaitre le nombre de mots exact

Bonsoir moufmouf

Ta remarque est pertinante.
Voici une solution testée qui devrait être correcte pour toString()

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
	public String toString() {
		return toString("");
	}
 
	public String toString(String prefix) {
		String s="";
		for (NoeudA noeudA=racine;noeudA!=NoeudVide.getInstance();noeudA = noeudA.getAlt()) {
			if (noeudA instanceof NoeudMarque) {
				s+=prefix+"\n";
			}
			else {
				char c=((Noeud)noeudA).getInfo();
				s+=new ArbreLexicographique(((Noeud)noeudA).getSucc()).toString(prefix+c);
			}
		}
		return s;
	}

15/11/2007, 20h04
rebel64

Pour sauve() et restaure() il y a une solution très simple.
Tu peux utiliser dans les classe de java ObjectInputStream et ObjectOutputStream les méthodes readObject(racine) et writeObject(racine).
Remarques:
- Ces méthode vont procéder de façon réccursive par introspection pour toi en détectant les références circulaires... 8-) .Pas de problèmes
- Les objets et sous-objets que tu sauves via cette méthode doivent être sérialisables (class MaClasse implements Serializable).
- Si tu veux ne pas sauvegarder une propriété de la classe déclare la comme transitoires (transient)
15/11/2007, 21h59
moufmouf

Ok rebel64 merci beaucoup.
Pour sauve et restaure ce n'était pas très compliqué de toutes les façons...
A bientôt

Bonsoir moufmouf

Je ne sais pas si ce poste est encore d'actualité (...c'est pas marqué RESOLU donc je continue...)

J'ai tester le code de suppression que tu m'as proposé. Mais çà ne mache pas.
L'idée de supprimer la racine à la base de la dernière branche unique était bonne pourtant. Le problème dans ton exercice c'est que les noeud n'ont pas de chainage arrière.:cry:C'est un vrai casse tête pour retrouver le noeud qui précède cette dernière branche.

Voici un code testé et qui marche (sous réserve). J'en ai encore mal de tête:

Méthodes à ajouter dans ArbreLexicographique

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
	/**
         * @param precNoeudAlt = Noeud qui précède la racine à supprimer
         * @param noeudAlt = racine à supprimer
         * @return true = noeudAlt a été supprimé
         */
	private boolean supprimerNoeud(NoeudA precNoeudAlt,NoeudA noeudAlt) {
		if (precNoeudAlt==null || noeudAlt==null) return false;
 
		if (precNoeudAlt == NoeudVide.getInstance()) return false;
 
		if (precNoeudAlt instanceof Noeud && ((Noeud)precNoeudAlt).getSucc()==noeudAlt) {
			((Noeud)precNoeudAlt).setSucc(noeudAlt.getAlt());
			return true;
		}
		else {
			if ((precNoeudAlt).getAlt()==noeudAlt) {
				precNoeudAlt.setAlt(noeudAlt.getAlt());
				return true;
			}
		}
		return false;
	}
 
	/**
         * 
         * @param s 
         * @param n = dernier noeud qui n'a pas d'alternative
         * @return
         */
	private boolean suppression(String s,NoeudA noeudPrec,NoeudA precNoeudAlt,NoeudA noeudAlt) {
		/*
		 * Quelles sont les conventions ici ?
		 */
		if (s==null) return false;
 
		/*
		 * Arrêt si la chaine est épuisée
		 */
		if (s.length() == 0) {
			/*
			 * N'appartient pas
			 */
			if (!(racine instanceof NoeudMarque)) 
				return false;
			else
				return supprimerNoeud(precNoeudAlt, noeudAlt);
		}
 
		/*
		 * Recherche le premier caractère dans les alternatives
		 */
		NoeudA noeudCourant;
		for (noeudCourant=racine; noeudCourant != NoeudVide.getInstance(); noeudCourant=noeudCourant.getAlt()) {
 
			if (noeudCourant instanceof Noeud) {
				/*
				 * Le noeud correspond à la tête de chaine actuelle ?
				 */
				if (((Noeud)noeudCourant).getInfo()==s.charAt(0)) {
					s=s.substring(1);
					/*
					 * Le noeud courant fait partie d'une alternative
					 * 
					 */
					if (racine.getAlt() != NoeudVide.getInstance()) {
						precNoeudAlt = noeudPrec;
						noeudAlt = noeudCourant;
					}
					/*
					 * Appel réccursif pour le traitement du caractère suivant de la chaine 
					 */
					noeudPrec=noeudCourant;
					noeudCourant=((Noeud)noeudCourant).getSucc();
					return new ArbreLexicographique(noeudCourant).suppression(s,noeudPrec,precNoeudAlt,noeudAlt);
				}
				else if (((Noeud)noeudCourant).getInfo() > s.charAt(0)) return false;
			}
			noeudPrec=noeudCourant;
		}
		return false;
	}
 
	public boolean suppression(String s) {
		return suppression(s,null,null,racine);
	}

Le petit test

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
 
public class TestArbre {
 
	/**
         * @param args
         */
	public static void main(String[] args) {
 
		ArbreLexicographique arbreLexicographique = 
			new ArbreLexicographique(new NoeudMarque(NoeudVide.getInstance()));
 
		System.out.println();
		System.out.println("***************");
		System.out.println("QUELQUES AJOUTS");
		System.out.println("***************");
		System.out.println("Ajout AI ? "+arbreLexicographique.ajout("AI"));
		System.out.println("Ajout AIL ? "+arbreLexicographique.ajout("AIL"));
		System.out.println("Ajout AILE ? "+arbreLexicographique.ajout("AILE"));
		System.out.println("Ajout TOUR ? "+arbreLexicographique.ajout("TOUR"));
		System.out.println("Ajout AINE ? "+arbreLexicographique.ajout("AINE"));
		System.out.println("Ajout ALE ? "+arbreLexicographique.ajout("ALE"));
		System.out.println("Ajout BAR ? "+arbreLexicographique.ajout("BAR"));
		System.out.println("Ajout BAR ? "+arbreLexicographique.ajout("BAR"));
		System.out.println("Ajout BAS ? "+arbreLexicographique.ajout("BAS"));
		System.out.println("Ajout TOITURE ? "+arbreLexicographique.ajout("TOITURE"));
 
		System.out.println();
		System.out.println("******************");
		System.out.println("ARBRE APRES AJOUTS");
		System.out.println("******************");
		System.out.println(arbreLexicographique);	
		System.out.println();
		System.out.println("*********************");
		System.out.println("QUELQUES SUPPRESSIONS");
		System.out.println("*********************");
		System.out.println("supprime ALE ? "+arbreLexicographique.suppression("ALE"));
		System.out.println("supprime TOUR ? "+arbreLexicographique.suppression("TOUR"));
		System.out.println("TOUR appartient ? "+arbreLexicographique.appartient("TOUR"));
		System.out.println("supprime TOUR ? "+arbreLexicographique.suppression("TOUR"));
		System.out.println("supprime TOIT ? "+arbreLexicographique.suppression("TOIT"));
		System.out.println("supprime TOITURE ? "+arbreLexicographique.suppression("TOITURE"));
		System.out.println("supprime \"\" ? "+arbreLexicographique.suppression(""));
		System.out.println();
		System.out.println("************************");
		System.out.println("ARBRE APRES SUPPRESSIONS");
		System.out.println("************************");
		System.out.println(arbreLexicographique);
	}
 
}

Pour le constructeur du singleton j'ai opté pour

Code:

1
2
3
4
	protected NoeudVide() {
		super(null);
		super.setAlt(this);
	}

A bientôt

19/11/2007, 18h16
moufmouf

ok je vois tous ça . à bientôt
20/11/2007, 01h15
moufmouf

Merci rebel 64
J'ai testé et pratiquement toutes tes méthodes marches.
C'est dommage que moi mes solutions ne marchaient pas très bien...
A bientôt
18/02/2011, 18h15
cpolos

Projet similaire

Bonjour à tous,

J'ai un projet de 3 mois similaire à faire et je serais très intéressé par les codes finaux si vous les avez conservé.

Merci d'avance.