Trier un arbre

[Rockleader]

Bonjour,bonsoir à tous

je n'arrive pas à faire ce que l'on me demande pour le coup je pense que c'est surtout un soucis conceptuel et algorithmique plus que de codage =)


Il s'agit de trier un arbre

Donc la structure d'un tel arbre serait ceci

Code: Tout sélectionner

typedef struct unfeuille {
   int val;
   struct unfeuille *gauche;
   struct unfeuille *droite;
}feuille;
typedef struct unfeuille * GRD;

Alors avant de me faire taper sur les doigts; oui j'ai bien retenu que c'est moche de cacher un pointeur avec typedef; mais c'est comme ça pour le cours donc ... cela dit, j'ai bien retenu c'est mal et il est mieux de passer des doubles pointeurs.

Bref là n'est pas la question.

Afin de trier un tel arbre, j'ai dans un premier temps effectué une fonction qui réalise le travail de façon récursive.

Code: Tout sélectionner

void triGRD(GRD a)
{
   if(!estVideGRD(a))
   {
      triGRD(a->gauche);
      printf("%d\n",a->val);
      triGRD(a->droite);
   }
}

Il serait plus judicieux de dire qu'elle affiche un arbre trié, l'arbre en lui même ne change pas.



Maintenant je dois effectuer le même travail, mais sans récursivité. Pour cela on m'a dit en cours que je devrais utiliser une structure de pile sur les noeuds de l'arbre; j'ai testé plusieurs choses mais je ne crois pas que ce soit bon; d'ailleurs à l'exécution je vois bien les erreurs de segmentation et je pense que ça vient plutot de la structure avant de venir de l'algorithme


Qu'en pensez vous ?

Code: Tout sélectionner

typedef struct elpile {
  feuille f;
  struct elpile * suivant; //pointeur sur la feuille suivante
 }celpile;

typedef struct elpile * pile;

Code: Tout sélectionner

void triIteratifGRD(GRD a)
{
   pile p=INIT_PILE();
   celpile n,nd,ng;
   if(!estVideGRD(a))
   {
      EMPILER(&p,a->val);
   }
   while(!PILE_VIDE(p))
   {
      n.f.val=TOP(p);
      p=DEPILER(p);
      if((n.f.gauche==NULL) && (n.f.droite==NULL))
      {
         printf("%d\n",n.f.val);
      }
      else
      {
         if(n.f.droite !=NULL)
         {
            nd.f.val=n.f.droite->val;
            ng.f.val=n.f.gauche->val;
            printf("OK\n");
            EMPILER(&p,nd.f.val);
            n.f.gauche=NULL;
            n.f.droite=NULL;
            EMPILER(&p,n.f.val);
            if(ng.f.gauche != NULL)
            {
               EMPILER(&p,ng.f.val);
            }
         }
      }
   }
}

Merci pour votre aide !

[fatal_error]

hello,

dans ton algorithme tu oublies un truc important c'est que dans ta version récursive, tu as
appelFilsGauche
printf
appelFilsDroit

sauf que dans ta version itérative tu as
printf
appelFilsGauche
appelFilsDroit

c'est évidemment pas pareil

pour remédier à ca, tu devrais considérer une pile et pusher des fonctions en tete de liste
grossièrement

Code: Tout sélectionner

while()...
 empiler(explorer(n->gauche))
 empiler(afficher(n->value))
 empiler(explorer(n->droit))


Un peu plus détaillé :

Code: Tout sélectionner

enum Order = {EXPLORE_NODE, AFFICHER_VALUE}
struct cell{
 noeud* n;
 Order order;
}
while()
  cell = depiler(pile)
  if(cell.order == EXPLORE_NODE){
    if(n->gauche){
      EMPILER(&p, cell(n->gauche, EXPLORE_NODE))
    }
    EMPILER(&p, cell(n, AFFICHER_VALUE))
    if(n->droit){
      EMPILER(&p, (n->droit, EXPLORE_NODE))
    }
  }else{
    printf("value %d", n->val)
  }
}


