Le mois dernier, nous avons vu comment la Glib-2.0 nous permet de gérer efficacement et simplement les listes simplement et doublement chaînées. Aujourd'hui, nous allons nous intéresser à la gestion d'un autre type de structure de données : les arbres, en commençant par les arbres binaires balancés.

Un arbre permet de stocker des données dans une structure arborescente allouée dynamiquement. Chaque donnée est stockée dans un des n uds de l'arbre. De ce n ud peuvent partir un certain nombre de branches, qui sont des pointeurs vers d'autres n uds de l'arbre. Les n uds qui ne comportent pas de branches sont appelés feuilles. Il existe un n ud particulier sur lequel aucun des autres n uds ne pointe, c'est le tronc de l'arbre, que l'on appelle communément la racine. La profondeur d'un arbre (ou plutôt la hauteur...) est le nombre maximal de branches séparant la racine de chacune de ses feuilles.

Les arbres binaires ont ceci de particulier que chacun de leur n ud comporte au plus deux branches. Un arbre est dit balancé lorsque sa profondeur est toujours minimale, c'est-à-dire que les n uds plus proches de la racine sont toujours remplis (ils ont deux branches) avant les n uds proches des feuilles.

Les arbres binaires balancés proposés par la Glib-2.0 sont donc de ce type-là. Du point de vue du programmeur, les arbres binaires balancés sont simplement une structure dans laquelle on peut placer des données de manière ordonnée, peu importe que ces données soient ou non stockées dans une structure arborescente.

Les arbres binaires balancés de la Glib-2.0 sont référencés par un pointeur sur une structure (opaque) GTree et les données qu'ils peuvent contenir sont composées d'une clef, permettant de classer la donnée et de la retrouver, et d'un pointeur générique sur la donnée proprement dite. La clef doit être unique dans un arbre donné.

Avant de pouvoir stocker des données dans un arbre, il faut le créer (vide). Cela se réalise par exemple avec la fonction suivante :

Le paramètre fonction_compare est une fonction de comparaison dont le prototype doit être le suivant :

Cette fonction doit permettre de comparer deux clefs a et b. Elle doit retourner une valeur négative si a doit être classée avant b, et une valeur positive dans le cas contraire. Les clefs peuvent être de nature quelconque, mais on utilise souvent des chaînes de caractères ou des entiers.

Dans le cas de clefs alphanumériques, une fonction de comparaison possible est strcmp(), mais vous pouvez élaborer des fonctions de comparaison bien plus complexes. En fait, il y a même une autre possibilité pour créer un arbre, permettant d'utiliser une fonction de comparaison encore plus complète :

Si l'on crée un arbre avec cette fonction, fonction_compare() doit avoir le prototype suivant :

Le paramètre donnee_supplementaire de la fonction g_tree_new_with_data() sera transmis tel quel à la fonction de comparaison des clefs. Cela permet d'écrire une fonction de comparaison pour tous les arbres, mais qui réagira différemment suivant l'arbre qui l'utilise. Bon, d'accord, ce n'est pas très utilisé...

En réalité, les deux fonctions précédentes sont des appels déguisés à une fonction de création d'arbre bien plus générale encore :

Les deux premiers paramètres de cette fonction sont déjà connus. Le paramètre detruire_clef est une fonction dont le prototype est le suivant :

Cette fonction sera appelée lors de la destruction de l'arbre, avec comme paramètre chacune des clefs des n uds de l'arbre, pour éventuellement libérer la mémoire qu'elles occupaient. Si on ne veut pas utiliser de telles fonctions, il suffit de passer NULL à la place.

Le paramètre detruire_donnee est une fonction du même genre qui permet de libérer la mémoire utilisée des données de chacun des n uds de l'arbre lors de sa destruction.

Le rôle exact de detruire_clef et detruire_donnee sera plus clair en regardant l'exemple de programme.

Cette fonction libère toute la mémoire utilisée par chacun des n uds de l'arbre et appelle les éventuelles fonctions de libération de la mémoire occupées par les clefs ou les données de chaque n ud.

Lorsqu'un arbre vide a été créé, on peut commencer à y introduire des données. Cela ce fait simplement grâce à la fonction :

