arbre.c File Reference

#include <stdlib.h>
#include "arbre.h"

Go to the source code of this file.

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)

Function Documentation

ArbreVide()

Arbre * ArbreVide

(

)

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
	)

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
	)

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

)

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

)

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

)

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
	)

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
	)

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).

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

)

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.