Représentation d'un arbre binaire
Application des pointeurs
Par les listes chaînées, nous avons vu comment utiliser les pointeurs pour stocker des informations dans une structure qui s'apparente au tableau dans le sens où le parcours de ces données se fait de manière séquentielle. Nous avons introduit, dans la structure de données de la liste, un second pointeur pour introduire, dans la gestion de liste, le parcours en sens inverse.
De la même façon, nous pouvons ajouter des pointeurs dont la prise en compte modifie les caractéristiques de gestion de la structure globale.
Définition : Pointeur et arborescence
Le pointeur par son caractère directionnel est intégré naturellement dans la représentation d'une arborescence.
Lorsque l'arborescence possède la caractéristique d'avoir un nombre réduit d'arcs issus d'un sommet, la modélisation de ses composantes est aisée.
Ainsi, si le nombre d'arcs issus d'un sommet est :
1, nous retrouvons la liste chaînée simple,
2, nous sommes en présence d'une arborescence que l'on qualifie de binaire. On parle communément d'arbre binaire.
Similitude avec la liste chaînée
L'arbre, comme la liste chaînée, est une structure récursive. Chaque élément de l'arbre présente au minimum une donnée stockée et 2 liens permettant d'accéder aux sous-arbres binaires éventuels.
Syntaxe : Structure de données de base
La structure de données élémentaires de l'arbre sera une structure comprenant l'information stockée de type T et les liens vers les sous-arbres.
struct Snoeud{
T donnee;
struct Snoeud *fg ; // fils gauche
struct Snoeud *fd ; // fils droit
}
typedef struct Snoeud Tnoeud;
L'arbre sera représenté le plus simplement par un pointeur sur l'élément racine de l'arborescence.
// déclaration d'une variable arbreTnoeud ArbBin=NULL; // l'arbre est vide à la déclaration