Sujet Précédent Sujet Suivant

Aide a la finalisation d'un projet d'implantation d'arbre avl avec des erreurs

leray24na Messages postés 4 Date d'inscription lundi 23 janvier 2006 Statut Membre Dernière intervention 27 janvier 2006 - 26 janv. 2006 à 23:13
super_toinou Messages postés 764 Date d'inscription mardi 25 mai 2004 Statut Membre Dernière intervention 8 mars 2011 - 27 janv. 2006 à 13:46
Bonjour a tous,

Je dois réaliser une implémentation générique des arbres AVL comportant au minimum les fonctions d'insertion, de suppression et de recherche d'une valeur.

Mon projet est a rendre pour samedi 28.01.06 (8h), merci de votre aide.

Voici mon projet :


//---TreeAVL3.java





interface BinTree<T>


{


boolean estVide();


T racine();


BinTree<T> sag ();


BinTree<T> sad ();


int hauteur();


int taille();


String toString();


int pentearb();




}






class Feuille<T> implements BinTree<T>


{


public boolean estVide() {return true;}


public T racine() {throw new IllegalArgumentException("c'est une feuille"); }


public BinTree<T> sag () {throw new IllegalArgumentException("c'est une feuille"); }


public BinTree<T> sad () {throw new IllegalArgumentException("c'est une feuille"); }


public int hauteur() {return 0;}


public int taille() {return 0;}


public String toString() {return "<>";}


public int pentearb() {return 0;}


}






class Noeud<T> implements BinTree<T>


{


protected T root;


protected BinTree<T> left;


protected BinTree<T> right;


protected int equilibre;


public Noeud()


{


left=null;


right=null;


equilibre=0;


}


public Noeud(T r, BinTree<T> g, BinTree<T> d)


{


root = r;


left = g;


right = d;


equilibre=0;


}




public boolean estVide() {return false;}


public T racine() {return root;}


public BinTree<T> sag() {return left;}


public BinTree<T> sad() {return right;}




public int hauteur()


{


int g = left.hauteur();


int d = right.hauteur();


int res = (g > d ? g : d);


return 1 + res;


}




public int taille()


{


return 1 + left.taille() + right.taille();


}




public String toString()


{


return "<" + root +"," + left.toString() + "," + right.toString() + ">";


}


public int pentearb()


{


int sag = left.hauteur();


int sad = right.hauteur();


int res = (sag-sad);


return res;


}


}


interface TreeAVL<T extends Comparable<T>> extends BinTree<T>


{


TreeAVL<T> ins(T e);


TreeAVL<T> suppr(T e);


T maxiarb();


T miniarb();


boolean equilibreR();


boolean equilibreL();


}


class TreeAVLFeuille<T extends Comparable<T>> extends Feuille<T> implements TreeAVL<T>


{


public TreeAVL<T> ins(T e)


{


return new TreeAVLNoeud<T>(e, this, this);


}


public TreeAVL<T> suppr(T e)


{throw new IllegalArgumentException("Une feuille est toujours vide !"); }





public T maxiarb()


{throw new IllegalArgumentException("Une feuille n'a pas de maximum !"); }


public T miniarb()


{throw new IllegalArgumentException("Une feuille n'a pas de minimum !"); }


public T miniter()


{throw new IllegalArgumentException("Une feuille n'a pas de minimum !"); }


public boolean equilibreR() {return true;}


public boolean equilibreL() {return true;}




}


class TreeAVLNoeud<T extends Comparable<T>> extends Noeud<T> implements TreeAVL<T>


