STRUCTURES ARBORESCENTES

STRUCTURES ARBORESCENTES

ARBRES BINAIRES

Examinons tout d’abord quelques exemples simples représentés par des arbres binaires : Figure 4.1 Les résultats d’un tournoi de tennis : au premier tour Jean a battu Jules, Marc a battu François, Paul a battu Yves, et Luc a battu Pierre ; au deuxième tour Jean a battu Marc, et Paul a battu Luc ; et Jean a gagné en finale contre Paul. Figure 4.2 Le pedigree d’un cheval Zoe ; son père est Tonnerre et sa mère est Belle ; la mère de Belle est Rose et le père de Belle est Éclair…  • Structures arborescentes Figure 4.3 Une expression arithmétique dans laquelle tous les opérateurs sont binaires… 4 + 5 * 8 La structure d’arbre binaire est utilisée dans très nombreuses applications informatiques ; de plus les arbres binaires permettent de représenter les arbres plus généraux. 4.1.1 Définition Le vocabulaire concernant les arbres informatiques est souvent emprunté à la botanique ou à la généalogie ; étant donné un arbre B = : • ’o’ est la racine de B. • B1 est le sous-arbre gauche (sag) de la racine de B, (ou, plus simplement, le sous-arbre gauche de B), et B2 est son sous-arbre droit (sad). • On dit que C est un sous-arbre de B si, et seulement si : C = B, ou C = B1, ou C = B2, ou C est un sous-arbre de B1 ou de B2. • On appelle fils gauche (respectivement fils droit) d’un nœud la racine de son sous-arbre gauche (respectivement sous-arbre droit), et l’on dit qu’il y a un lien gauche (respectivement droit) entre la racine et son fils gauche (respectivement fils droit). • Si un nœud ni a pour fils gauche (respectivement droit) un nœud nj , on dit que ni est le père de nj (chaque nœud n’a qu’un seul père). • Deux nœuds qui ont le même père sont dits frères. • Le nœud ni est un ascendant ou un ancêtre du nœud nj si, et seulement si, ni est le père de nj , ou un ascendant du père de nj ; ni est un descendant de nj si, et seulement si ni est fils de nj , ou ni est un descendant d’un fils de nj . Tous les nœuds d’un arbre binaire ont au plus deux fils : • un nœud qui a deux fils est appelé nœud interne ou point double • un nœud sans fils est appelé nœud externe ou feuille. Donc, un arbre binaire est : • soit vide ; • soit constitué d’un élément de type T et d’au plus deux arbres binaires.

Représentation

La représentation la plus naturelle reproduit la définition récursive des arbres binaires. Elle peut être réalisée en allouant la mémoire soit de façon chaînée soit de façon contiguë.

Arbres binaires

La représentation classique d’un arbre est dynamique. À chaque nœud on associe deux pointeurs, l’un vers le sous-arbre gauche, l’autre vers le sousarbre droit, et l’arbre est déterminé par l’adresse de sa racine. Lorsque l’arbre est étiqueté, on représente dans un champ supplémentaire l’information contenue dans le nœud. Implantation en C typedef struct arbre { T info; struct arbre *sag, *sad; } arbre; typedef arbre *ptr_arbre; Si a est un pointeur sur la racine de l’arbre, alors a = NULL correspond à un arbre vide ; a->sag pointe sur le fils gauche de a ; a->sad pointe sur le fils droit de a ; a->info permet d’accéder au contenu du nœud. On ne parle d’arbres binaires que par l’intermédiaire des algorithmes qui utilisent le type arbre.

Algorithmes de parcours d’un arbre binaire

Il y a deux types de parcours : • Parcours en profondeur d’abord – Examiner complètement un chemin et passer au chemin suivant tant qu’il en reste. Figure 4.4 Parcours en profondeur (à l’aide d’une pile) • Parcours en largeur d’abord – Examiner tout un niveau (profondeur hiérarchique) passant au niveau du dessous tant qu’il en reste. Problème : pas de lien entre fils. Cela doit être traité itérativement. 129 Chapitre 4 • Structures arborescentes Figure 4.5 Parcours en largeur (à l’aide d’une file) Parcours en profondeur d’abord Pré-ordre Principe Si arbre non vide alors : traiter la racine parcourir en Pré-ordre le sag parcourir en Pré-ordre le sad Algorithme en pseudo C Donnée : ptr_arbre p FONCTION préordre(a : ptr_arbre) DEBUT SI a 6= NULL ALORS afficher(a→info) préordre(a→sag) préordre(a→sad) FINSI FIN