Référence du fichier integer_bitree.h

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

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

Aller au code source de ce fichier.

Structures de données
struct	integer_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type int Plus de détails...
struct	integer_bitree_t
	Type de données pour l'arbre binaire. Plus de détails...

Définitions de type
typedef struct integer_bitreenode_t	integer_bitreenode_t
	Type de données pour un noeud de l'arbre binaire stockant des valeurs de type int
typedef struct integer_bitree_t	integer_bitree_t
	Type de données pour l'arbre binaire.

Fonctions
void	integer_bitree_init (integer_bitree_t *tree)
	Initialisation d'un nouvel arbre binaire.
void	integer_bitree_destroy (integer_bitree_t *tree)
	Destruction d'un arbre binaire.
int	integer_bitree_ins_left (integer_bitree_t *tree, integer_bitreenode_t *node, int data)
	Insertion d'un noeud en position fils gauche dans un arbre binaire à une position donnée.
int	integer_bitree_ins_right (integer_bitree_t *tree, integer_bitreenode_t *node, int data)
	Insertion d'un noeud en position fils droit dans un arbre binaire à une position donnée.
void	integer_bitree_rem_left (integer_bitree_t *tree, integer_bitreenode_t *node)
	Suppression d'un sous arbre en position fils gauche dans un arbre binaire à une position donnée.
void	integer_bitree_rem_right (integer_bitree_t *tree, integer_bitreenode_t *node)
	Suppression d'un sous arbre en position fils droit dans un arbre binaire à une position donnée.
int	integer_bitree_merge (integer_bitree_t *merge, integer_bitree_t *left, integer_bitree_t *right, int data)
	Fusion de deux arbres binaires.
int	integer_bitree_size (integer_bitree_t *tree)
	Accesseur pour la taille de l'arbre binaire.
integer_bitreenode_t *	integer_bitree_root (integer_bitree_t *tree)
	Accesseur pour récupérer la racine.
bool	integer_bitree_is_eob (integer_bitreenode_t *node)
	Test si un noeud est la fin du branche.
bool	integer_bitree_is_leaf (integer_bitreenode_t *node)
	Test si un noeud est une feuille.
int	integer_bitree_data (integer_bitreenode_t *node)
	Accesseur pour récupérer la valeur stockée dans un noeud.
integer_bitreenode_t *	integer_bitree_left (integer_bitreenode_t *node)
	Accesseur pour récupérer le fils gauche d'un noeud.
integer_bitreenode_t *	integer_bitree_right (integer_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 int .

Documentation des définitions de type

integer_bitree_t

typedef struct integer_bitree_t integer_bitree_t

Type de données pour l'arbre binaire.

integer_bitreenode_t

typedef struct integer_bitreenode_t integer_bitreenode_t

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

Documentation des fonctions

integer_bitree_data()

int integer_bitree_data

(

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

Renvoie

la valeur de type int stockée dans node

integer_bitree_destroy()

void integer_bitree_destroy

(

integer_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 integer_bitree_ins_left et integer_bitree_ins_right.

Paramètres

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

integer_bitree_init()

void integer_bitree_init

(

integer_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 integer_bitree_t

integer_bitree_ins_left()

int integer_bitree_ins_left	(	integer_bitree_t *	tree,
		integer_bitreenode_t *	node,
		int	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 integer_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données integer_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)

integer_bitree_ins_right()

int integer_bitree_ins_right	(	integer_bitree_t *	tree,
		integer_bitreenode_t *	node,
		int	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 integer_bitree_t contenant la racine de l'arbre
node	est un pointeur vers la structure de données integer_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)

integer_bitree_is_eob()

bool integer_bitree_is_eob

(

integer_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 integer_bitreenode_t représentant le noeud à tester

Renvoie

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

integer_bitree_is_leaf()

bool integer_bitree_is_leaf

(

integer_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 integer_bitreenode_t représentant le noeud à tester

Renvoie

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

integer_bitree_left()

integer_bitreenode_t * integer_bitree_left

(

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

Renvoie

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

integer_bitree_merge()

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

integer_bitree_rem_left()

void integer_bitree_rem_left	(	integer_bitree_t *	tree,
		integer_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 integer_bitree_rem_left et integer_bitree_rem_right

Paramètres

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

integer_bitree_rem_right()

void integer_bitree_rem_right	(	integer_bitree_t *	tree,
		integer_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 integer_bitree_rem_left et integer_bitree_rem_right

Paramètres

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

integer_bitree_right()

integer_bitreenode_t * integer_bitree_right

(

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

Renvoie

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

integer_bitree_root()

integer_bitreenode_t * integer_bitree_root

(

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

Renvoie

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

integer_bitree_size()

int integer_bitree_size

(

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

Renvoie

une valeur entière indiquant la taille