edit : dans les trois empiler ci-dessus, petit correctum
on s'attend à avoir dans liste:
tete :
cell(n->gauche, EXPLORE_NODE)
cell(n, AFFICHER_VALUE)
cell(n->droit, EXPLORE_NODE)
queue

[joel76]

Si on regarde bien la structure d'un arbre, on voit qu'on n'écrit la valeur d'un noeud qu'une fois que le sous-arbre gauche ait été complètement exploré, donc quand on a visité la partie la plus à droite du sous arbre gauche, qui est NULL.
On n'ecrit la valeur d'un noeud qu'après avoir rencontré NULL juste avant.
Ce qui fait que le programme peut s'ecrire

Code: Tout sélectionner

empiler arbre
tant que pile non vide faire
    feuille val
        fin si
   sinon
       empiler feuille->droite
       empiler feuille
       emplier feuille->gauche
   fin si
fin tant que


[fatal_error]

je pense pas que ton algo marche...

considérons l'arbre

Code: Tout sélectionner

     A
  B     E
C   D F   G <---C,D,F,G sont NULL


Soit L la pile, tete à gauche
L=[A]
on depile A: L=[]
A non feuille, L=[EAB]
on depile E: L=[AB]
E non feuille,L=[GEF AB]
on dépile G: L=[EFAB]
G NULL, L non vide, on dépile E: L=[FAB] on affiche E
on dépile F : L=[AB]
F NULL, L non vide, on dépile A: L=[B], on affiche A
on dépile B:...

