Exemple :

1. j'entre en premier la valeur 10.
2. Puis j'entre 5 : il est plus petit que 10 donc le champ pp de la première boite va pointer vers cette seconde boite
3. j'entre 8 : plus petit que 10, or pp est déjà occupé. pg est libre mais ça ne respecterait pas la consigne. donc je teste la seconde boite. 8 est plus grand que 5, pg est libre, j'y place donc l'adresse de ma nouvelle boite.
4. puis j'entre 18, 48, 15, 12, 10, 9, 2. J'obtiens l'arbre :
   

questions

• création de l'arbre (je l'explique au tableau)
• affichez toutes les valeurs de l'arbre, dans n'importe quel ordre
• affichez dans l'ordre croissant, sans effectuer de tri
• calculez la somme de toutes les valeurs contenues dans l'arbre

solution

#include <conio.h>
#include <stdio.h>
#include <stdlib.h>

typedef struct boite      /*je crée ma structure boite*/
  {
  float val;              /*qui comprend un flottant*/
  struct boite* pp;       /*et pp est une adresse d'une boite* */
  struct boite* pg;       /*idem*/
  }
  boite;                  /* je nomme ma structure*/
typedef boite* pointeur;  /* le type "pointeur" est équivalent à "boite*" */

pointeur creation (void)            /* ma fonction de saisie*/
  {
  pointeur racine=NULL;             /*déclaration racine, de type pointeur, qui est initialisé à NULL*/
  pointeur actu,nouv;               /*déclaration actu et nouv de type pointeur*/
  float x;                          /*déclaration du flottant x */
  do
    {
    printf ("valeur (<0 pour finir)?");
    scanf ("%f",&x);
    if (x>=0)                             /*on vérifie que la valeur est prenable*/
      {                                   /* NULL correspond a l'adresse 0*/
      nouv=malloc(sizeof(boite));         /*alors on réserve de la place pour une boite et je mets l'adresse dans nouv*/
      nouv->val=x;                        /*dans le champ val pointé par nouv, je place la valeur de x cad une valeur de type flottant*/
      nouv->pp=NULL;                     /* pp(c'est une adresse) de nouv vaut NULL(=adresse 0)*/
      nouv->pg=NULL;                     /* idem pour pg*/
      if (racine==NULL) racine=nouv;     /* ceci ne sera fait que pour la première boite créée, puisqu'après il n'est plus NULL*/
      else
	{
	actu=racine;
	do
	  {
	  if (x<actu->val) /*s'il est plus petit je vais le mettre dans la case pp */
	    if (actu->pp==NULL) /* si la case pp est disponible, je l'y mets */
	      {
	      actu->pp=nouv;
	      nouv=NULL; /* c'est juste pour dire que "ca y est, on l'a casé" */
	      }
	    else actu=actu->pp; /* si pp est déjà occupé j'essaie le suivant */
	  else /*donc x>=actu->val : idem pour pg au lieu de pp */
	    if (actu->pg==NULL)
	      {
	      actu->pg=nouv;
	      nouv=NULL;
	      }
	    else actu=actu->pg;
	  }
	while (nouv!=NULL); /* tant que je ne l'ai pas "casé" */
	} /* accolade de fin du "else" */
      } /* fin du "if(x>=0)" */
    } /* fin du "do" donc doit être suivi par un "while" */
  while (x>=0);
  return (racine);
  } /* fin de la fonction creation */

void affiche(pointeur p)
/* version qui les affiche dans l'ordre (récursif) */
   {
   if (p->pp!=NULL) affiche (p->pp);
   printf ("%f ",p->val);         /* il y a un espace pour éviter qu'il colle les nombres les uns a la suite des autres*/
   if (p->pg!=NULL) affiche (p->pg);
   }

float somme(pointeur p)
  {
  float s;
  s=p->val;
  if (p->pp!=NULL) s+=somme(p->pp);
  if (p->pg!=NULL) s+=somme(p->pg);
  return (s);
  }

void main(void)
  {
  pointeur racine;
  racine=creation();
  affiche (racine);
  printf("%f",somme (racine));
  }

Commentaire

Patrick TRAU,ULP - IPST 12/12/97