Arbres:structures hiérarchiques.Arbres binaires:nœuds, racines, feuilles, sous-arbres gauches, sous-arbres droits

Structures de données

Plan

Arbres: définition

Essayons de donner une définition simple d'un arbre. Un arbre est constitué de sommets, que l'on appelle noeuds (ou vertex), et d'arêtes qui relient les sommets entre eux. Ces arêtes sont appelées branches ou arêtes. Pour avoir un arbre il faut que tous les noeuds soient reliés à un ou deux autres sommets et qu'il n'y ait qu'un seul chemin possible d'un noeud à un autre (il n'y a pas de cycle, c'est à dire, on ne peut pas tourner en rond).

Lorsqu'un arbre a un noeud de départ, duquel partent les premières branches, ce noeud s'appelle la racine de l'arbre.. Par la suite nous ne parlerons que d'arbres avec racine.

Si l'on représente l'arbre avec la racine en haut, et en faisant des branches qui descendent, les noeuds issues d'un noeud immédiatement au dessus, s'appellent les fils et le noeud source s'appelle le père (ou fils=enfants=descendants, père=parents). Des noeuds qui ont le même père sont dits frères.

Le nombre de chemins connectés à un noeud s'appelle le degré. Comme dans un arbre il n'y a qu'un seul parent par noeud (sauf pour la racine), degré-1 donne le nombre de fils.

Les noeuds qui ne sont reliés qu'à un seul noeud sont appelés les feuilles (ce sont des noeuds de degré 1, ils n'ont pas de fils). Lorsqu'on représente un arbre verticalement avec la racine en haut, les feuilles sont tout en bas...il suffit de retourner l'arbre pour avoir une analogie parfaite avec les arbres de la nature.

On peut nommer les noeuds. Ces noms sont appelés etiquettes. Lorsque tous les noeuds ont une étiquette, on dit que le graphe est étiqueté. L'étiquette peut indiquer le nom du noeud mais cela peut aussi être une valeur qui donne des informations sur le noeud.

LA taille est le nombre de noeuds

La profondeur ou hauteur d'un arbre est le nombre de branches que contient le chemin le plus long de l'arbre en partant de la racine et en descendant. C'est la distance entre la racine et le noeud. C'est le rang du dernier niveau de l'arbre, la racine étant le niveau 0, ces enfants au niveau 1, etc...

On parle aussi de la profondeur d'un noeud, c'est comme ci-dessus, le niveau où se trouve le noeud (autre façon de le voir , c'est le nombre de branches à utiliser en partant de la racine et en descendant).

On appelle chemin d'un noeud, la suite de noeuds par lesquels il faut passer en partant de la racine.

Arbres binaires

Avec le vocabulaire précédent, il est facile de définir un arbre binaire: c'est un arbre avec une racine, dont le degré maximum de chaque noeud est 3. En d'autres termes, chaque noeud a au plus deux fils: le fils gauche et le fils droit.

Voici un arbre de taille 7 (il a 7 neouds). 'feuille1' et 'père de feuille2' sont frères. La distance de 'Fils gauche de racine' à 'Feuille2' est de 2 et le chemin est {'Fils Gauche de racine','Père de feuille2', 'Feuille2'}.

Un arbre binaire strict est un arbre dont tous les noeuds ont soit zéro soit deux fils. Dessinez un arbre binaire strict.

Un arbre binaire parfait, est un arbre dont toutes les feuilles sont à la même profondeur. Dessinez un arbre parfait de profondeur 2.

Dessinez un arbre qui soit ni parfait ni strict.

L'arbre binaire de recherche. La particularité de cet arbre binaire est d'avoir des étiquettes qui sont des nombres entiers appelés clés tels que le fils gauche soit plus petit que le père qui est lui même plus petit que le fils gauche. En regardant l'arbre de gauche à droite on lit une suite de nombres strictement croissante. Un arbre binaire de recherche permet des opérations rapides pour rechercher une clé, insérer ou supprimer une clé.

Dessinez un arbre binaire de recherche de hauteur 3, de taille 9 dont la racine a pour clé 20.

Arbres binaires: sous-arbres gauches, sous-arbres droits

Imaginez que vous preniez un noeud quelconque avec tous ses descendants, vous obtenez un sous arbre. L'arbre à partir du fils gauche est le sous arbre gauche et l'arbre à partir du fils droit est le sous arbre droit.

Exercices

  1. blabla
  2. blabla

Android

De la programmation pour pc à la programmation pour téléphone.

A finir

Pas eu le temps de tout faire.....