déjà à ce niveau là, on se rend compte qu'on a pas affiché la partie gauche de l'arbre alors que ca aurait du etre le cas.
(on s'attend à voir BAE)

[joel76]

Si si, ça marche :

considérons l'arbre

Code: Tout sélectionner

     A
  B     E
C   D F   G <---C,D,F,G sont NULL


Soit L la pile, ( tete à gauche <<== je ne comprends pas ce que tu veux dire)
L=[A]
on depile A: L=[]
A non NULL, L=[EAB] <== Non erreur, c'est une pile et j'empile d'abord la feuille droite donc L = [BAE]
Depile B, L = [AE].
B non NULL, L = [CBDAE]
Depile C, L = [BDAE]
C NULL, depile B, L = [DAE], affiche valeur de B
depile D L = [AE]
D NULL, depile A L= [E], affiche valeur de A
depile E, L = []
E non NULL, L = [FEG]
depile F, L = [EG]
F NULL, depile E, L = [G], affiche valeur de E
depile G, L = [], pile vide on fait rien

[fatal_error]

ouais ok

tete à gauche <<== je ne comprends pas ce que tu veux dire

ca veut dire que j'insère à la fin (push_back) donc sur la droite et que je dépile à gauche...
alors qu'en fait tu insères à gauche et dépile à gauche

[joel76]

ouais ok

ca veut dire que j'insère à la fin (push_back) donc sur la droite et que je dépile à gauche...
alors qu'en fait tu insères à gauche et dépile à gauche

Tu utilises une file alors, pas une pile.

[Helene02]

on doit tout d'abord connaitre la structure d'arbre en commençant par un schéma de conception car ça peut nous aider à programmer notre code.
je vous suggérer de essayer avec ce code :

void addNode(node **tree)
{
node *tNode;
node *tTree = *tree;

node *e = malloc(sizeof(node));
e->left = NULL;
e->right = NULL;

if(tTree)
do
{
tNode = tTree;

{
tTree = tTree->right;
if(!tTree) tNode->right = e;
}
else
{
tTree = tTree->left;
if(!tTree) tNode->left = e;
}
}
while(tTree);
else *tree = e;
}

[joel76]

Il est plus pratique de renvoyer un noeud plutôt que de modifier ce noeud.
J'aurais plutôt écrit quelque chose du style

Code: Tout sélectionner

node *addNode(node *tree)

Maintenant, je pense qu'il y a une erreur de copier/coller : le code indenté

Code: Tout sélectionner

void addNode(node **tree)
{
   node *tNode;
   node *tTree = *tree;

   node *e = malloc(sizeof(node));
   e->left = NULL;
   e->right = NULL;

   if(tTree)
      do
      {
         tNode = tTree;
         {
            tTree = tTree->right;
            if(!tTree)
               tNode->right = e;
         }
         else
         {
            tTree = tTree->left;
            if(!tTree)
               tNode->left = e;
         }
      }
      while(tTree);
   else
      *tree = e;
}

[fatal_error]

hello all,

je pense que rockleader a sa réponse parmi tout ca!
Question subsidiaire pour comparer les méthodes:
comment feriez pour transformer la récursive suivante en itérative! (les printf sont pas facultatifs)

Code: Tout sélectionner

int tri(Tree* t){
 if(t==NULL) return 0;
 printf("%d",t->value);
 int sum = tri(t->left);
 printf("%d",sum);
 int sum2 = tri(t->right);
 int total = sum+sum2+t->value;
 printf("%d",total);
 return total;
}


[joel76]

Pareil :

Code: Tout sélectionner

empiler t
valeur v
      fin si
   sinon
      empiler arbre-gauche
      empiler arbre
      empiler arbre_droit
   fin si
fin tant que

afficher valeur

[Rockleader]

Merci à tous pour ces réponses; c'est bien plus clair pour l'algo désormais, mais je dois bien avouer que je suis resté coincé quand même parce que j'ai pas réussi à implémenter une pile de noeud...tant pis je verrais ça plus tard en tp ;)

[joel76]

Merci à tous pour ces réponses; c'est bien plus clair pour l'algo désormais, mais je dois bien avouer que je suis resté coincé quand même parce que j'ai pas réussi à implémenter une pile de noeud...tant pis je verrais ça plus tard en tp

Par exemple ça devrait faire l'affaire

Code: Tout sélectionner

typedef struct elpile {
  GRD *feuille;
  struct elpile * suivant; //pointeur sur la feuille suivante
 } pile;

pile *initpile(void)
{
   return NULL;
}

// retourne 1 si la pile est vide
int pilevide(pile *p)
{
   return p == NULL;
}

pile *empile(pile *p, GRD *feuille)
{
   pile *tmp = malloc(sizeof(*tmp));

   if (tmp == NULL)
   {
      puts("pb memoire");
      exit(0);
   }
   tmp->feuille = feuille;
   tmp->suivant = p;
   return tmp;
}

GRD *depile(pile **p)
{
   GRD *feuille = (*p)->feuille;

   pile *tmp = *p;
   *p = (*p)->suivant;
   free(tmp);

   return feuille;
}


[fatal_error]

@Joel76

Pareil :

non, les printf sont pas facultatifs.

[joel76]

@Joel76
non, les printf sont pas facultatifs.

Comme d'hab j'ai lu trop vite :mur:
[EDIT] du coup c'est un peu plus coton !!!

[Rockleader]

Hello; j'ai essayer de mettre en place l'algorithme en ré-utilisant ta structure et tes fonctions.

J'ai juste rajouté un typedef de pile* pour renommé le pointeur en PILE (même si je le redis je sais que c'est mal^^)


Mais je prend tout un tas d'erreur à l'exécution que je n'arrive pas à régler sur les types

