Programmation Impérative
 Imperative Programming

TP Arbres


  1. Type definition
    Définition des types
    /* Arbres binaires tout simplement */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

struct noeud {
  int num;
  float val;
  struct noeud * sg;
  struct noeud * sd;
} ;

typedef struct noeud noeud;
typedef struct noeud * arbre;
    Pour ajouter un élément puis construire un tel arbre :

    arbre ajout (arbre a, int v, float x) {
  arbre new;
  int rande;
  if (! a) {
	new = (arbre) malloc (sizeof (noeud));
	new->num = v;
	new->val = x;
	new->sg = (arbre) 0;
	new->sd = (arbre) 0;
	return new;
  }
  rande = rand ();
  /*
  printf(" insere %d en %d avec %2d\n", v, a->num, rande %10);
  */
  if (rande % 2) {
	/* on le met à gauche*/
	if (! (a->sg)) {
	  /* s‘il ny a pas de fils gauche */
	  a->sg = (arbre) malloc (sizeof (noeud));
	  a->sg->num = v;
	  a->sg->val = x;
	  a->sg->sg = (arbre) 0;
	  a->sg->sd = (arbre) 0;
	  return a;
	}
	a->sg = ajout(a->sg, v, x);
	return a;
  }
  /* on le met donc a droite*/
  if (! (a->sd)) {
	/* s‘il ny a pas de fils droit */
	a->sd = (arbre) malloc (sizeof (noeud));
	a->sd->num = v;
	a->sd->val = x;
	a->sd->sg = (arbre) 0;
	a->sd->sd = (arbre) 0;
	return a;
  }
  a->sd = ajout(a->sd, v, x);
  return a;
}
/*
To create the tree, you add, one after the other, the values in the
tree.*/
arbre creation (int n) {
  arbre a;
  float x, y;
  x = 1.5;
  y = 0.21;
  a = (arbre) 0;
  srand(time(NULL));
  while (n--) {
	a = ajout (a, n, x);
	x += y;
	y += 0.06;
	if (x > 3.0 || x < -2.0) {
	  y = - y;
	}
  }
  return a;
}
    It is also possible to show the tree created: 
    void afficharbre (arbre a) {
  if (a) {
	afficharbre (a->sg);
	printf("%d %3.2f ", a->num, a->val);
	afficharbre (a->sd);
  }
}

    int appartient (int nu, arbre a) {
  if (! a)
    return 0;
  if (a->num == nu)
    return 1;
  if (appartient (nu, a->sd))
    return 1;
  return appartient (nu, a->sg);
}
    Vous devez maintenant :
    • Trouver le plus grand val dans un arbre.
    • Trouver le second plus petit val dans un arbre.
    • Compter le nombre de noeuds de l‘arbre.
    • Compter le nombre de noeuds dont le champ val est supérieur à une valeur donnée.
    • Compter le nombre de feuilles de l‘arbre (une feuille est un noeud qui n‘a aucun successeur).
    • Renvoyer la profondeur d‘un noeud de l‘arbre. La profondeur est le nombre de générations entre la racine de l‘arbre et la cellule cherchée. La racine est à la profondeur 0, ses successeurs directs à la profondeur 1, etc.
    • Renvoyer la profondeur maximale de l‘arbre.

    Arbres binaires de recherche

    Voici une réécriture des fonctions ajout et création. 
    arbre ajout (arbre a, int v, float x) {
  arbre new;
  if (! a) {
	new = (arbre) malloc (sizeof (noeud));
	new->num = v;
	new->val = x;
	new->sg = (arbre) 0;
	new->sd = (arbre) 0;
	return new;
  }
  if (x < a->val) {
	/* on le met à gauche*/
	if (! (a->sg)) {
	  /* s‘il ny a pas de fils gauche */
	  a->sg = (arbre) malloc (sizeof (noeud));
	  a->sg->num = v;
	  a->sg->val = x;
	  a->sg->sg = (arbre) 0;
	  a->sg->sd = (arbre) 0;
	  return a;
	}
	a->sg = ajout(a->sg, v, x);
	return a;
  }
  /* on le met donc a droite*/
  if (! (a->sd)) {
	/* s‘il ny a pas de fils droit */
	a->sd = (arbre) malloc (sizeof (noeud));
	a->sd->num = v;
	a->sd->val = x;
	a->sd->sg = (arbre) 0;
	a->sd->sd = (arbre) 0;
	return a;
  }
  a->sd = ajout(a->sd, v, x);
  return a;
}
arbre creation (int n) {
  arbre a;
  float x, y;
  x = 1.5;
  y = 0.21;
  a = (arbre) 0;
  while (n--) {
	a = ajout (a, n, x);
	x += y;
	y += 0.06;
	if (x > 3.0 || x < -2.0) {
	  y = - y;
	}
  }
  return a;
}
    Fonction de recherche : 
    int appartient (arbre a, float x) {
  if (! a)
	return 0;
  if (a->val == x)
	return 1;
  if (a->val > x)
	return appartient (a->sg, x);
  return appartient (a->sd, x);
}
    1. Puis une fonction qui compte le nombre d‘occurences d‘une certaine valeur non entière x dans cet arbre.
    2. Puis une fonction qui affiche toutes les valeurs (val) dans l‘ordre croissant.
    3. Puis une fonction qui affiche toutes les valeurs (val) dans l‘ordre décroissant.
    4. Puis une fonction qui renvoie le nombre de sommets de l‘arbre.
    5. Puis une fonction qui renvoie le nombre de feuilles de l‘arbre.
    6. Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement deux successeurs.
    7. Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement un successeur.
    Dernière mise à jour le 12/3/2024 18h00