Programmation Impérative
Imperative Programming

TP Arbres

Type definition
Définition des types

We start by defining some structures.

/* Arbres binaires tout simplement */
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

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

typedef struct noeud * arbre_t;

We‘ll add a new set of values in the tree.


void ajout (arbre_t * a, int v, float x) {
  arbre_t new;
  int rande;
  if (! (*a)) {
	new = (arbre_t) malloc (sizeof (noeud_t));
	new->num = v;
	new->val = x;
	new->sg = (arbre_t) 0;
	new->sd = (arbre_t) 0;
	*a = new;
	return;
  }
  rande = rand ();
  if (rande & 0x01) {
	/* on le met à gauche*/
    if (! ((*a)->sg)) {
	  /* s'il ny a pas de fils gauche */
      (*a)->sg = (arbre_t) malloc (sizeof (noeud_t));
      (*a)->sg->num = v;
      (*a)->sg->val = x;
      (*a)->sg->sg = (arbre_t) 0;
      (*a)->sg->sd = (arbre_t) 0;
      return;
    }
    ajout(&((*a)->sg), v, x);
	return;
  }
  /* on le met donc a droite*/
  if (! ((*a)->sd)) {
	/* s'il ny a pas de fils droit */
    (*a)->sd = (arbre_t) malloc (sizeof (noeud_t));
    (*a)->sd->num = v;
    (*a)->sd->val = x;
    (*a)->sd->sg = (arbre_t) 0;
    (*a)->sd->sd = (arbre_t) 0;
    return;
  }
  ajout(&((*a)->sd), v, x);
  return;
}
/*
To create the tree, you add, one after the other, the values in the
tree.*/
arbre_t creation (int n) {
  arbre_t a;
  float x, y;
  x = 1.5;
  y = 0.21;
  a = (arbre_t) 0;
  srand(time(NULL));
  while (n--) {
	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_t a) {
  if (a) {
	afficharbre (a->sg);
	printf("%d %3.2f ", a->num, a->val);
	afficharbre (a->sd);
  }
}

int appartient (int nu, arbre_t 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.


void ajout (arbre_t * a, int v, float x, float y) {
  arbre_t new;
  int pivot;
  
  if (! (*a)) {
	new = (arbre_t) malloc (sizeof (noeud_t));
	assert(new);
	new->num = v;
	new->coef = y;
	new->unit = x;
	new->sg = (arbre_t) 0;
	new->sd = (arbre_t) 0;
	(*a) = new;
	return;
  }
  pivot = (*a)->num;
  /*
  printf(" insere %d en %d avec %2d\n", v, a->num, rande %100);
  */
  if (v < pivot) {
	/* on le met à gauche*/
    if (! ((*a)->sg)) {
	  /* s‘il ny a pas de fils gauche */
      (*a)->sg = (arbre_t) malloc (sizeof (noeud_t));
      assert((*a)->sg);
      (*a)->sg->num = v;
      (*a)->sg->coef = y;
      (*a)->sg->unit = x;
      (*a)->sg->sg = (arbre_t) 0;
      (*a)->sg->sd = (arbre_t) 0;
      return;
    }
    ajout(&((*a)->sg), v, x, y);
    return;
  }
  /* on le met donc a droite*/
  if (! ((*a)->sd)) {
	/* s‘il ny a pas de fils droit */
    (*a)->sd = (arbre_t) malloc (sizeof (noeud_t));
    assert((*a)->sd);
    (*a)->sd->num = v;
    (*a)->sd->coef = y;
    (*a)->sd->unit = x;
    (*a)->sd->sg = (arbre_t) 0;
    (*a)->sd->sd = (arbre_t) 0;
    return;
  }
  ajout(&((*a)->sd), v, x, y);
  return ;
}

arbre_t creation (int n) {
  arbre_t 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_t 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);
}

Puis une fonction qui compte le nombre d‘occurences d‘une certaine valeur non entière x dans cet arbre.
Puis une fonction qui affiche toutes les valeurs (val) dans l‘ordre croissant.
Puis une fonction qui affiche toutes les valeurs (val) dans l‘ordre décroissant.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre.
Puis une fonction qui renvoie le nombre de feuilles de l‘arbre.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement deux successeurs.
Puis une fonction qui renvoie le nombre de sommets de l‘arbre ayant effectivement un successeur.

Dernière mise à jour le 25/3/2024 12h00

Programmation Impérative Imperative Programming

TP Arbres

Programmation Impérative
Imperative Programming