은 클래스를 확장하도록 캐스트 할 수 없습니다.

Question

안녕하세요. AVLTree 코드를 작성하려고합니다. BST는 4 시간 전에 작동하지만 지금은 이유를 알지 못합니다. 코드에 주석을 추가하기 만하면됩니다.

오류 :

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

} 
} 

Answer 1

생성자 ArbreAVL에서, 당신은 super()를 호출하여, Arbre 생성자를 사용하고 있습니다. 그들은 NoeudAVL으로 나중에 캐스팅 할 Noeud 개체를 생성합니다.

사실, ArbreAVL 클래스는 모든 요소가 NoeudAVL 인 것으로 가정하고 있습니다. 이는 사실이 아닙니다. 이 가정을 제거하거나 (예 : instanceof 테스트를 사용하여) 코드를 깊게 다시 작성하십시오 (예 : Generics 사용).