Structures de données

1 ) définition

Les arbres binaires sont des cas particuliers d'arbres : dans un arbre binaire, on a au maximum 2 branches qui partent d'un élément. Dans la suite de l’activité nous travaillerons uniquement sur les arbres binaires.


2 ) vocabulaire

Voici ce que dit wikipedia au sujet des arbres binaires :
En informatique, un arbre binaire est une structure de données qui peut se représenter sous la forme d'une hiérarchie dont chaque élément est appelé nœud, le nœud initial étant appelé racine. Dans un arbre binaire, chaque élément possède au plus deux éléments fils au niveau inférieur, habituellement appelés gauche et droit.
Du point de vue de ces éléments fils, l'élément dont ils sont issus au niveau supérieur est appelé père.
Au niveau le plus élevé, niveau 0, il y a un nœud racine. Au niveau directement inférieur, il y a au plus deux nœuds fils. En continuant à descendre aux niveaux inférieurs, on peut en avoir quatre, puis huit, seize, etc. c'est-à-dire la suite des puissances de deux. Un nœud n'ayant aucun fils est appelé feuille.
Le niveau d'un nœud, autrement dit la distance entre ce nœud et la racine, est appelé profondeur. La hauteur de l'arbre est la profondeur maximale d'un nœud. Un arbre réduit à un seul nœud est de hauteur 1.
Les arbres binaires peuvent notamment être utilisés en tant qu'arbre binaire de recherche ou en tant que tas binaire.


Pour bien comprendre , voici des vidéos permettant de vous familiariser avec le vocabulaire et quelques types d'arbres.

* Commençons par une présentation vidéo des termes utilisés
* Ici un premier type de parcours de l'arbre Le parcours en profondeur
* Ici un second type de parcours de l'arbre Le parcours en largeur


Pour bien comprendre , voici un pdf permettant de vous familiariser avec le vocabulaire et quelques parcours d'arbres.