INFORMATIQUE 'LES ARBRES'

UNE INTRODUCTION

Les structures arborescentes

Un arbre est un ensemble d’éléments appelés nœuds ou sommets organisés de manière hiérarchique à partir d’un nœud distingué appelé racine. On repère les nœuds de l’arbre en leur donnant des noms différents.

Arbres binaires

Un arbre binaire est soit vide, noté Ø, soit de la forme < r, B₁, B₂ > où r est la racine et où B₁ et B₂ sont des arbres binaires.

On définit intuitivement les notions de sous-arbre, de sous-arbre gauche, de fils gauche, de lien gauche et réciproquement à droite. On définit encore les notions de père, de frère, d’ascendant et de descendant. Les nœuds d’un arbre binaire ont au plus deux fils. Un nœud interne ou double a 2 fils. Un point simple à gauche a seulement un fils à gauche, et réciproquement à droite. Un nœud externe ou feuille n’a pas de fils. De façon généralisé, on qualifie de nœud interne, tout nœud qui n’est pas externe. On appelle les branches de l’arbre tout chemin (suite consécutive de nœuds) allant de la racine à une feuille. Il y a autant de branches que de feuilles. Le bord gauche est le chemin issu de la racine en suivant les liens gauches, et réciproquement à droite.

 Les caractéristiques d’un arbre sont :

-          la taille de l’arbre est le nombre total de nœuds.

-          la hauteur ou niveau d’un nœud x est le nombre de lien sur l’unique chemin allant de la racine à x, notée h(x).

-          la hauteur ou profondeur de l’arbre A, .

-          la longueur de cheminement de l’arbre A,   avec LCE la longueur de cheminement extérieure  et LCI la longueur de cheminement intérieure .

-          la profondeur moyenne externe de A est .

 On donne la signature du type abstrait arbre binaire :

                sorte arbre

                utilise nœud

                opérations

                                Ø : à arbre

                                < – , – , – > : nœud x arbre x arbre à arbre

                                racine : arbre à nœud

                                gauche : arbre à arbre

                                droit : arbre à arbre.

 Proposition : Soit un arbre binaire de taille n, de profondeur p et possédant f  feuilles. Si on examine les cas extrêmes, on obtient que  ; par ailleurs  d’où .

 Représentation des arbres en machines : On utilise la structure récursive des arbres.

1)       Dans cette première représentation, le chaînage est symbolisé par des pointeurs.

type arbre = adresse de nœud ;

type nœud =                 structure

                        val : élément ;

                        g, d : arbre ;

                        fin ;

 L’arbre est déterminé par l’adresse de la racine. On gère la mémoire dynamiquement pour les opérations de suppression / insertion.

1) Dans la représentation contiguë, on simule les chaînages par des indices dans un tableau.

 type arbre = tableau de 1 à N de

                                        structure

                                        val : élément ;

                                        g, d : entier ;

                                        fin ;

 On utilise l’indice 0 pour indiquer qu’il n’y a pas de fils. L’arbre est déterminé par une variable entière contenant l’indice de la racine. On va gérer les cases libres pour des insertions / suppressions. On chaîne les cases libres comme une pile, en utilisant le chaînage g et on utilise une variable entière libre pour indiquer l’indice du « sommet de pile ».

Arbres binaires complets

Un arbre binaire est complet si tous les nœuds qui ne sont pas des feuilles ont 2 fils.

Propositions : Un arbre binaire complet ayant n nœuds internes possède en tout n+1 feuilles. La démonstration se fait simplement par récurrence. Par ailleurs, on montre qu’il existe une bijection entre l’ensemble des arbres binaires de tailles n, B_n, et l’ensemble des arbres binaires complets de taille 2n+1, BC_2n+1. Principe : on ajoute des feuilles de sorte que tout nœudde l’arbre ait deux fils. De plus on établit que .

Arbres binaires parfaits, ordre hiérarchiqueOn dit qu’un arbre binaire est parfait si toutes ses feuilles sont situées sur les deux derniers niveau, l’avant dernier étant complet, et les feuilles du dernier sont le plus à gauche possible. Attention ! un arbre binaire parfait n’est pas forcément complet, mais il a toujours au plus un nœud simple (le père de la feuille la plus à droite).On peut représenter un arbre binaire parfait de taille n de manière compacte par un tableau à n cases. Ceci se fait en numérotant les nœuds de 1 à n en partant de la racine, niveau par niveau de gauche à droite (ordre hiérarchique). On a les relation générales suivantes :

-          le père du nœud d’indice i est à l’indice i / 2 (division entière) ;

-          le fils gauche d’un nœud i est, s’il existe, à l’indice 2i ;

-          le fils droit d’un nœud i est, s’il existe, à l’indice 2i+1 ;

-          les feuilles sont aux indices > n / 2.

 Parcours en profondeur d’un arbre binaire

On considère l’opération de parcours qui consiste à examiner systématiquement dans un certain ordre tous les nœuds de l’arbres pour effectuer un traitement de données.  Le parcours en profondeur à gauche consiste à partir de la racine et à tourner autour de l’arbre en allant toujours le plus à gauche possible.

 Procédure Parcours(A : arbre) ;

                début

                Si A = Ø

Alors T₀

                                Sinon

                                début

                                                T₁ ;