Introduction aux arbres.

bien utilisée donne de très bonnes performances. On la retrouvera donc dans les systèmes de bases de données ou bien encore dans l'organisation d'un système de fichiers d'un système d'exploitation.

-3Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

II - Définitions

Un arbre est une structure qui peut se définir de manière récursive : un arbre est un arbre qui possède des liens ou des pointeurs vers d'autres arbres. Cette définition plutôt étrange au premier abord résume bien la démarche qui sera utilisé pour réaliser cette structure de données. Toutefois, cette définition est un peu vague, et nous allons introduire de nouvelles définitions pour mieux caractériser et identifier les arbres.

II-A - Arbres enracinés

On distingue deux grands types d'arbres : les arbres enracinés et les arbres non enracinés. Le premier type d'arbre est celui qui nous intéressera le plus. Un arbre enraciné est un arbre hiérarchique dans lequel on peut établir des niveaux. Il ressemblera plus à un arbre généalogique tel qu'on le conçoit couramment. Voici un exemple d'arbre enraciné :

Exemple d'arbre enraciné. Le deuxième grand type d'arbre est un arbre non enraciné. Il n'y a pas de relation d'ordre ou de hiérarchie entre les éléments qui composent l'arbre. On peut passer d'un arbre non enraciné à un arbre enraciné. Il suffit de choisir un élément comme sommet de l'arbre et de l'organiser de façon à obtenir un arbre enraciné. Voici un exemple d'arbre non enraciné :

-4Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

Exemple d'arbre non enraciné Vous remarquerez qu'il y a équivalence entre les deux arbres précédents. En effet, en réorganisant l'arbre non enraciné, on peut obtenir strictement le même arbre que le premier. En revanche, ce n'est qu'un exemple d'arbre enraciné que l'on peut effectuer avec cet arbre non enraciné, il en existera d'autres.

-5Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

Dans la suite, nous nous intéresserons uniquement aux arbres enracinés.

II-B - Terminologie

Précisons maintenant un peu plus les termes désignant les différents composant d'un arbre. Tout d'abord, chaque élément d'un arbre se nomme un noeud. Les noeuds sont reliés les uns aux autres par des relations d'ordre ou de hiérarchie. Ainsi on dira qu'un noeud possède un père, c'est à dire un noeud qui lui est supérieur dans cette hiérarchie. Il possède éventuellement un ou plusieurs fils. Il existe un noeud qui n'a pas de père, c'est donc la racine de l'arbre. Un noeud qui n'a pas de fils est appelé un feuille. Parfois on appelle une feuille un noeud externe tout autre noeud de l'arbre sera alors appelé un noeud interne. Voici donc un schéma qui résume les différents composant d'un arbre :

Description des différents composants d'un arbre

II-C - Arité d'un arbre

On a aussi envie de qualifier un arbre sur le nombre de fils qu'il possède. Ceci s'appelle l'arité de l'arbre. Un arbre dont les noeuds ne comporteront qu'au maximum n fils sera d'arrité n. On parlera alors d'arbre n-aire. Il existe un cas particulièrement utilisé : c'est l'arbre binaire. Dans un tel arbre, les noeuds ont au maximum 2 fils. On parlera alors de fils gauche et de fils droit pour les noeuds constituant ce type d'arbre. L'arité n'impose pas le nombre minimum de fils, il s'agit d'un maximum, ainsi un arbre d'arité 3 pourra avoir des noeuds qui ont 0,1,2 ou 3 fils, mais en tout cas pas plus. On appelle degré d'un noeud, le nombre de fils que possède ce noeud.

-6Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

La suite de cet article portera uniquement sur les arbres binaires puisque c'est le type d'arbre le plus basique à étudier mais aussi parce que tout ce que vous verrez sur un arbre binaire est valable pour un arbre n-aire. De plus il est possible de passer d'un arbre n-aire à un arbre binaire. Voici un exemple de passage d'un arbre généalogique (qui par définition n'est pas forcément binaire) à un arbre binaire. Voici donc l'arbre généalogique de base :

Arbre généalogique des Valois directs En remarquant qu'on peut mettre sur les fils gauche les enfants et sur les fils droit les frères et soeurs on en déduit donc que l'on peut construire un arbre binaire à partir de l'arbre n-aire. Voici donc l'arbre que nous obtenons :

-7Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

Arbre généalogique mis sous forme d'arbre binaire Comme vous pouvez le constater, il est assez difficile de lire ce genre d'arbre et généralement on remonte au même niveau les noeuds de la même génération. Ainsi un noeud n'a pas de fils gauche et de fils droit mais un fils et un frère. Voici à quoi peut ressembler l'arbre précédent dans ce cas:

-8Les sources présentés sur cette pages sont libres de droits, et vous pouvez les utiliser à votre convenance. Par contre la page de présentation de ces sources constitue une oeuvre intellectuelle protégée par les droits d'auteurs. Copyright © 2006 - Romuald Perrot. Aucune reproduction, même partielle, ne peut être faite de ce site et de l'ensemble de son contenu : textes, documents, images, etc sans l'autorisation expresse de l'auteur. Sinon vous encourez selon la loi jusqu'à 3 ans de prison et jusqu'à 300 000 E de dommages et intérêts.

http://rperrot.developpez.com/articles/algo/structures/arbres/

Introduction aux arbres. par Romuald Perrot

Arbre