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