Bonjour a tous,
Mon projet consiste a implementer un arbre avl comportant au minimum les fonctions d'insertion, de suppression et de recherche d'une valeur.
Apres compilation, j'ai des messages d'erreurs.
Besoin d'aide, mon projet dois etre rendu ce soir avant 24h, par mail, veille de mon examen.
Voici mon projet avec ses erreurs:
//---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());
}
}
}
Merci a tous.
Afficher la suite
