Référence du fichier generic_bitree.h

Structure de données d'arbre binaire contenant des valeurs de type void* . Plus de détails...

#include <stdlib.h>
#include <stdbool.h>

Aller au code source de ce fichier.

Structures de données
struct	generic_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type void* Plus de détails...
struct	generic_bitree_t
	Type de données pour l'arbre binaire générique. Plus de détails...

Définitions de type
typedef struct generic_bitreenode_t	generic_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type void*
typedef struct generic_bitree_t	generic_bitree_t
	Type de données pour l'arbre binaire générique.

Fonctions
void	generic_bitree_init (generic_bitree_t *tree, int(*compare)(const void *key1, const void *key2), void *(*build)(const void *data), void(*destroy)(void *data))
	Initialisation d'un nouvel arbre binaire générique.
void	generic_bitree_destroy (generic_bitree_t *tree)
	Destruction d'un arbre binaire.
int	generic_bitree_ins_left (generic_bitree_t *tree, generic_bitreenode_t *node, const void *data)
	Insertion d'un noeud en position fils gauche dans un arbre binaire à une position donnée.
int	generic_bitree_ins_right (generic_bitree_t *tree, generic_bitreenode_t *node, const void *data)
	Insertion d'un noeud en position fils droit dans un arbre binaire à une position donnée.
void	generic_bitree_rem_left (generic_bitree_t *tree, generic_bitreenode_t *node)
	Suppression d'un sous arbre en position fils gauche dans un arbre binaire à une position donnée.
void	generic_bitree_rem_right (generic_bitree_t *tree, generic_bitreenode_t *node)
	Suppression d'un sous arbre en position fils droit dans un arbre binaire à une position donnée.
int	generic_bitree_merge (generic_bitree_t *merge, generic_bitree_t *left, generic_bitree_t *right, const void *data)
	Fusion de deux arbres binaires.
int	generic_bitree_size (generic_bitree_t *tree)
	Accesseur pour la taille de l'arbre binaire.
generic_bitreenode_t *	generic_bitree_root (generic_bitree_t *tree)
	Accesseur pour récupérer la racine.
bool	generic_bitree_is_eob (generic_bitreenode_t *node)
	Test si un noeud est la fin du branche.
bool	generic_bitree_is_leaf (generic_bitreenode_t *node)
	Test si un noeud est une feuille.
void *	generic_bitree_data (generic_bitreenode_t *node)
	Accesseur pour récupérer la valeur stockée dans un noeud.
generic_bitreenode_t *	generic_bitree_left (generic_bitreenode_t *node)
	Accesseur pour récupérer le fils gauche d'un noeud.
generic_bitreenode_t *	generic_bitree_right (generic_bitreenode_t *node)
	Accesseur pour récupérer le fils droit d'un noeud.

Description détaillée

Structure de données d'arbre binaire contenant des valeurs de type void* .

Documentation des définitions de type

generic_bitree_t

typedef struct generic_bitree_t generic_bitree_t

Type de données pour l'arbre binaire générique.

generic_bitreenode_t

typedef struct generic_bitreenode_t generic_bitreenode_t

Type de données pour un noeud de l'arbre binaire stockant des valeurs de type void*

Documentation des fonctions

generic_bitree_data()

void * generic_bitree_data

(

generic_bitreenode_t *

node

)

Accesseur pour récupérer la valeur stockée dans un noeud.

Paramètres

node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud pour lequel on veut la valeur

Renvoie

la valeur de type void* stockée dans node

generic_bitree_destroy()

void generic_bitree_destroy

(

generic_bitree_t *

tree

)

Destruction d'un arbre binaire.

Met à zéro la taille et à NULL le pointeur vers la racine après avoir parcourus l'arbre pour détruire tous les noeuds en utilisant les fonctions generic_bitree_ins_left et generic_bitree_ins_right.

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre

generic_bitree_init()

void generic_bitree_init	(	generic_bitree_t *	tree,
		int(*)(const void *key1, const void *key2)	compare,
		void *(*)(const void *data)	build,
		void(*)(void *data)	destroy )

Initialisation d'un nouvel arbre binaire générique.

Met à zéro la taille et à NULL le pointeur vers la racine. Cette fonction nécessite une fonction de comparaison des éléments de la file, une fonction de construction d'un élément de la file et une fonction de destruction des éléments de la file.

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t
compare	fonction permettant la comparaison de deux éléments de l'arbre
build	fonction permettant la construction d'une valeur de l'arbre
destroy	fonction permettant la destruction d'une valeur de l'arbre

generic_bitree_ins_left()

int generic_bitree_ins_left	(	generic_bitree_t *	tree,
		generic_bitreenode_t *	node,
		const void *	data )

Insertion d'un noeud en position fils gauche dans un arbre binaire à une position donnée.

1. On trouve la bonne position où insérer
   • si node == NULL alors on ajoute un fils gauche à la racine si emplacement vide autrement erreur
   • si node != NULL alors on ajoute un fils gauche au noeud node si emplacement vide autrement erreur
2. On alloue un nouveau noeud et on y stocke la valeur de data

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud auquel ajouté un fils gauche
data	la valeur à stocker dans le fils gauche créé