Cette fonction insère la donnée donnee dans l'arbre. Le paramètre clef sert à classer la donnée dans l'arbre. Si la clef existe déjà dans cet arbre, la donnée du n ud correspondant est remplacée par la nouvelle donnée. Si l'arbre a été créé avec g_tree_new_full() et qu'une fonction detruire_donnee() a été spécifiée, l'ancienne donnée est libérée par un appel à cette fonction. De même, si une fonction detruire_clef() a été spécifiée, la clef passée en paramètre (la nouvelle) est libérée par un appel à detruire_clef().

Cela peut sembler bizarre de détruire la nouvelle clef si une clef équivalente existe déjà. On peut vouloir que ce soit l'ancienne clef qui soit détruite dans ce cas. C'est ce que réalise la fonction suivante :

Le paramètre clef est évidemment la clef permettant de retrouver le n ud dans l'arbre. Si les fonctions detruire_clef() et detruire_donnee() ont été spécifiées, elles sont employées pour libérer la mémoire utilisée respectivement par la clef et la donnée de ce n ud.

Si vous voulez juste retirer le n ud de l'arbre, sans libérer la mémoire, il faut alors utiliser la fonction suivante :

Notez que si l'arbre a été créé avec g_tree_new() ou g_tree_new_with_data(), ces deux fonctions sont strictement équivalentes.

Lorsque l'arbre est construit et garni de n uds, on peut retrouver une donnée très rapidement à partir de sa clef associée, avec la fonction suivante :

La valeur de retour de cette fonction est la donnée que l'on cherche, ou NULL si la clef n'a pas été trouvée. La recherche d'une donnée dans un arbre est extrêmement rapide, surtout si on la compare à une recherche dans une liste chaînée par exemple.

Cependant, si on veut que notre arbre puisse contenir des données NULL, un appel à g_tree_lookup() ne nous dira pas si une donnée valant NULL a été trouvée ou non. C'est pourquoi on peut utiliser la fonction, un peu plus complexe, suivante :

Cette fonction renvoie TRUE si la clef a été trouvée dans l'arbre, et FALSE sinon. De plus, si le n ud a été trouvé, la donnée de ce n ud est transmise dans le pointeur donnee, et la clef de ce n ud (qui peut être physiquement différente de la clef de recherche, puisque ces deux clefs ne doivent être identiques que dans le sens de la fonction fonction_compare() définie lors de la création de l'arbre). La récupération de ces pointeurs peut par exemple permettre de libérer la mémoire utilisée par la clef et la donnée avant un g_tree_remove(), si l'arbre n'a pas été créé avec g_tree_new_full().

Comme pour les listes chaînées, il est possible d'appeler une fonction qui recevra en paramètre successivement chacun des n uds de l'arbre. Pour cela, il faut utiliser la fonction :

Cette fonction doit renvoyer FALSE si l'on souhaite continuer le parcours et TRUE sinon. En pratique, ce genre de fonction renvoie toujours FALSE, car il est bien rare que l'on doive arrêter un parcours en cours de route. Les paramètres clef et donnee sont les contenus de chacun des n uds et le paramètre donnee_sup est celui passé à la fonction g_tree_foreach(). Ici encore, tout cela sera bien plus clair dans le programme exemple.

Justement, avant de voir le premier exemple de ce mois-ci, voyons les deux dernières fonctions de la Glib-2.0 concernant les arbres binaires balancés.

Vous remarquerez que les arbres trient les n uds d'après les clefs et, si vous utilisez g_mem_profile(), vous pourrez constater que la mémoire est correctement libérée à la fin de l'exécution de ce programme.

Les arbres binaires balancés ne sont en fait qu'un cas particulier des arbres plus généraux que sait gérer la Glib-2.0. Plus exactement, la Glib-2.0 sait gérer des n uds nettement plus complexes que les n uds des arbres binaires balancés.

Un n ud (de type GNode) d'un arbre général est une structure qui contient un pointeur sur une donnée et quatre pointeurs sur d'autres n uds. Voici cette structure :