{


public TreeAVLNoeud(T r, TreeAVL<T> g, TreeAVL<T> d )


{


super(r, g, d);


}




public TreeAVL<T> ins(T e)


{


T rac = this.racine();


TreeAVL<T> l = (TreeAVL<T>) this.sag();


TreeAVL<T> r = (TreeAVL<T>) this.sad();


if (e.compareTo(rac) < 0) {return new TreeAVLNoeud<T>(rac,l.ins(e),r);}


if (e.compareTo(rac) > 0) {return new TreeAVLNoeud<T>(rac,l,r.ins(e));}


else {return this;}


}




public T maxiarb()


{


T rac = this.racine();


TreeAVL<T> d = (TreeAVL<T>) this.sad();


if (d.estVide()) return rac;


else return d.maxiarb();


}




public T miniarb()


{


T rac = this.racine();


TreeAVL<T> g = (TreeAVL<T>) this.sag();


if (g.estVide()) return rac;


else return g.miniarb();


}




public TreeAVL<T> suppr(T e)


{


T r = this.racine();


TreeAVL<T> sg = (TreeAVL<T>) this.sag();


TreeAVL<T> sd = (TreeAVL<T>) this.sad();


if ((e.compareTo(r)!=0) && sg.estVide() && sd.estVide()) {return this;}


else if (e.compareTo(r) == 0 && sg.estVide()) { return sd;}


else if (e.compareTo(r) == 0 && sd.estVide()) { return sg;}


else


{


if (e.compareTo(r) < 0) return new TreeAVLNoeud<T>(r,sg.suppr(e),sd);


else if (e.compareTo(r) > 0) return new TreeAVLNoeud<T>(r,sg,sd.suppr(e));


else


{


T valgmax = sg.maxiarb();


return new TreeAVLNoeud<T>(valgmax,sg.suppr(valgmax),sd);


}


}


}




public boolean equilibreR (TreeAVLNoeud<T> a, TreeAVLNoeud<T>b, boolean g)


{


TreeAVLNoeud a1, a2;


switch(a.equilibre)


{


case -1 : a.equilibre = 0; return false;


case0 : a.equilibre = 1; return true;


case1 :


default : a1 = a.right;


if(a1.equilibre == 1)


{


a.right =a1.left;


a1.left = a;


a.equilibre = 0;


a = a1;


}


else


{


a2 = a1.left;


a1.left = a2.right;


a2.right = a1;


a.right = a2.left;


a2.left = a;


if(a2.equilibre == 1)


a.equilibre = -1;


else a.equilibre = 0;


if(a2.equilibre == -1)


a1.equilibre = 1;


else a1.equilibre = 0;


a = a2;


}


if(b==null)


root = a;


else if(g)


b.left = a;


else b.right = a;


a.equilibre = 0;


return false;


}


}




public boolean equilibreL (TreeAVLNoeud<T> a, TreeAVLNoeud<T>b, boolean g)


{


TreeAVLNoeud a1, a2;


switch(a.equilibre)


{


case1 : a.equilibre = 0; return false;


case0 : a.equilibre = -1; return true;


case -1 :


default : a1 = a.left;


if(a1.equilibre == -1)


{


a.left =a1.right;


a1.right = a;


a.equilibre = 0;


a = a1;


}


else


{


a2 = a1.right;


a1.right = a2.left;


a2.left = a1;


a.left = a2.right;


a2.right = a;


if(a2.equilibre == -1)


a.equilibre = 1;


else a.equilibre = 0;


if(a2.equilibre == 1)


a1.equilibre = -1;


else a1.equilibre = 0;


a = a2;


}


if(b==null)


root = a;


else if(g)


b.left = a;


else b.right = a;


a.equilibre = 0;


return false;


}


}




}






public class TreeAVL3<T>


{


public static void main(String[] args)


{


TreeAVL avl = new TreeAVLFeuille();


int[] val1 = {1,6,7,2,4,3,5};


for (Integer i : val1)


{


avl = avl.ins(i);


System.out.println("" + avl.toString());


System.out.println("insertion de " + i + " =>" + "pente: " + avl.pentearb());




}


for (Integer i : val1)


{


avl = avl.suppr(i);


System.out.println("" + avl.toString());


System.out.println("suppression de " + i + " => " + "pente: " + avl.pentearb());


}


}


}



Voici les erreurs qui me sont retounées :

--------------------Configuration: JDK version 1.5.0_04 <Default>--------------------
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:118: TreeAVLNoeud is not abstract and does not override abstract method equilibreL() in TreeAVL
class TreeAVLNoeud<T extends Comparable<T>> extends Noeud<T> implements TreeAVL<T>
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:179: incompatible types
found : BinTree<T>
required: TreeAVLNoeud
default : a1 = a.right;
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:189: incompatible types
found : BinTree
required: TreeAVLNoeud
a2 = a1.left;
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:203: incompatible types
found : TreeAVLNoeud<T>
required: T
root = a;
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:220: incompatible types
found : BinTree<T>
required: TreeAVLNoeud
default : a1 = a.left;
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:230: incompatible types
found : BinTree
required: TreeAVLNoeud
a2 = a1.right;
^
D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java:244: incompatible types
found : TreeAVLNoeud<T>
required: T
root = a;
^
Note: D:\cnam cours 2005-2006\Structures de données\Mes projets\Mon projet\TreeAVL3.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
7 errors


Process completed.

1 réponse

Réponse 1 / 1
super_toinou Messages postés 764 Date d'inscription mardi 25 mai 2004 Statut Membre Dernière intervention 8 mars 2011 6
27 janv. 2006 à 13:46
euh ton truc c un peu gros maais d apres les erreurs
-TreeAVL3.java:118: TreeAVLNoeud is not abstract and does not override abstract method equilibreL() in TreeAVL
class TreeAVLNoeud<T extends Comparable<T>> extends Noeud<T> implements TreeAVL<T>
dans TreeAVL t a une méthode qui s appelle equilibreL vu que TreeAVLNoeud implémente TreeAVL faut que t implémente dans TreeAVLNoeud la fonction equilibreL
- pour le reste c est que t affecte a une variable une autre variable d un autre type et donc ca te pete au nez, j connais pas trop les template de java 1.5 mais force le cast si c juste qu une question de type générique

++ Toinou
0

Discussions similaires

langage C : fonction calcul hauteur maximale arbre
lordvan -
lordvan -

4 réponses
implementation d'arbre avl
leray24na -
platon179 -

1 réponse
Formulaire de création d'un arbre généalogique
EmmaBlack -
kohntark -

17 réponses
dessin d'arbre binaire avec sdl
lealynn18 -
intissar242 -

2 réponses
Tournoi avec arbre
masseur -
masseur -

2 réponses
Rejoignez-nous