Admin CliCours
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
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.
Arbres binaires parfaits, ordre hiérarchique
On 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.
Arbres généraux
Un arbre général, ou simplement arbre, est une structure arborescente où le nombre de fils n’est plus limité à 2.
Un arbre A = < r, A1, A2, …, An > est la donnée d’une racine r et d’une suite éventuellement vide de sous-arbres disjoints. Cette suite est une forêt. Un arbre est obtenu en rajoutant un nœud racine à la forêt.
…….
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)Cours algorithmes et structures de donnés arborescentes (764 KO) (Cours DOC)
