arbre.h File Reference

Go to the source code of this file.

Classes
struct	SNoeud

Typedefs
typedef int	Donnee
typedef struct SNoeud	Noeud
typedef Noeud	Arbre

Functions
void	CopierDonnees (Donnee *d1, Donnee *d2)
Arbre *	ArbreVide ()
void	Detruire (Arbre *A)
Arbre *	Creer0 (Donnee *ptr_d)
Arbre *	Creer2 (Donnee *ptr_d, Arbre *G, Arbre *D)
Noeud *	Racine (Arbre *A)
Noeud *	Gauche (Noeud *N)
void	ModifieGauche (Noeud *N, Arbre *SG)
Noeud *	Droit (Noeud *N)
void	ModifieDroit (Noeud *N, Arbre *SD)
Donnee *	Valeur (Noeud *N)

Typedef Documentation

Arbre

typedef Noeud Arbre

Un arbre binaire est un noeud appelé racine. On utilisera le type Arbre lorsqu'on désignera le noeud racine et le type Noeud lorsqu'on désigne un noeud quelconque.

Definition at line 42 of file arbre.h.

Donnee

typedef int Donnee

Definition at line 5 of file arbre.h.

Noeud

typedef struct SNoeud Noeud

Un noeud dans un arbre binaire contient une donnée, et éventuellement un pointeur vers un fils gauche et/ou vers un fils droit. On pourrait aussi stocker le noeud père ici, mais on ne s'en servira pas dans les algorithmes développés.

Function Documentation

ArbreVide()

Arbre * ArbreVide ( )

extern

Returns

l'arbre vide.

Definition at line 24 of file arbre.c.

{
  return NULL;
}

Referenced by Creer0(), and Detruire().

CopierDonnees()

void CopierDonnees ( Donnee *  d1, Donnee *  d2  )

extern

Copie une donnée dans une autre. Cette fonction est utile lorsque le type Donnee est complexe et que l'opérateur d'affectation du C ne fonctionne pas bien.

Parameters

d1	un pointeur vers la première donnée à recopier.
d2	un pointeur vers la deuxième donnée, qui sera écrasée et prendra les valeurs de d1.

Copie une donnée dans une autre. Cette fonction est utile lorsque le type ValType est complexe et que l'opérateur d'affectation du C ne fonctionne pas bien.

Parameters

d1	un pointeur vers la première donnée à recopier.
d2	un pointeur vers la deuxième donnée, qui sera écrasée et prendra les valeurs de d1.

Definition at line 15 of file arbre.c.

{
  *d2 = *d1;
}

Referenced by Creer2().

Creer0()

Arbre * Creer0 ( Donnee *  ptr_d )

extern

Crée et retourne un arbre avec un seul noeud qui recopie la donnée pointée par ptr_d.

Parameters

ptr_d

un pointeur vers une donnée.

Returns

un pointeur vers l'arbre créé (ie. un pointeur vers sa racine).

Definition at line 53 of file arbre.c.

{
  return Creer2( ptr_d, ArbreVide(), ArbreVide() );
}

References ArbreVide(), and Creer2().

Creer2()

Arbre * Creer2 ( Donnee *  ptr_d, Arbre *  G, Arbre *  D  )

extern

Crée et retourne un arbre qui l'union de deux sous-arbres plus un noeud qui recopie la donnée pointée par ptr_d.

Parameters

ptr_d	un pointeur vers une donnée.
G	un pointeur vers le futur sous-arbre gauche. Attention il ne faut plus s'en servir après, car il est intégré à l'arbre A.
D	un pointeur vers le futur sous-arbre droit. Attention il ne faut plus s'en servir après, car il est intégré à l'arbre A.

Returns

un pointeur vers l'arbre créé (ie. un pointeur vers sa racine).

Definition at line 74 of file arbre.c.

{
  Noeud* racine = (Noeud*) malloc( sizeof(Noeud) );
  CopierDonnees( ptr_d, &racine->data );
  racine->gauche = G;
  racine->droit = D;
  return racine;
}

References CopierDonnees(), SNoeud::data, SNoeud::droit, and SNoeud::gauche.

Referenced by Creer0().

Detruire()

void Detruire ( Arbre *  A )

extern

Détruit un arbre et désalloue tous ses éléments alloués.

Parameters

A	un pointeur vers un arbre valide.

Definition at line 34 of file arbre.c.

{
  if ( A != ArbreVide() )
    {
      Detruire( A->gauche );
      Detruire( A->droit );
      free( A );
    }
}

References ArbreVide(), Detruire(), SNoeud::droit, and SNoeud::gauche.

Referenced by Detruire(), ModifieDroit(), and ModifieGauche().

Droit()

Noeud * Droit ( Noeud *  N )

extern

Returns

le noeud fils droit de N (éventuellement NULL si N n'avait pas de fils droit).

Parameters

N	un pointeur vers un noeud valide.

Definition at line 128 of file arbre.c.

{
  return N->droit;
}

References SNoeud::droit.

Gauche()

Noeud * Gauche ( Noeud *  N )

extern

Returns

le noeud fils gauche de N (éventuellement NULL si N n'avait pas de fils gauche).

Parameters

N	un pointeur vers un noeud valide.

Definition at line 104 of file arbre.c.

{
  return N->gauche;
}

References SNoeud::gauche.

ModifieDroit()

void ModifieDroit ( Noeud *  N, Arbre *  SD  )

extern

Modifie le noeud N de façon à ce que SD devienne sous nouveau sous-arbre droit. L'ancien sous-arbre droit de N est désalloué.

Parameters

N	un pointeur vers un noeud valide.
SD	le nouveau sous-arbre, éventuellement vide ou réduit à un noeud.

Definition at line 140 of file arbre.c.

{
  Detruire( N->droit );
  N->droit = SD;
}

References Detruire(), and SNoeud::droit.

ModifieGauche()

void ModifieGauche ( Noeud *  N, Arbre *  SG  )

extern

Modifie le noeud N de façon à ce que SG devienne sous nouveau sous-arbre gauche. L'ancien sous-arbre gauche de N est désalloué.

Parameters

N	un pointeur vers un noeud valide.
SG	le nouveau sous-arbre, éventuellement vide ou réduit à un noeud.

Definition at line 116 of file arbre.c.

{
  Detruire( N->gauche );
  N->gauche = SG;
}

References Detruire(), and SNoeud::gauche.

Racine()

Noeud * Racine ( Arbre *  A )

extern

Retourne le noeud racine de A (éventuellement NULL si arbre vide).

Parameters

A	un pointeur vers un arbre valide.

Retourne le noeud racine de A (éventuellement NULL si arbre vide).

NB: Vu les définitions, retourne A directement, car l'arbre est confondu avec son noeud racine.

Parameters

A	un pointeur vers un arbre valide.

Definition at line 92 of file arbre.c.

{
  return A;
}

Valeur()

Donnee * Valeur ( Noeud *  N )

extern

Permet la lecture et l'écriture dans la donnée associée au noeud N.

Returns

un pointeur vers la donnee du noeud N.

Parameters

N	un pointeur vers un noeud valide.

Definition at line 153 of file arbre.c.

{
  return & N->data;
}

References SNoeud::data.