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