您好，我尝试在 4h 之前编写 AVLTree 扩展 BST 的代码，但现在没有，我不知道为什么。我只是在代码中添加一些注释。
错误 ：
Exception in thread "main" java.lang.ClassCastException: Arbre$Noeud cannot be cast to ArbreAVL$NoeudAVL
at ArbreAVL.insertion(ArbreAVL.java:162)
at Test.main(Test.java:9)
代码：
public class Arbre {
protected Noeud racine;
protected static class Noeud {
protected int data;
protected Noeud filsG;
protected Noeud filsD;
public Noeud(int data, Noeud filsG, Noeud filsD) {
this.data = data;
this.filsG = filsG;
this.filsD = filsD;
}
public Noeud(int data) {
this.data = data;
this.filsD = null;
this.filsG = null;
}
}
public Arbre() {
this.racine = null;
}
public Arbre(int data) {
this.racine = new Noeud(data);
}
public Arbre(int data, Noeud filsG, Noeud filsD) {
this.racine = new Noeud(data, filsG, filsD);
}
/*
* L’adjonction d’un nouvel élément à un arbre modifie l’arbre.
*/
public void insertion(int data) {
this.racine = insertion(this.racine, data);
}
private Noeud insertion(Noeud racine, int data) {
if (racine == null)
return new Noeud(data);
if (data < racine.data)
racine.filsG = insertion(racine.filsG, data);
else
racine.filsD = insertion(racine.filsD, data);
return racine;
}
/*
* Une méthode booléenne qui teste la présence d’un élément dans l’arbre
*/
public boolean recherche(int data) {
return recherche(this.racine, data);
}
private boolean recherche(Noeud racine, int data) {
if (racine == null)
return false;
else {
if (data < racine.data)
return recherche(racine.filsG, data);
else if (data > racine.data)
return recherche(racine.filsD, data);
else
return true;
}
}
/*
*
*/
public void suppMin() {
if (this.racine != null)
this.racine = suppMin(this.racine);
}
private Noeud suppMin(Noeud n) {
if (n.filsG == null)
return n.filsD;
n.filsG = suppMin(n.filsG);
return n;
}
/*
* recherche le nœud portant la clé à supprimer
*/
public void supprimer(int data) {
this.racine = supprimer(this.racine, data);
}
/*
* recherche le nœud portant la clé à supprimer
*/
private Noeud supprimer(Noeud n, int data) {
if (n == null)
return null;
if (data < n.data)
n.filsG = supprimer(n.filsG, data);
else if (data > n.data)
n.filsD = supprimer(n.filsD, data);
else {
if (n.filsD == null)
return n.filsG;
if (n.filsG == null)
return n.filsD;
Noeud t = n;
n = getMin(t.filsD);
n.filsD = suppMin(t.filsD);
n.filsG = t.filsG;
}
return n;
}
private Noeud getMin(Noeud n) {
if (n == null)
return null;
else if (n.filsG == null)
return n;
else
return getMin(n.filsG);
}
public int hauteur() {
return hauteur(this.racine);
};
public int hauteur(Noeud n) {
if (n == null)
return -1;
else
return 1 + Math.max(hauteur(n.filsG), hauteur(n.filsD));
}
public boolean isVide() {
return (this.racine == null);
}
public Noeud getRacine() {
return racine;
}
public void setRacine(Noeud racine) {
this.racine = racine;
}
/*
* Serialisation
* @see java.lang.Object#toString()
*/
public String toString() {
return toString(this.racine);
}
private String toString(Noeud n) {
if (n == null)
return "()";
else {
String s = "(";
s = s + toString(n.filsG);
s = s + "," + n.data + ",";
s = s + toString(n.filsD);
return s + ")";
}
}
}
public class ArbreAVL extends Arbre{
protected class NoeudAVL extends Noeud {
protected int factorEquilibre;
public NoeudAVL(int cle, Noeud filsG, Noeud filsD, int b) {
super(cle, filsG, filsD);
this.factorEquilibre = b;
}
public NoeudAVL(int cle) {
super(cle);
this.factorEquilibre = 0;
}
/*
* Une rotation rééquilibre une partie de l’arbre en réarrangeant les
* nœuds tout en préservant la propriété qui fait que le nœud gauche est
* plus petit que son père, qui est lui même inférieur à son fils droit;
* cette propriété doit être maintenue pour que l’arbre reste un arbre
* binaire de recherche. Après la rotation, les facteurs d’équilibre de
* tous les nœuds du sous-arbre équilibré sont +1, −1 et 0. Il n’y a que
* quatre types de rotations à réaliser : les GG (gauche-gauche), GD
* (gauche-droite), DD (droite-droite) et DG (droite-gauche).
*/
protected NoeudAVL rotationG() {
NoeudAVL oldRacine = this;
NoeudAVL newRacine = (NoeudAVL) filsD;
oldRacine.filsD = newRacine.filsG;
newRacine.filsG = oldRacine;
int a = oldRacine.factorEquilibre;
int b = newRacine.factorEquilibre;
if (b <= 0) {
newRacine.factorEquilibre = (a >= 1) ? b - 1 : a + b - 2;
oldRacine.factorEquilibre = a - 1;
} else {
newRacine.factorEquilibre = (a <= b) ? a - 2 : b - 1;
oldRacine.factorEquilibre = a - b - 1;
}
return newRacine;
}
protected NoeudAVL rotationD() {
NoeudAVL oldRacine = this;
NoeudAVL newRacine = (NoeudAVL) filsG;
oldRacine.filsG = newRacine.filsD;
newRacine.filsD = oldRacine;
int a = oldRacine.factorEquilibre;
int b = newRacine.factorEquilibre;
if (b <= 0) {
newRacine.factorEquilibre = (b > a) ? b + 1 : a + 2;
oldRacine.factorEquilibre = a - b + 1;
} else {
newRacine.factorEquilibre = (a < 0) ? b + 1 : a + b + 2;
oldRacine.factorEquilibre = a + 1;
}
return newRacine;
}
protected NoeudAVL reequilibreG(int oldfactorEquilibre) {
if ((NoeudAVL) filsG == null) {
factorEquilibre++;
} else if ((((NoeudAVL) filsG).factorEquilibre == 0)
&& (oldfactorEquilibre != 0)) {
factorEquilibre++;
}
return (factorEquilibre > 1) ? equilibrer() : this;
}
protected NoeudAVL reequilibreD(int oldfactorEquilibre) {
if ((NoeudAVL) filsD == null) {
factorEquilibre--;
} else if ((((NoeudAVL) filsD).factorEquilibre == 0)
&& (oldfactorEquilibre != 0)) {
factorEquilibre--;
}
return (factorEquilibre < -1) ? equilibrer() : this;
}
/*
* La méthode principale implante l’algorithme de rééquilibrage
*/
protected NoeudAVL equilibrer() {
if (factorEquilibre < 0) {
if (((NoeudAVL) filsG).factorEquilibre <= 0)
return rotationD();
else {
filsG = ((NoeudAVL) filsG).rotationG();
return rotationD();
}
} else {
if (((NoeudAVL) filsD).factorEquilibre >= 0)
return rotationG();
else {
filsD = ((NoeudAVL) filsD).rotationD();
return rotationG();
}
}
}
public NoeudAVL insertion(int data) {
if (data <= this.data) {
if (filsG != null) {
int oldfactorEquilibre = ((NoeudAVL) filsG).factorEquilibre;
filsG = ((NoeudAVL) filsG).insertion(data);
if ((((NoeudAVL) filsG).factorEquilibre != oldfactorEquilibre)
&& (((NoeudAVL) filsG).factorEquilibre != 0)) {
factorEquilibre--;
}
} else {
filsG = new NoeudAVL(data);
factorEquilibre--;
}
} else {
if (filsD != null) {
int oldfactorEquilibre = ((NoeudAVL) filsD).factorEquilibre;
filsD = ((NoeudAVL) filsD).insertion(data);
if ((((NoeudAVL) filsD).factorEquilibre != oldfactorEquilibre)
&& (((NoeudAVL) filsD).factorEquilibre != 0)) {
factorEquilibre++;
}
} else {
filsD = new NoeudAVL(data);
factorEquilibre++;
}
}
if ((factorEquilibre < -1) || (factorEquilibre > 1))
return equilibrer();
return this;
}
}
public ArbreAVL() {
super();
}
public ArbreAVL(int cle) {
super(cle);
}
public ArbreAVL(int cle, Noeud filsG, Noeud filsD) {
super(cle, filsG, filsD);
}
/*
* EN prenant soin de rééquilibrer l’arbre à chaque étape. On reprend
* simplement les méthodes déjà écrites pour un arbre binaire de recherche
*/
public void insertion(int data) {
if (isVide())
super.insertion(data);
else
racine = ((NoeudAVL) racine).insertion(data);
}
public void supprimer(int data) {
super.supprimer(data);
this.racine = ((NoeudAVL) racine).equilibrer();
}
}