Discussion :

[loic911]

Bonjour,
Je dois réaliser un petit arbre binaire avec certaines données. Pour faire simple, je dois pouvoir ajouter des éléments les un a la suite de l’autre.
Les éléments ne doivent pas être ajoutés en fonction de leur valeur mais en fonction du nombre d’élément qu’ils peuvent avoir. Il faut ajouter les éléments tant que possible vers la gauche. Je m’explique
Exemple :

• Deux peut posséder 2 fils,
• Un peut posséder 1 fils,
• Zero ne peut pas posséder de fils

A chaque étape, j’ajoute un élément de la liste DEUX DEUX UN ZERO ZERO ZERO.
(regarder le shéma en pièce jointe)

1. J'ajoute l'élément "DEUX" -> racine
2. J'ajoute l'élément "DEUX". -> racine peut contenir encore 2 éléments, on l'ajoute a gauche
3. J'ajoute l'élément "UN". -> racine peut contenir encore 1 éléments, mais on essaye de l'ajouter à gauche. Racine a déjà un fils, donc on l'ajoute au fils de la racine (qui peut encore contenir 2 éléments)
4. J'ajoute l'élément "ZERO" -> racine a déjà un fils a gauche, son fils de gauche aussi, le fils de gauche de son fils de gauche aussi. Le dernier élément peut contenir 1 fils et n'a pas encore de fils, on l'ajoute à gauche.
5. J'ajoute l'élément "ZERO" -> on essaye de l'ajouter vers la gauche, mais ca coince au niveau de l'élément "ZERO" qui ne peut pas contenir de fils, l'élément "UN" qui ne peut plus en contenir. On l'ajoute comme fils de droite de l'élément "DEUX" qui peut encore contenir un élément.
6. J'ajoute l'élément "ZERO" -> le fils de gauche de racine est plein, donc on l'ajoute a droite.

Remarque:
-On essaye de toujours aller le plus vers la gauche
-Si un élément ne peut plus contenir d'élément, ses fils ne pourront pas non plus

J'ai essayé de réaliser l'algo pour l'ajout dans l'arbre. Mais après une demi-dizaine d'heure, j'ai du jeter l'éponge et poster mon problème ici (pour mieux la ramasser ).

Bref, la récursion ca passe pas
Voilà le dernier bout de code que j'ai gardé.
getGauche et getDroite: renvoit les noeuds de gauche ou droite
resteLibre() test si il reste encore des places libre pour avoir un fils (un élément "DEUX" qui a un fils, a 1 place libre...).

Ca a l'air de bien se passer jusqu'au moment ou un élément n'arrive plus à s'insérer vers la gauche (la 5ème case sur l'image)

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
 
    public void ajoute(Noeud r ,Fonction f) {
 
        if(racine==null) {
            //l'arbre est vide, on ajoute le premier élément comme racine
            racine = new Noeud(f,null,null);
        } else {
            if(r.resteLibre()) {
                if(r.getGauche()==null) 
                {
                    r.ajouterNoeudGauche(new Noeud(f,null,null));
                } 
                else if(r.getGauche()!=null)
                {
                    if(r.getGauche().resteLibre()) ajoute(r.getGauche(),f);
                }
                else if(r.getDroit()==null) 
                {
                    r.ajouterNoeudDroite(new Noeud(f,null,null));
                }
                else if(r.getDroit()!=null)
                {
                    if(r.getDroit().resteLibre()) ajoute(r.getDroit(),f);
                }
            }
 
        }
 
    }

J'ai un peu regarder l'ajout récursif dans un arbre binaire mais j'ai pas trouvé grand chose...
Quelqu'un pourrait il me sortir de la?