Arbre binaire: Ajout précis avec récursion

Version imprimable

1 pièce(s) jointe(s)

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)

J'ajoute l'élément "DEUX" -> racine
J'ajoute l'élément "DEUX". -> racine peut contenir encore 2 éléments, on l'ajoute a gauche
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)
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.
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.
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 :mrgreen:).

Bref, la récursion ca passe pas :evilred:
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:

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...:aie:
Quelqu'un pourrait il me sortir de la? :lol:

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

Moi je ferai plutôt comme cela:

Code:

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:

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:

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));

20/03/2008, 17h27
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ï
20/03/2008, 17h52
loic911

Citation:

Envoyé par pseudocode

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

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

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

Merci encore :king:

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.
20/03/2008, 18h11
pseudocode

Citation:

Envoyé par loic911

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

C'est Jedai qui va être content.

Citation:

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.

:sm:

Mais comme c'est juste un parcours en profondeur préfix, c'etait aussi simple d'écrire l'implémentation que le pseudocode. :P
20/03/2008, 18h16
Jedai

Citation:

Envoyé par loic911

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

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ï
20/03/2008, 18h31
pseudocode

Citation:

Envoyé par Jedai

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 ? :mouarf:

Citation:

Envoyé par Jedai

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 :lol:. C'est clair qu'une fois qu'on maitrise bien la récursion, on peut faire des merveilles :king:

Je rebloque sur un autre problème :aie:

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

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...:?

:yaisse2: :aie: Au passage...vive le Scheme: :aie: :yaisse2:

Citation:

Envoyé par loic911

:yaisse2: :aie: Au passage...vive le Scheme: :aie: :yaisse2:

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:

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:

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

--
Jedaï

21/03/2008, 21h11
loic911
(non mais c'était ironique aussi :aie: [se fait lyncher par Jedai])

En fait, j'essaie de simplifier un expression booléenne spécifique.
Si mon arbre contient par exemple un noeud OR avec un fils TRUE, on peut simplifier le noeud OR par le noeud TRUE.
Un NOT avec un fils TRUE, deviendra False.

Tout marchait bien si je faisais dans ma fonction de simplification:
Code:

1 2 3 4 5 6 7 8 F (Noeud) SI Noeud = "NOT" AND SI Noeud.filsgauche = "TRUE" ALORS Noeud.resetToFalse() F (Noeud.filsgauche) F (Noeud.filsdroit) FIN SI
Mais j'ai décider de changer la façon de gérer les différents éléments en les traitants plus sous forme d'objet que sous forme de chaine de caractère.

Dés lors, au lieu de changer le nom de la "fonction" avec un bête "resettofalse" (qui faisait bêtement "nom=false"), il faudrait que le noeud change d'objet et qu'il passe d'un NOT à un VAR (dont fait partie true).
En sachant que la variable Noeud est du type "interface" qui est implémenté par NOT et VAR.
Code:

1 2 3 4 5 6 7 8 F (Noeud) SI Noeud instanceof NOT AND SI Noeud.filsgauche = "TRUE" ALORS Noeud = new VAR("TRUE") F (Noeud.filsgauche) F (Noeud.filsdroit) FIN SI
Le problème étant qu'en changeant l'objet, je fous tout en l'air :oops:

J'ai déjà en théorie implémenté toutes la logiques de la simplifcation booléenne (merci pour l'algo au passage. Je vérifierais si je traite bien tout), seulement je cale sur le changement du type d'objet d'un noeud dans une fonction récursive :aie:
21/03/2008, 21h52
Jedai

Citation:

Envoyé par loic911