Renvoie

une valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

generic_bitree_ins_right()

int generic_bitree_ins_right	(	generic_bitree_t *	tree,
		generic_bitreenode_t *	node,
		const void *	data )

Insertion d'un noeud en position fils droit dans un arbre binaire à une position donnée.

1. On trouve la bonne position où insérer
   • si node == NULL alors on ajoute un fils droit à la racine si emplacement vide autrement erreur
     • si node != NULL alors on ajoute un fils droit au noeud node si emplacement vide autrement erreur
2. On alloue un nouveau noeud et on y stocke la valeur de data

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud auquel ajouté un fils droit
data	la valeur à stocker dans le fils droit créé

Renvoie

une valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

generic_bitree_is_eob()

bool generic_bitree_is_eob

(

generic_bitreenode_t *

node

)

Test si un noeud est la fin du branche.

Vérifie si le noeud est NULL ou pas

Paramètres

node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud à tester

Renvoie

la valeur booléenne indiquant si node est NULL ou pas

generic_bitree_is_leaf()

bool generic_bitree_is_leaf

(

generic_bitreenode_t *

node

)

Test si un noeud est une feuille.

Vérifie que le fils gauche et le fils droit d'un noeud sont NULL

Paramètres

node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud à tester

Renvoie

la valeur booléenne indiquant si node est une feuille ou pas

generic_bitree_left()

generic_bitreenode_t * generic_bitree_left

(

generic_bitreenode_t *

node

)

Accesseur pour récupérer le fils gauche d'un noeud.

Donne le pointeur vers le noeud fils gauche

Paramètres

node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud pour lequel on veut le fils gauche

Renvoie

le pointeur vers la structure generic_bitreenode_t associée au fils gauche

generic_bitree_merge()

int generic_bitree_merge	(	generic_bitree_t *	merge,
		generic_bitree_t *	left,
		generic_bitree_t *	right,
		const void *	data )

Fusion de deux arbres binaires.

1. Initialisation du nouvel arbre merge
2. Insertion de la donnée data dans ce nouvel arbre (à la racine)
3. Ajout d'un fils gauche avec left et d'un fils droit right
4. Mise à jour de la taille du nouvel arbre

Paramètres

merge	est un pointeur vers la structure de données generic_bitree_t contenant l'arbre issu de la fusion de left et right
left	est un pointeur vers la structure de données generic_bitree_t représentant un arbre binaire qui sera en position sous arbre gauche dans la fusion
right	est un pointeur vers la structure de données generic_bitree_t représentant un arbre binaire qui sera en position sous arbre droit dans la fusion
data	valeur de type void* qui sera stockée à la racine de l'arbre binaire issue de la fusion

Renvoie

une valeur entière indiquant si tout s'est bien passé (0 pour ok, -1 pour erreur)

generic_bitree_rem_left()

void generic_bitree_rem_left	(	generic_bitree_t *	tree,
		generic_bitreenode_t *	node )

Suppression d'un sous arbre en position fils gauche dans un arbre binaire à une position donnée.

1. On trouve la bonne position où insérer
   • si node == NULL alors on supprime le sous arbre gauche de la racine
   • si node != NULL alors on supprime le sous arbre gauche du noeud node
2. Récursion pour supprimer tous les noeuds jusqu'aux feuilles en utilisant les fonctions generic_bitree_rem_left et generic_bitree_rem_right

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud auquel il faut supprimer le sous-arbre gauche

generic_bitree_rem_right()

void generic_bitree_rem_right	(	generic_bitree_t *	tree,
		generic_bitreenode_t *	node )

Suppression d'un sous arbre en position fils droit dans un arbre binaire à une position donnée.

1. On trouve la bonne position où insérer
   • si node == NULL alors on supprime le sous arbre droit de la racine
   • si node != NULL alors on supprime le sous arbre droit du noeud node
2. Récursion pour supprimer tous les noeuds jusqu'aux feuilles en utilisant les fonctions generic_bitree_rem_left et generic_bitree_rem_right

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud auquel il faut supprimer le sous-arbre droit

generic_bitree_right()

generic_bitreenode_t * generic_bitree_right

(

generic_bitreenode_t *

node

)

Accesseur pour récupérer le fils droit d'un noeud.

Donne le pointeur vers le noeud fils droit

Paramètres

node	est un pointeur vers la structure de données generic_bitreenode_t représentant le noeud pour lequel on veut le fils droit

Renvoie

le pointeur vers la structure generic_bitreenode_t associée au fils droit

generic_bitree_root()

generic_bitreenode_t * generic_bitree_root

(

generic_bitree_t *

tree

)

Accesseur pour récupérer la racine.

Donne le pointeur vers le noeud racine

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre binaire

Renvoie

le pointeur vers la structure generic_bitreenode_t associée à la racine

generic_bitree_size()

int generic_bitree_size

(

generic_bitree_t *

tree

)

Accesseur pour la taille de l'arbre binaire.

Donne le nombre de noeud dans l'arbre binaire

Paramètres

tree	est un pointeur vers la structure de données generic_bitree_t contenant la racine de l'arbre binaire

Renvoie

une valeur entière indiquant la taille