Discussion :

[ptipoutche]

Salut,

voila en fait j'ai une liste chainée sous forme d'arbre qui me donne une fonction (ex: f= ab+ac). Et je voudrai parcourir cet arbre pour ensuite faire une comparaison avec une table de vérité pour simplifier l'expression.

On ma conseiller d'utiliser une pile mais je ne vois pas comment réaliser cela.

Pouvez-vous m'aidez svp.

Au départ de mon arbre j'ai un pointeur Ptr_tête, je pense qu'il faut l'utiliser.

[borisd]

Voici des indices (ça ressemble beaucoup à un exercice ton truc ) :
- chaque élément de ta pile correspond à un noeud dont tu es en train d'explorer les descendants
- tu stockes dans chaque élément de ta pile le prochain noeud fils à explorer (c'est-à-dire par où il faudra continuer quand on se retrouvera à ce niveau de l'arbre)
- tu peux aussi (pas obligatoirement) stocker le résultat du calcul correspondant aux descendants du noeud.

Tu peux faire la même chose de manière plus simple à programmer mais moins efficace (en temps de calcul) en utilisant la récursivité.

[ToTo13]

Bonjour,

je ne suis pas sûr que la pile soit super efficace dans ce cas présent.
Je suis plutôt d'accord pour la récursivité en gardant l'arbre, un peu comme dans un analyseur syntaxique.

[koala01]

Salut,

Déjà, faire "une liste chainée sous forme d'arbre"... ca n'a pas beaucoup de sens...

Un arbre, par définition, ca a une racine ou un tronc (un "point d'entrée" en programmation), qui contient des branches (2 ou plus) et dont chaque branche contient des feuilles (2 ou plus, dont certaines peuvent ne pas etre définies )

Autrement dit, là ou une chaine est "rectiligne", un arbre apparait sous forme de "niveaux", et les deux ont des utilisations tout à fait différentes

La structure "classique" d'une liste chainée (meme en considérant une liste doublement chainée, ce qui est le plus proche d'une possiblité de gestion en arbre) on a quelque chose ressemblant à

Code :

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

1
2
3
4
5
6
 
structure chaine
    Donnee
    Chaine Precedent
    Chaine suivant
fin structure

qui va réagir sous la forme de

Code :

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

1
2
3
4
5
6
7
 
element1
  ↑  ↓
element2
  ↑  ↓
element3
...

alors qu'un arbre (le plus facile à gérer étant un arbre binaire aura une structure ressemblant à

Code :

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

1
2
3
4
5
6
 
structure noeud
    donnee
    noeud gauche
    noeud droite
fin structure

et va réagir sous la forme de

Code :

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

1
2
3
4
5
6
 
          elem4
         /    \
    elem2     elem6
   /     \     /   \
elem1 elem3 elem5 elem7

Heuu... saisi tu la différence ???

Alors, il est, effectivement bien clair que, dans les deux cas, tu dois utiliser le pointeur *ptr_tete... vu que, de toutes manières, ce sera ton "point d'entrée"

Mais, l'utilisation et la logique seront tout à fait différentes selon le cas...

Dans les deux cas, la récurivité peut te venir en aide, mais de manière différente:

Dans le cas d'une liste chainee, tu peux créer une fonction parcoure sous la forme de

Code :

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

1
2
3
4
5
6
7
8
9
10
 
type_retour parcoure( type_de_structure * ptr)
{
    gestion des données
    si ptr->Suivant different de NULL
        variable temporaire<- parcoure(ptr->Suivant)
    fin si
    gestion variable temporaire
    renvoie quelquechose
}

dans le cas d'un arbre binaire, cela ressemblera plutot à

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
type_retour parcoure( type_de_structure * ptr)
{
    gestion des données
    si ptr->gauche different de NULL
        variable temporaire<- parcoure(ptr->gauche)
    fin si
    si ptr->droite different de NULL
       variable temporaire<- variable temporaire + parcoure(ptr->droite)
    fin si
    gestion variable temporaire
    renvoie quelque chose
}

Evidemment, à défaut d'etre plus précis, dans les termes utilisés et dans ce que tu veux précisément, il te sera difficile d'obtenir des informations beaucoup plus précises... le premier conseil que je vais te donner c'est: aide nous à t'aider

[nletteron]

J'ai trouvé peut être quelque chose qui ressemble à ce que tu cherches dans mes vieux cours mais pour des graphes. Les noeuds sont marquer d'un flag "AD" pour à développer, "M" pour marquer, "A" pour à découvrir. Mais comme il est dit précédemment, il serait intéressant de comprendre un peu plus ton problème. J'avoue ne pas comprendre le lien entre une liste chaînée et un arbre alors que je vois très bien celui entre un arbre et une pile

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
visite(G, source) { // Itératif 
Initialiser la pile;
A développer marquer tous les noeuds Nondécouvert;
marquer source Adévelopper;
pile.ajouter(source);
tant que pile.nonvide() { 
  n=pile.sommet();
  t++;
  debut(n)=t;
  traiter(n);
  si il existe noeud un successeur de n Nondécouvert alors {
    marquer noeud comme Adévelopper;
    parent(noeud)=n;
    pile.ajouter(noeud);
  } sinon {
    t++;
    marquer n exploré;
    fin(n)=t; 
    dépiler();
  }fin si;
}fin tantque;

[ptipoutche]

Escuser moi, j'avais plein de boulot et je n'est pas eut le temps de voir vos réponse.

Je vous pose l'énoncer de mon probleme afin que vous voyer ce que je doit réaliser.

1) on doit transformer une fonction booléenne acquis au clavire en un arbre binaire.