Le champ data est la donnée. Le champ parent pointe sur le n ud parent de notre n ud. Les champs next et prev pointent vers le n ud suivant et le n ud précédent de la liste des enfants du n ud parent de notre n ud. En effet, les arbres généraux n'étant pas forcément binaires, il peuvent contenir autant de n uds fils que l'on veut. Et le pointeur children pointe justement sur le premier de ces n uds fils. En général, on n'a jamais à utiliser ces champs directement, puisque des fonctions sont là pour nous simplifier la vie. Chacun des pointeurs GNode * peut être NULL.

Il n'existe pas de réelle structure pour les arbres généraux de la Glib-2.0. On utilise directement les n uds pour chacune des opérations. On reconnaît simplement la racine d'un tel arbre au fait que c'est un n ud dont les pointeurs parent, prev et next sont NULL. Plus simplement, on peut utiliser la macro suivante :

De la même façon, on peut savoir si un n ud est une feuille ou non à l'aide de la macro suivante :

Cette fonction réserve la mémoire pour la structure GNode, initialise le champ data à donnee, et tous les autres pointeurs à NULL.

Une fois le n ud créé, on peut le placer dans un arbre, ou plus exactement dans une branche. Il existe beaucoup de manières de faire cela. La première consiste à appeler la fonction suivante :

qui insère le noeud parmi les fils de parent, juste après le n ud frere. frere peut être NULL, dans quel cas, noeud est placé en dernier dans les enfants de parent. Mais si frere n'est pas NULL, il doit absolument avoir parent comme n ud parent.

La fonction suivante réalise à peu près la même chose, mais place le n ud avant frere, ou en premier parmi les enfants de parent si frere est NULL :

Les deux fonctions suivantes (la première est en réalité une macro) permettent de simplifier les cas où l'on veut ajouter un n ud respectivement en dernier et en premier parmi les enfants de parent :

Il est également possible d'ajouter un n ud parmi les enfants d'un n ud parent à une position donnée avec cette fonction :

Le paramètre position indique où l'on veut que le n ud soit placé. S'il vaut 0, le noeud sera le premier des enfants de parent ; s'il est négatif, il sera le dernier, sinon il sera à la position position.

Enfin, sachez qu'il existe trois macros permettant de créer un n ud et de le placer dans un arbre en une seule opération. Elles fonctionnent de la même façon que leur contrepartie qui ne comportent pas le suffixe «_data»:

Toutes les fonctions présentées jusqu'à maintenant renvoient un pointeur sur le n ud qui vient d'être créé ou inséré.

A l'intérieur d'un arbre, on peut facilement naviguer d'un n ud à l'autre à l'aide d'une foule de fonctions. Par exemple, il est facile de trouver le n ud précédant ou suivant un n ud donnée dans la liste des enfants d'un n ud parent à l'aide des deux macros suivantes:

Dans le même ordre d'idées, on peut trouver respectivement le premier et le dernier des frères d'un n ud avec les deux fonctions suivantes :