arbre.c: In function ‘empile’:
arbre.c:72:8: error: request for member ‘feuille’ in something not a structure or union
tmp->feuille = feuille;
^
arbre.c:73:5: error: dereferencing pointer to incomplete type
tmp->suivant = p;
^
arbre.c: In function ‘depile’:
arbre.c:79:21: error: dereferencing pointer to incomplete type
GRD *feuille = (*p)->feuille;
^
arbre.c:82:11: error: dereferencing pointer to incomplete type
*p = (*p)->suivant;
^
unit_test_itArbre.c: In function ‘triIteratifGRD’:
unit_test_itArbre.c:12:7: error: incompatible types when assigning to type ‘struct unfeuille’ from type ‘struct unfeuille **’
(*a)=depile(&p);
^
unit_test_itArbre.c:17:9: error: incompatible types when assigning to type ‘struct unfeuille’ from type ‘struct unfeuille **’
(*a)=depile(&(p));
^
unit_test_itArbre.c:18:23: error: invalid type argument of ‘->’ (have ‘struct unfeuille’)
printf("%d\n",(*a)->val);
^
unit_test_itArbre.c:23:19: error: invalid type argument of ‘->’ (have ‘struct unfeuille’)
p=empile(p,(*a)->gauche);
^
unit_test_itArbre.c:24:4: error: incompatible type for argument 2 of ‘empile’
p=empile(p,(*a));
^
In file included from unit_test_itArbre.c:1:0:
arbre.h:25:6: note: expected ‘struct unfeuille **’ but argument is of type ‘struct unfeuille’
PILE empile(PILE p, GRD *feuille);
^
unit_test_itArbre.c:25:19: error: invalid type argument of ‘->’ (have ‘struct unfeuille’)
p=empile(p,(*a)->droite);

Sachant que du coup voici ce que sont devenu les fonctions.

Code: Tout sélectionner

PILE empile(PILE p, GRD *feuille)
{
   PILE tmp = malloc(sizeof(tmp));

   if (tmp == NULL)
   {
      puts("pb memoire");
      exit(0);
   }
   tmp->feuille = feuille;
   tmp->suivant = p;
   return tmp;
}

GRD *depile(PILE *p)
{
   GRD *feuille = (*p)->feuille;

   PILE tmp = *p;
   *p = (*p)->suivant;
   free(tmp);

   return feuille;
}

Code: Tout sélectionner

void triIteratifGRD(GRD a)
{
   PILE p=initpile();
   while(!pilevide(p))
   {
      (*a)=depile(&p);
      if(estVideGRD(a))
      {
         if(!pilevide(p))
         {
            (*a)=depile(&(p));
            printf("%d\n",(*a)->val);
         }
      }
      else
      {
         p=empile(p,(*a)->gauche);
         p=empile(p,(*a));
         p=empile(p,(*a)->droite);
      }
   }
}

[Rockleader]

J'ai pu éliminer les ereurs de la fonction de tri à la compilation; mais il me reste tous les dereferencing pointer to incomplete type que je n'arrive pas à régler sur empiler et dépiler et je ne comprends absolument pas comment régler ça.


Par ailleurs j'ai modifié GRD *depile(PILE *p) en GRD depile; je voyais pas pourquoi renvoyer un pointeur de GRD.

[joel76]

J'ai recopié mon code en oubliant que tu cachais les pointeurs ...
Pour ce qui de la dérécursification de fatal_error, pour le moment je sèche, et la réponse n'est pas pour demain, car je suis absent pendant quelques jours

A+

EDIT en y refléchissant, j'ai l'impression qu'il faut gérer de une pile de piles !!!

[fatal_error]

un coup c'est pile, un coup c'est PILE, avec des typedefs machin*, quelque part, tu cherches!

Deref pointers to incomplete type, c'est typiquement quand tu fais une forward declaration mais que tu inclues pas le type.
quand tu accèdes à ptr->, tu as besoin de connaitre l'objet *ptr. Sauf que si tu connais pas son type (qui se trouve typiquement dans un autre include) ben le compilo clash.

Même si c'est pas ça, de toute facon tu as la ligne!
et tu y verrais sans doute plus clair en enlevant tes typedefs, quitte à les rajouter en fin de projet si c'est une exigence de ton professeur (stupide pour le coup)

[Rockleader]

Ouai c'est une exigence de passer par le stypedef.

Et non ça ne vient pas du fait que j'utilise un autre type inconnu; j'ai mis toutes mes structures dans un même .h; il n'y a donc aucun soucis de ce coté là.