(non mais c'était ironique aussi :aie: [se fait lyncher par Jedai])

Ben c'est doublement ironique alors, vu que mon code fait l'affaire en une grosse trentaine de ligne. Les langages fonctionnels sont vraiment bien adaptés pour faire du calcul symbolique ou ce genre de chose.

--
Jedaï

Citation:

Envoyé par loic911

Le problème étant qu'en changeant l'objet, je fous tout en l'air :oops:

Inspire toi de la méthode dans mon code, au lieu de modifier le noeud en place, renvoie le noeud modifié et récursivement branche les simplifications des fils au nouveau noeud simplifié, autrement dit :
Code:

1 2 3 4 5 6 7 8 9 10 simplification (Noeud n) { filsSimplifié = map simplification n.fils; // simplification éventuelle du nouveau noeud // exemple pour n = Not(...) : // Si filsSimplifié = [Constante booléenne(b)] // nouveauNoeud = Constante booléenne (not b) // Sinon // nouveauNoeud = Not (filsSimplifié) renvoie nouveauNoeud; }
--
Jedaï

J'essaye de l'adapter au code Java.
L'arbre à juste "NOT" et son fils à gauche "TRUE".
Il parcourt les éléments et renvoit un null a la fonction appelante :bug:

C'est au contrôle de "if(filsSimplifie!=null)" qu'il refuse de rentrer.:bug:

T'aurais pas une version un peu plus détaillé de ton raisonnement? Parce que la je cale vraiment :aie:

Code:

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
 
private interface simplification(interface n) {
        interface filsSimplifie=null;
        interface nouveauNoeud=null;
 
        if(n.Gauche()!=null) {
            filsSimplifie = simplification(n.Gauche());
            nouveauNoeud = filsSimplifie;
            if(filsSimplifie!=null) {
                if(filsSimplifie instanceof NOT) {
                    NOT not = (NOT) filsSimplifie;
                    if(not.simplifiable()) {
                        nouveauNoeud = new VAR("false");
                    }
                }
            }
        }
        if(n.Droite()!=null) {
            filsSimplifie = simplification(n.Droite());
            nouveauNoeud = filsSimplifie;
            if(filsSimplifie!=null) {
                if(filsSimplifie instanceof NOT) {
                    NOT not = (NOT) filsSimplifie;
                    if(not.simplifiable()) {
                        nouveauNoeud = new VAR("false");
                    }
                }
            }
        }
        return nouveauNoeud;
    }

22/03/2008, 00h32
Jedai
Citation:
Envoyé par loic911

Code:

1 2 nouveauNoeud = filsSimplifie;
Ca sort d'où ça ?

Par ailleurs ton code me frappe comme très mal conçu dans l'optique objet... Une classe de noeud doit savoir comment se simplifier, simplification() doit faire partie des méthodes de la classe, le "instanceOf NOT" est très inquiétant (sans parler du fait qu'il devrait concerner n, pas filsSimplifie).

Tu pourrais nous expliquer un peu comment tu as arrangé ta hiérarchie de classe ? Déjà que je ne considère pas que les LOO soit particulièrement adaptés à la manipulation d'arbre, alors si en plus ta conception objet n'est pas propre...

--
Jedaï
22/03/2008, 10h40
loic911

EDIT: c'est en voie d'être résolu en modifiant la structure des classes de manière plus cohérente :lol:
Un grand merci à jedai et pseudocode :king:

Classe abstraite Noeud
Sous classe: AND,OR,NOT,VAR qui implémente toute "intarface".

Je pensais faire une méthode de simplification dans la classe abstraite noeud ou dans chaque sous classe.
Mais je bloque sur le "remplacement" des noeuds.
Par exemple dans le noeud "NOT", je regarde si il a un fils à "VAR" (true ou false).
Si oui, je dois simplifier le noeud "NOT" à "VAR"
Donc l'objet doit "s'autochanger" en passant du type NOT au type VAR

Je pense que c'est pas possible (?).
Donc j'ai délégué la tâche à une autre classe qui aurait une méthode qui pourrait simplifier le noeud.

Le if x instanceof NOT a juste comme but de regarder si c'est un NOT, si c'est un NOT on peut effectuer le casting et appeler les méthodes pour voir si il est sumplifiable (un des fils est TRUE ou FALSE).

C'est plus clair?

Désolé mais je suis pas encore un pro de l'OO :king: