Bonjour,
je souhaite ecrire une fonction itérative pour ajouter une clé dans un arbre binaire de recherche ( Soit A un noeud , tout noeud du ss arbre gauche de A a une clé < a cle(A) et > a cle(A) pour tout noeud du ss arbre droit de A).
La fonction récursive marche bien mais je ne vois pas ou est le pb dans la version itérative :
public class Abr {
int cle;
Abr left,right;
public Abr(int x){
this.cle=x;
}
/* methode recursive */
public Abr ajouter(Abr a, int x){
if(a==null) {
return new Abr(x);
}
else if(x<=a.cle){
a.left=ajouter(a.left,x);
}
else a.right=ajouter(a.right, x);
return a;
}
/* methode iterative */
public void ajouter(int x){
Abr tmp=this;
while(tmp!=null){
if(x<=tmp.cle)
tmp=tmp.left;
else
tmp=tmp.right;
}
// ici tmp est encore bien rattaché a la racine
tmp=new Abr(x);
// maintenant il ne l'est plus donc je perd le nouveau noeud créer
// observé avec le debuggage
}
/* methode d'affichage */
public void affiche(Abr a){
if(a!=null){
affiche(a.left);
System.out.print(a.cle " ");
affiche(a.right);
}
System.out.println();
}
public static void main(String[] args) {
Abr a=new Abr(10);
a.ajouter(20);
a.affiche(a);
}
}
Cela m’affiche … 10 !
Voila donc en gros pourquoi tmp perd la reference qui le rattache a l’arbre ?
J’espere avoir été clair et merci a l’avance de vos éclaircissements =) !
Ciao
Heu…
tmp=new Abr(x); <-- tu crée une nouvelle instance… donc sauf si tu en fais quelque chose, il ne se passe rien de plus…
en gros, je dirais qu’il te manque la fin de l’algo :
Abr tmp = this;
Abr previous = null;
while(tmp!=null) {
previous = tmp;
tmp=x<=tmp.cle ? tmp.left: tmp.right;
}
if (previous == null) {
throw new IllegalStateException("pas censé arrivé");
}
Abr xabr = new Abr(x);
if (x <= previous.cle) previous.left = xabr;
else previous.right = xabr;
En effet ta solution marche !
Mais je ne comprend pas :
a la sortie de la boucle while , tmp et ( previous.left ou previous.right ) ont la meme adresse !
dans cet exemple : System.out.println(tmp==previous.right) renvoi true .
et si je fait simplement a la sortie de boucle :
Abr xabr=new Abr(x);
tmp=xabr;
Là non-plus ca ne marche pas…! Quelle est la différence avec le fait de passer par un Abr auxiliaire (ici previous) ?
Merci en tout cas pour ta reponse :super:
Si je ne veut pas de previous je peut faire :
Abr tmp = this;
Abr previous = null;
while(tmp.left!=null || tmp.right!=null) {
tmp=x<=tmp.cle ? tmp.left: tmp.right;
}
if (x <= tmp.cle) tmp.left = new Abr(x);
else tmp.right = new Abr(x);
Ca marche, c la meme chose …
Mais je ne vois toujours pas en quoi
(ancienne version) : tmp=new Abr(x); et (cette version) tmp.right=new Abr(x); peuvent différer puisque les adresses auxquelles ils font référence sont les memes…
Le previous c’était juste pour garder ce qu’il y avait avant le changement de tmp.
En Java, ce n’est pas possible. D’où ton problème. ie: tmp = new Abr(x) ne fait que crée un objet dans une variable locale (= temporaire), que tu ne réutilise pas par la suite.
En C, ça pourrait fonctionner ceci dit.
Aaah très bien. Merci pour cette explication. Dans ma tête trottait justement une espèce d’équivalence entre pointeurs© et références(JAVA)…qui s’avère donc être fausse ! Merci ! :hello: