Discussion :

[mroudy]

Bonjour,
Je suis actuellement sur les arbres et leurs parcours.

Alors, je ne comprends pas pourquoi mon premier parcours, que je pense juste, ne fonctionne pas dans mon main.
Ne vous formalisez pas sur la méthode Afficher, c'est celle qui m'était demandée. Elle est étrange mais retrace bien le parcours d'un arbre.
Peut-être que mon problème vient de là mais si c'est le cas celà va me laisser dubitatif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
 
class Noeud {
    int valeur;
    Noeud filsGauche, filsDroit;
 
    Noeud(int v) {
	valeur = v;
	filsGauche = filsDroit = null;
    }
 
}
 
 
class ArbreBinaire {
    Noeud racine;
 
    ArbreBinaire() {
	racine = null;
    }
 
    void Afficher() {
	AfficherNoeud(racine, 0);
    }
 
    boolean EstVide() {
	if (racine == null)
	    return true;
	else
	    return false;
    }
 
    void AfficherNoeud(Noeud n, int niveau) {
	String decalage = "";
 
	for (int i = 0; i < niveau; i++)
	    decalage += "   ";
 
	System.out.print(decalage);
 
	if (n != null) {
	    System.out.println("|->" + n.valeur);
 
	    niveau++;
 
	    AfficherNoeud(n.filsGauche, niveau);
	    AfficherNoeud(n.filsDroit, niveau);
	} else {
	    System.out.println("|->null");
	}
    }
 
    void Ajouter(int v) {
	if (racine == null)
	    racine = new Noeud(v);
	else
	    AjouterNoeud(racine, v);
    }
 
    void AjouterNoeud(Noeud r, int v) {
	if (r.valeur >= v) {
	    if (r.filsGauche == null)
		r.filsGauche = new Noeud(v);
	    else
		AjouterNoeud(r.filsGauche, v);
	} else {
	    if (r.filsDroit == null)
		r.filsDroit = new Noeud(v);
	    else
		AjouterNoeud(r.filsDroit, v);
	}
    }
 
// et voilà où je coince. Je ne poste qu'un parcours, les autre ne présentant que de très légères modifications.
 
 
    void ParcoursPrefixe() {
	System.out.print("[ ");
	ParcoursPrefixeNoeud(racine);
	System.out.print(" ]");
    }
 
    void ParcoursPrefixeNoeud(Noeud n) {
	if (n != null) {
	    System.out.print(n.valeur + " ");
	    ParcoursPrefixeNoeud(n.filsGauche);
	    ParcoursPrefixeNoeud(n.filsDroit);
	}
    }
}

Mon Main, le but est d'afficher l'arbre selon un certain ordre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
public class ArbreBinaireTest {
    public static void main(String[] args) throws IOException {
	ArbreBinaire abr = new ArbreBinaire();
 
	abr.Ajouter(6);
	abr.Ajouter(3);
	abr.Ajouter(8);
	abr.Ajouter(2);
	abr.Ajouter(5);
	abr.Ajouter(7);
	abr.Ajouter(9);
	abr.Ajouter(4);
 
	System.out.println("ABR :");
	abr.Afficher();
 
	System.out.println("Parcours préfixe : " + abr.ParcoursPrefixe());
    }
}

[joel.drigo]

Salut,

Si par "ne fonctionne pas", tu veux dire que ton programme ne compile pas (ce serait mieux que tu sois plus explicite), c'est parce que tu essayes de concaténer un retour de méthode de type void à une String :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

System.out.println("Parcours préfixe : " + abr.ParcoursPrefixe());

Le retour de la méthode ParcoursPrefixe de ArbreBinaire est du type void. Java ne sais pas concaténer une String avec rien, et donc lance une erreur à la compilation : "operator + is undefined for the argument type(s) String, void", qui explicite clairement le souci.

Solution :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
System.out.println("Parcours préfixe : ");
abr.ParcoursPrefixe();

[mroudy]

Merci Joel,
Je suis vraiment une buse, effectivement mettre ma méthode à cette place j'aurais dû m'en rendre compte tout seul tellement ça saute aux yeux.
Bon, maintenant il faut que je j'implémente le parcours en largeur avec une file de noeud et enfin que je fasse la méthode rechercher en booléen. Bref, j'ai encore du boulot jusqu'à ce soir

Pfffffffff
Je ne comprends pas comment implémenter ma file avec des noeuds, même en pseudo code je n'y arrive pas.
J'ai bien une idée, créer une nouvelle file dans ma méthode ParcoursLargeur.
En un premier temps ajouter la racine à la file.
Après faire une boucle while qui retire au fûr et à mesure les noeuds gauche puis droit de l'arbre sans oublier d'ajouter ces derniers à la file jusqu'à ce que les fils gauche et droit soient vides et les afficher au fûr et à mesure.

Je sais qu'il faut que je créer une classe file, vient-elle remplacer ma classe ArbreBinaire ?
La classe Noeud correspond elle à une classe Cellule ?

[mroudy]

Bon, je poste la solution a mes derniers problèmes si ça peut servir à quelqu'un.
Et après je posterai mes autres soucis

Ajout de la classe Cellule

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
class Cellule
{
	Noeud noeud;
	Cellule suivant;
 
 
	Cellule(Noeud n)
	{
		noeud = n;
		suivant = null;
	}	
 
}

Classe FileNoeud

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
 
public class FileNoeud
{
  Cellule Premier;
 
  FileNoeud()
  {
    Premier = null;
  }
 
  boolean EstVide()
  {
	if(Premier == null)
		return true;
	else
		return false;	
  }
 
  void Ajouter(Noeud n)
  {
 
  	if(Premier == null)
  		Premier = new Cellule(n);
  	else
  	{	
  		Cellule c = Premier;
  		while(c.suivant != null)
  		{
  			c = c.suivant;
  		}
 
  		c.suivant = new Cellule(n);	
  	}	
  }
 
  Noeud Retirer()
  {
    Noeud n = Premier.noeud; 
	  Premier = Premier.suivant;
	  return n;
  }
 
  Noeud Premier()
  {
	 return Premier.noeud;
  }
}

Codes pour les différents parcours et la recherche d'un Noeud dans un arbre.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
 
 void ParcoursPrefixe()
  {
  	System.out.print("[");
  	ParcoursPrefixeNoeud(racine);	
  	System.out.print((racine == null?"]":"\b]"));
  }
 
  void ParcoursPrefixeNoeud(Noeud n)
  {
  	if(n != null)
  	{
  		System.out.print(n.valeur + ",");
  		ParcoursPrefixeNoeud(n.filsGauche);
  		ParcoursPrefixeNoeud(n.filsDroit);
  	}
  }
 
  void ParcoursInfixe()
  {
  	System.out.print("[");
  	ParcoursInfixeNoeud(racine);
  	System.out.print((racine == null?"]":"\b]"));
  }
 
  void ParcoursInfixeNoeud(Noeud n)
  {
  	if(n != null)
  	{
  		ParcoursInfixeNoeud(n.filsGauche);
  		System.out.print(n.valeur + ",");
  		ParcoursInfixeNoeud(n.filsDroit);
  	}
  }
 
  void ParcoursSuffixe()
  {
  	System.out.print("[");
  	ParcoursSuffixeNoeud(racine);
  	System.out.print((racine == null?"]":"\b]"));
  }
 
  void ParcoursSuffixeNoeud(Noeud n)
  {
  	if(n != null)
  	{		
  		ParcoursSuffixeNoeud(n.filsGauche);
  		ParcoursSuffixeNoeud(n.filsDroit);
  		System.out.print(n.valeur + ",");
  	}
  }
 
  void ParcoursLargeur()
  {
    FileNoeud f = new FileNoeud();
 
    f.Ajouter(racine);
 
    System.out.print("[");
 
    while(!f.EstVide())
    {
      Noeud n = f.Retirer();
      System.out.print(n.valeur + ",");
      if(n.filsGauche != null)
      {
        f.Ajouter(n.filsGauche);
      }
      if(n.filsDroit != null)
      {
        f.Ajouter(n.filsDroit);
      }
    }
 
    System.out.print((racine == null?"]":"\b]")); 
 
  } 	
 
	/************************/
  /*      recherche       */
  /************************/  
 
  boolean Recherche(int v)
  {
    return (RechercheNoeud(racine, v) != null);  
  }
 
  Noeud RechercheNoeud(Noeud n, int v)
  {
 
    if(n == null)
    return null;
    if(n.valeur == v)
      return n;
    if(n.valeur > v)
      return RechercheNoeud(n.filsGauche, v);
    else
      return RechercheNoeud(n.filsDroit, v);  
 
  }

[mroudy]

Bon, maintenant j'ai d'autres soucis.

Le premier je n'arrive pas, mais alors pas du tout à le coder.
Il s'agit d'implémenter une méthode qui retourne la valeur du désiquilibre d'un noeud, j'avoue que là j'ai aucune idée de comment procèder.

Autres choses, réaliser les rotations droite et gauche.
Bon, à force de chercher j'ai trouvé un code que je n'arrive pas à modifier par rapport au code que j'ai déjà écrit.
un petit exemple, je comprends l'algorithme de rotation de l'arbre gauche mais son adaptation alors là, je coince :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
 
static Arbre rotationG(Arbre a)
{
Arbre b = a.filsD;
Arbre c = new Arbre (a.filsG,
a.contenu, b.filsG);
return new Arbre (c, b.contenu,
b.filsD);
}

J'ai essayé avec ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
    int rotationGaucheNoeud(Noeud n) {
	if (n != null) {
	    return rotationGaucheNoeud(n.filsDroit);
	}
	new Noeud(n.filsGauche, n.valeur);
	return new Noeud( n.valeur, n.filsDroit);
    }

Je sais que c'est complétement naze puisque le Noeud ne peut pas être un int ( notamment parce-que ça ne compile pas à cause de ça et cetainement d'autres soucis ). Autre chose, je sais (enfin je crois) que la hauteur ne doit pas être supèrieur à 2, sinon, rien ne sert de faie une rotation. Je crois que mon plus gros problème c'est que je ne pose jamais la racine de l'arbre, celle qui permet grace à la rotation d'équilibrer l'arbre.

idem pour ce qui est des codes de rotation gauche-droite. J'avoue que comme les premiers je n'ai pas réussi à les codés, là j'ai même pas essayé .
Dernière chose, je n'arrive pas à créer une méthode insérer qui met un entier au bon endroit dans l'arbre et qui effectue les opérations afin que l'arbre conserve son équilibre...

[mroudy]

La nuit portant consei j'ai, normalement réussi à faire mes rotations gauche et droite et gauchedroite et droitegauche. J'espère surtout que je ne marque pas d'erreurs.

Rotation gauche :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
    void rotationGauche(Noeud racine) {
	System.out.print("[ ");
	rotationGaucheNoeud(racine);
	System.out.print(" ]");
    }
 
    Noeud rotationGaucheNoeud(Noeud n) {
	Noeud n2 = n.filsGauche;
	n.filsGauche = n2.filsDroit;
	n2.filsDroit = n;
	return n2;
    }

Rotation droite, bon évidemment le code ne change que très peu.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 
    void rotationDroite(Noeud racine) {
	System.out.print("[ ");
	rotationGaucheNoeud(racine);
	System.out.print(" ]");
    }
 
    Noeud rotationDroiteNoeud(Noeud n) {
	Noeud n2 = n.filsGauche;
	n.filsGauche = n2.filsDroit;
	n2.filsDroit = n;
	return n2;
    }

Bon, la méthode déséquilibre hormis le fait que la hauteur ne doit pas être supèrieuer à deux, je suis toujours dans le flou.


Rotation gauche-droite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    Noeud rotationGaucheDroite(Noeud n) {
	Noeud n2 = n.filsGauche;
	n.filsGauche = rotationGaucheNoeud(n2);
	return rotationDroiteNoeud(n);
    }

Rotation droite-gauche, j'en ai dévellopé deux mais je ne sais pas laquelle utiliser :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
    Noeud rotationDroiteGauche(Noeud n) {
	Noeud n2 = n.filsDroit;
	n.filsDroit = rotationDroitNoeud(n2);
	return rotationGaucheNoeud(n);
    }

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
        Noeud rotationDroiteGauche2(Noeud n) {
	n.filsDroit = rotationDroiteNoeud(n.filsDroit);
	return rotationGaucheNoeud(n);
    }

[mroudy]

Bon,
Je pense finalement que mes codes sur les rotations sont faux, ou peut-ête y en a-t-il un de juste dans le tas mais moi je ne m'y fierai pas.
Comme je n'ai pas réussi à développer la méthode certainement la plus simple, retourner la valeur d'un arbre désiquilibré, je ne peux pas avancer plus en avant : réaliser une insertion et effectuer les opérations de rééquilibrage en même temps, puis un main de contrôle... et bien j'ai perdu des dizaines d'heures sur les arbres oui, vaut mieux en rigoler et rester pragmatique, je crois que je ne suis pas fait pour le java et vice versa