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?

[pseudocode]

Ça me parait bien compliqué comme fonction récursive...

Moi je ferai plutôt comme cela:

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
boolean add(Node parent, Node newnode) {
	for(int i=0;i<parent.children.length;i++) {
		// noeud fils libre -> on ajoute -> succès
		if (parent.children[i]==null) {
			parent.children[i]=newnode;
			return true;
		}
		// noeud fils occupé -> on tente d'ajouter sous le fils
		if (add(parent.children[i],newnode)) return true;
	}
 
	// aucun fils libre -> echec
	return false;
}

en utilisant ce type de structure:

Code java :

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

1
2
3
4
5
6
7
8
9
class Node {
	Node[] children;
	String name;
 
	Node(String name, int maxchildren) {
		this.name=name;
		this.children = new Node[maxchildren];
	}
}

Ensuite, il ne reste qu'a créer le noeud "racine" et y ajouter les autres noeuds:

Code java :

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

1
2
3
4
5
6
7
8
Node root = new Node("root",2);
 
add(root,new Node("DEUX (a)",2));
add(root,new Node("DEUX (b)",2));
add(root,new Node("UN",1));
add(root,new Node("ZERO (a)",0));
add(root,new Node("ZERO (b)",0));
add(root,new Node("ZERO (c)",0));

[loic911]

Ça me parait bien compliqué comme fonction récursive...

Une fonction récursive compliqué...C'est pas un pléonasme ca?

Merci pour tout, ça fonctionne impec!
Je m'attendais pas à une solution "clé en main".

Merci encore

edit: pour Jedai, oui mon code était assez obscure, j'ai passé trop de temps dessus a modifié plein de truc...bref a la fin ca ressemblait pas a grand chose.

[pseudocode]

Une fonction récursive compliqué...C'est pas un pléonasme ca?

C'est Jedai qui va être content.

Merci pour tout, ça fonctionne impec!
Je m'attendais pas à une solution "clé en main".

Oui, c'est vrai: je n'aurais pas du donner de solution clé en main.



Mais comme c'est juste un parcours en profondeur préfix, c'etait aussi simple d'écrire l'implémentation que le pseudocode.

[Jedai]

Une fonction récursive compliqué...C'est pas un pléonasme ca?

La plupart des fonctions récursives sont simples, il y a toute une catégorie de problèmes pour lesquels écrire une solution itérative est bien plus complexe que d'écrire une solution récursive. La fonction que t'a fourni Pseudocode est récursive et simple.

Que la récursivité soit complexe est une fausse idée propagée par les utilisateurs de langages qui y sont peu adaptés.

--
Jedaï

[pseudocode]

Que la récursivité soit complexe est une fausse idée propagée par les utilisateurs de langages qui y sont peu adaptés.

C'est les utilisateurs qui sont peu adaptés ?

[loic911]

Que la récursivité soit complexe est une fausse idée propagée par les utilisateurs de langages qui y sont peu adaptés.

Oui, je disais ca pour rire . C'est clair qu'une fois qu'on maitrise bien la récursion, on peut faire des merveilles

Je rebloque sur un autre problème

NOT et VAR implémente l'interface "interface" (j'ai simplifié...)

Code :

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

1
2
3
4
5
6
7
8
9
10
 
    private void simplification(interface root) {
        if(root instanceof NOT) {
            if(root.simplifiable()) {
                root = new VAR("false");
            }
        }
        if (root.childrenGauche()!=null)  simplification(root.childrenGauche());
        if (root.childrenDroite()!=null)  simplification(root.childrenDroite());
    }

Bon, en gros si mon noeud est une instance de la classe NOT et qu'il est simplifiable (son fils vaut "true"), alors on remplace le noeud NOT par un nouveau noeud False (qui n'a pas de fils...).
NOT---TRUE
devient
FALSE

Les problèmes sont (je suppose ):
-je modifie localement la valeur de root...donc ca n'a pas d'effet...
-si un noeud NOT est simplifiable, je continue la récursion sur base du nouveau noeud "FALSE" modifié qui devient root (et qui n'a pas de fils...)

Mais j'arrive pas a voir comment je pourrais faire pour modifier la valeur au niveau "global" sans que le noeud ajouté ne remplace l'arbre complet a parcourir...

Au passage...vive le Scheme:

[Jedai]

Au passage...vive le Scheme:

Comme tu dis, pour ce genre de problème, un langage fonctionnel est nettement plus adapté...

Par exemple je pense que tu essaies de faire ça ?

Code Haskell :

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
import Data.Maybe
 
data BExpr = C Bool | V String 
           | Not BExpr | And BExpr BExpr | Or BExpr BExpr
             deriving (Show, Eq, Ord)
 
type Env = [(String,BExpr)]
 
simpl :: BExpr -> Env -> BExpr
simpl (C b) e = C b
simpl (V s) e = fromMaybe (V s) (lookup s e)
simpl (Not expr) e = 
    let res = simpl expr e in
    case res of
      (C b) -> C (not b)
      _ -> Not res
simpl (And expr1 expr2) e =
    let res1 = simpl expr1 e
        res2 = simpl expr2 e
    in case (res1, res2) of
         (C False,_) -> C False
         (_,C False) -> C False
         (C True,_) -> res2
         (_,C True) -> res1
         _ -> And res1 res2
simpl (Or expr1 expr2) e =
    let res1 = simpl expr1 e
        res2 = simpl expr2 e
    in case (res1, res2) of
         (C True,_) -> C True
         (_,C True) -> C True
         (C False,_) -> res2
         (_,C False) -> res1
         _ -> Or res1 res2

Code :

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

1
2
> simpl (Or (Not(And (C True) (V "x"))) (V "y")) [("x", C True)]
V "y"

--
Jedaï

[Jedai]

Je comprend pas grand chose à ton code... D'abord qu'est ce que sont les entrées de ta fonction exactement ? D'où sort la variable "racine" (ajoute n'étant apparemment pas une méthode, ça ne peut pas être une variable d'instance) ? Est-ce que resteLibre() est récursif ou non (j'ai l'impression que c'est là qu'est le problème d'après ce que tu décris) ?

--
Jedaï