Référence du fichier character_bitree.h

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

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

Aller au code source de ce fichier.

Structures de données
struct	character_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type char Plus de détails...
struct	character_bitree_t
	Type de données pour l'arbre binaire. Plus de détails...

Définitions de type
typedef struct character_bitreenode_t	character_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type char
typedef struct character_bitree_t	character_bitree_t
	Type de données pour l'arbre binaire.

Fonctions
void	character_bitree_init (character_bitree_t *tree)
	Initialisation d'un nouvel arbre binaire.
void	character_bitree_destroy (character_bitree_t *tree)
	Destruction d'un arbre binaire.
int	character_bitree_ins_left (character_bitree_t *tree, character_bitreenode_t *node, char data)
	Insertion d'un noeud en position fils gauche dans un arbre binaire à une position donnée.
int	character_bitree_ins_right (character_bitree_t *tree, character_bitreenode_t *node, char data)
	Insertion d'un noeud en position fils droit dans un arbre binaire à une position donnée.
void	character_bitree_rem_left (character_bitree_t *tree, character_bitreenode_t *node)
	Suppression d'un sous arbre en position fils gauche dans un arbre binaire à une position donnée.
void	character_bitree_rem_right (character_bitree_t *tree, character_bitreenode_t *node)
	Suppression d'un sous arbre en position fils droit dans un arbre binaire à une position donnée.
int	character_bitree_merge (character_bitree_t *merge, character_bitree_t *left, character_bitree_t *right, char data)
	Fusion de deux arbres binaires.
int	character_bitree_size (character_bitree_t *tree)
	Accesseur pour la taille de l'arbre binaire.
character_bitreenode_t *	character_bitree_root (character_bitree_t *tree)
	Accesseur pour récupérer la racine.
bool	character_bitree_is_eob (character_bitreenode_t *node)
	Test si un noeud est la fin du branche.
bool	character_bitree_is_leaf (character_bitreenode_t *node)
	Test si un noeud est une feuille.
char	character_bitree_data (character_bitreenode_t *node)
	Accesseur pour récupérer la valeur stockée dans un noeud.
character_bitreenode_t *	character_bitree_left (character_bitreenode_t *node)
	Accesseur pour récupérer le fils gauche d'un noeud.
character_bitreenode_t *	character_bitree_right (character_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 char .

Documentation des définitions de type

character_bitree_t

typedef struct character_bitree_t character_bitree_t

Type de données pour l'arbre binaire.

character_bitreenode_t

typedef struct character_bitreenode_t character_bitreenode_t

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

Documentation des fonctions

character_bitree_data()

char character_bitree_data

(

character_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 character_bitreenode_t représentant le noeud pour lequel on veut la valeur

Renvoie

la valeur de type char stockée dans node

character_bitree_destroy()

void character_bitree_destroy

(

character_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 character_bitree_ins_left et character_bitree_ins_right.

Paramètres

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

character_bitree_init()

void character_bitree_init

(

character_bitree_t *

tree

)

Initialisation d'un nouvel arbre binaire.

Met à zéro la taille et à NULL le pointeur vers la racine

Paramètres

tree	est un pointeur vers la structure de données character_bitree_t

character_bitree_ins_left()

int character_bitree_ins_left	(	character_bitree_t *	tree,
		character_bitreenode_t *	node,
		char	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 character_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données character_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)

character_bitree_ins_right()

int character_bitree_ins_right	(	character_bitree_t *	tree,
		character_bitreenode_t *	node,
		char	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 character_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données character_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)

character_bitree_is_eob()

bool character_bitree_is_eob

(

character_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 character_bitreenode_t représentant le noeud à tester

Renvoie

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

character_bitree_is_leaf()

bool character_bitree_is_leaf

(

character_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 character_bitreenode_t représentant le noeud à tester

Renvoie

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

character_bitree_left()

character_bitreenode_t * character_bitree_left

(

character_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 character_bitreenode_t représentant le noeud pour lequel on veut le fils gauche

Renvoie

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

character_bitree_merge()

int character_bitree_merge	(	character_bitree_t *	merge,
		character_bitree_t *	left,
		character_bitree_t *	right,
		char	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 character_bitree_t contenant l'arbre issu de la fusion de left et right
left	est un pointeur vers la structure de données character_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 character_bitree_t représentant un arbre binaire qui sera en position sous arbre droit dans la fusion
data	valeur de type char 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)

character_bitree_rem_left()

void character_bitree_rem_left	(	character_bitree_t *	tree,
		character_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 character_bitree_rem_left et character_bitree_rem_right

Paramètres

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

character_bitree_rem_right()

void character_bitree_rem_right	(	character_bitree_t *	tree,
		character_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 character_bitree_rem_left et character_bitree_rem_right

Paramètres

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

character_bitree_right()

character_bitreenode_t * character_bitree_right

(

character_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 character_bitreenode_t représentant le noeud pour lequel on veut le fils droit

Renvoie

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

character_bitree_root()

character_bitreenode_t * character_bitree_root

(

character_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 character_bitree_t contenant la racine de l'arbre binaire

Renvoie

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

character_bitree_size()

int character_bitree_size

(

character_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 character_bitree_t contenant la racine de l'arbre binaire

Renvoie

une valeur entière indiquant la taille