Un n ud peut évidemment avoir accès à son premier ou à son dernier enfant (s'il existe) avec les deux fonctions suivantes:

Réciproquement, on peut savoir à quelle position un n ud fils apparaît parmi les enfants d'un n ud. C'est ce que réalise la fonction suivante:

Cette fonction renvoie un entier positif correspondant à la position de fils dans les enfants de noeud. Le premier n ud a la position 0. Si fils n'est pas un des enfants de noeud, -1 est renvoyé.

De la même façon, la fonction suivante renvoie la position du fils de noeud dont la donnée est donnee.

On peut retrouver quel est le n ud racine de l'arbre auquel appartient un n ud donné par un appel à la fonction:

Plus généralement, la fonction suivante permet de savoir si un n ud est dans la descendance d'un autre:

Si noeud est le père de descendant, ou le père de son père, etc., cette fonction renvoie TRUE. Dans le cas contraire, elle renvoie FALSE.

Il existe également des fonctions permettant de savoir comment est situé un n ud dans un arbre. Par exemple, la fonction suivante permet de savoir quel est le nombre maximal de générations qui suivent un n ud:

Si racine a au moins un fils et aucun petit-fils, cette fonction renvoie 1 ; si racine possède au moins un petit-fils et aucun arrière-petit-fils, elle renverra 2, etc.

A l'inverse, la fonction suivante renvoie le nombre de générations qui séparent un n ud de la racine de l'arbre auquel il appartient:

Enfin, la fonction suivante renvoie le nombre de descendants d'un n ud, c'est-à-dire le nombre de ses enfants plus le nombre de ses petits-enfants, plus le nombre de ses arrières-petits-enfants, etc.:

G_TRAVERSE_NON_LEAFS, seuls les n uds non-feuilles (c'est-à-dire ayant des fils) seront comptabilisés ;
•         G_TRAVERSE_ALL, tous les n uds, feuilles et non-feuilles seront comptabilisés.

Maintenant que l'on sait créer et placer des n uds dans un arbre, et avoir un maximum d'informations sur chacun de ces n uds, on peut voir quelles sont les opérations que l'on peut appliquer à un n ud ou à un arbre tout entier.

Tout d'abord, pour un n ud donné, il est possible de retrouver quel est le n ud (s'il existe), parmi ses enfants directs (c'est-à-dire à l'exclusion des petits-enfants ou des arrières-petits-enfants), qui contient la donnée donnee. Cela se réalise à l'aide de la fonction suivante:

Le paramètre type a le même sens que pour la fonction g_node_n_nodes(). Si aucun n ud ne contient la donnée donnee, g_node_find_child() renvoie NULL.

Il est également possible d'effectuer une recherche d'une donnée parmi toute la descendance d'un n ud, ce qui revient à effectuer une recherche dans tout un arbre si le n ud en question en est la racine. Pour cela, il faut utiliser la fonction:

Le seul paramètre qui nécessite une explication est le paramètre ordre. Il indique dans quel ordre doit s'effectuer la recherche. Il peut prendre les valeurs suivantes:
•        

Suivant les cas, tel ou tel ordre est plus approprié. Par exemple, pour un arbre binaire, l'ordre G_IN_ORDER est le mieux adapté (essayez de comprendre pourquoi); alors que pour la recherche d'un fichier dans une arborescence de répertoires, on utilisera plutôt G_LEVEL_ORDER.

L'ordre est important car, bien évidemment, seul le premier n ud correspondant est retourné.

Comme c'est le cas avec les autres types de structures, la Glib-2.0 permet d'appeler une fonction donnée pour chacun des enfants d'un n ud avec la fonction suivante:

Cette fonction sera appelée pour chacun des n uds enfants de noeud, suivant la règle imposée par type, avec comme premier paramètre un pointeur sur le n ud enfant et comme second paramètre le pointeur donnee_sup.

Mais g_node_children_foreach() n'est pas très puissante puisqu'elle ne concerne que la première génération en dessous d'un n ud (ce qui signifie qu'elle n'est pas récursive).

La fonction suivante est beaucoup plus générale puisqu'elle permet d'appeler une fonction pour chacun des n uds d'un arbre, suivant un ordre donné, en se limitant éventuellement à une profondeur donnée:

Les paramètres ordre et type ont le même sens que précédemment. La fonction fonction doit avoir le prototype suivant:

Si elle renvoie TRUE, le parcours des n uds s'arrête immédiatement, elle doit renvoyer FALSE sinon. Cela peut être utile si fonction est une fonction de recherche, qui doit s'arrêter à la première occurrence trouvée.

Le paramètre profondeur_max indique la profondeur maximale des appels. Par exemple, s'il vaut 1, fonction n'est appelée que pour la racine ; s'il vaut 2, fonction est appelée pour la racine et ses fils ; s'il vaut 3, fonction est appelée pour la racine, ses fils et ses petits-fils, etc. Si profondeur_max vaut -1, fonction est appelée sans limite de profondeur. 0 et les autres valeurs négatives ne doivent pas être utilisés.

Enfin, les deux fonctions suivantes permettent respectivement de séparer un n ud d'un arbre (ce qui revient en gros à remettre certains pointeurs à NULL, et de détruire complètement un arbre ou un sous-arbre:

L'exemple suivant utilise quelques-unes de ces fonctions pour afficher une arborescence de répertoires:

Vous pouvez également grandement l'améliorer, ne serait-ce qu'en libérant la mémoire qu'il utilise...

La prochaine fois, nous continuerons notre tour d'horizon des structures de données gérées par la Glib-2.0.