Practical Programming Courses(C)

Les Arbres

, Définition d’un arbre

◼ Un arbre est une structure de donnée hiérarchique,
composé de nœuds et de relations de précédence entre
ces nœuds
◼ Chaque nœud possède
➢ 0, 1, 2, ..., n successeur(s)

➢ un et un seul prédécesseur (sauf la racine qui en a
aucun)
◼ Un nœud ne peut pas être à la fois prédécesseur et
successeur d’un autre nœud

, Vocabulaire
◼ La racine est le nœud sans prédécesseur (point d’accès au
contenu de l’arbre)
◼ Une feuille est un nœud sans successeur
◼ Une branche est la suite des nœuds liant la racine à une feuille
◼ Un fils est un successeur d’un nœud
◼ Le père est le prédécesseur d’un nœud
◼ Le degré d’un nœud est le nombre de fils de ce nœud
◼ La profondeur d’un nœud est le nombre de prédécesseur entre
ce nœud et la racine
◼ La hauteur d’un arbre est la profondeur maximale de tous les
nœuds

, Exemple d’un arbre n-aire
◼ Racine (arbre) = Z

◼ Feuilles (arbre) = { L , S , C , B , G , I }
◼ Branche ( S )={ S , F , A , Z }
◼ Fils ( A )={ F , C , B }
◼ Père ( F )= A

◼ Degré ( A )=3
◼ Profondeur ( C )=2
◼ Hauteur (arbre) = 3