2) Transformer l'arbre binaire initial en un arbre correspondant à la même fonction mais sous forme d'une somme de produit. ( il ne sera pas possible qu'un noeud "." puisse être le père d'un noeud "+".

3) Déterminer par la méthode de Quine les implicants premiers de la fonction booléenne.

4)Eliminer les termes redondants par la méthode de Mac Cluskey et afficher le résultat de la simplification. Sachant qu'il est possible qu'il y ait plusieurs solutions, on se cantonnera à la recherche d'une seule.



Moi je m'occupe de la 3ème partie. En entrée j'ai donc un arbre binaire avec un pointeur "prt-tête". On m'avais conseillé d'utiliser une pile comme borisd la décrit.
Ensuite je ve comparer les résultats à une table de vérité.
De la j'obtient toute les combinaisons qui sont VRAI
Ensuite j'applique la méthode de Quine qui va me permettre de connaitre les implicants premier.

Donc voila ce que je doit faire, le probleme est que je comprend pas trop le principe de fonctionnrment de la pile, pouvez-vous m'expliquer le plus précis possible (si c pas trop vous demander).

Merci

[borisd]

La pile te sert ici, en quelque sorte, à implémenter le concept de récursivité de l'arbre.

En effet, on peut voir un arbre comme une racine, et ses branches, chacune de ses branches étant elle-même un arbre, potentiellement sans branche ou vide. Il en résulte que le traitement d'un arbre entier peut se faire par le traitement séparé de chacun de ses noeuds, qui sont eux aussi des arbres, et donc traitables d'une seule et unique façon.

Dans le cas particulier d'une expression booléenne, un noeud pourrait comporter un opérateur (OU par exemple) et avoir deux enfants, l'un une variable a, l'autre un opérateur ET, ayant lui-même deux enfants variables b et c. Cet arbre représenterait alors "a OU (b ET c)".

Chacun de ces noeuds peut être évalué par la procédure "évaluation" suivante :
- si le noeud est une variable, renvoyer l'évaluation de la variable
- si le noeud est un opérateur OU, renvoyer (évaluation(enfant_gauche) OU évaluation(enfant_droit))
- si le noeud est un opérateur ET, renvoyer (évaluation(enfant_gauche) ET évaluation(enfant_droit))

Ce type de procédure est par définition récursive, elle s'appelle elle-même. On peut l'implémenter telle qu'elle, cela fonctionne parfaitement si l'arbre est de taille raisonnable.

Pourquoi ne pas l'implémenter dans le cas d'un arbre plus gros ?
En gros, lors de l'exécution d'une procédure A, le compilateur fait en sorte que les variables locales soient regroupées quelque part dans la mémoire. Lorsque cette procédure va en appeler une autre (B), le programme compilé va à nouveau avoir besoin de stocker les variables locales de B. Si B appelle C, il faudra aussi de la place pour les variables de C.
Lorsque C est terminé, on retourne à B, et il faut donc récupérer les variables de B. Lorsque B est fini, on retourne à A. Notons qu'on n'a nullement besoin de passer des variables de C aux variables de A, mais qu'on a besoin de pouvoir passer des var de C à B, et de B à A, i.e. des dernières utilisées aux avant-dernières (LIFO). On a donc besoin d'une structure de pile.
Les compilateurs utilisent ces structures de façon sûre : ils stockent toutes les variables locales dans la pile.
Donc, si on utilise de grosses structures locales (et non allouées dans le tas), la taille de la pile va rapidement limiter le nombre d'appels de procédure. Par ailleurs, le temps d'allocation et d'initialisation des var locales dans la pile peut devenir conséquent.

Pour éviter ça, il suffit de gérer soi-même la pile, comme le fait le compilateur, mais en n'y mettant que ce qui nous intéresse : noeud en cours de traitement, évaluation de l'enfant gauche (par exemple infini si pas encore calculé, 0 ou 1), éval du noeud droit...

L'algo général consiste alors à ajouter un premier élément à la pile, comportant (racine,infini,infini).
On effectue ensuite une boucle tant que la pile n'est pas vide.

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
 
Si le noeud est une variable,
  Si le noeud est un enfant gauche
    père.eval_gauche <- éval
  Sinon
    père.eval_droite <- eval
  Finsi
  Dépiler
Sinon Si l'éval de l'enfant gauche est infini, 
  on empile (enfant_gauche_courant,infini,infini)
Sinon
  Si l'éval de l'enfant droit est infini
    on empile (enfant_droit_courant,infini,infini)
  Sinon
    Si le noeud est un OU
      res <- eval_gauche ou eval_droite
    Sinon...
    Fin Si
    Si le noeud est un enfant gauche
      père.eval_gauche <- res
    Sinon
      père.eval_droite <- res
    Finsi
    Dépiler
  FinSi
FinSi

Ce code n'est là que pour aider et ne gère pas tous les cas (retour du premier noeud par exemple).