Structures de données arborescentes (Les Arbres)

Définition
Types de parcours
Primitives des Arbres binaires
Implémentation chainée
Implémentation contiguë

Exemples d’utilisation

Une variable structure peut etre représentée sous forme d’un arbre. Par exemple la variable structure Etudiant (de type Type Etudiant) suivante peut etre represente e par l’arborescence suivante :

Exemples d’utilisation

n Quelques types de donne es en Java
Type primitif
boolean
Type nume rique
Type entier
long
int
Type a vigule flottante
float
double

Introduction

Les arbres sont des structures de donne es non lineaires : structures arborescentes
Les arbres mode lisent une relation hierarchique dans laquelle tous les e le ments peuvent avoir ze ro ou plusieurs successeurs et un pre de cesseur unique sauf la racine En d…autres termes !
Un arbre est forme d’un ensemble de nêuds, relie s par des aretes entre deux noeuds il existe au plus un et un seul chemin
Un arbre organise de hierarchique: c«est un graphe connexe sans cycle (acyclique)

Terminologie (1)

Un pere (parent) est le pre de cesseur direct d«un
… ud. Exemple TM est le pœ re de T1, T2 et T3
Un fils (enfant) est un successeur direct
… ud. Exemple T1, T2 et T3 sont les trois fils de TM
Un frére dun n… ud est le fils d«un meme pœ re.

Exemple T2 est un frœ re d T1.

Une feuille est un n… ud sans fils. Exemple T1,T211, T212, T31 et T32 sont des feuilles.
Le degre d(un nêud correspond a son nombre de fils. Exemple le degre de TM est 3.
Le niveau de la racine est 0, si un n… ud est au niveau n, son successeur est au niveau n+1.

Exemple le niveau de T1 est 1.

Une generation repre sente les n… uds d’un meme niveau. Exemple T21, T22, T23, T31, T32 sont de la meme generation
Deux n… uds sont adjacents si l«un est le pre de l«autre. Exemple TM et T1 sont adjacents.

Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Structures de données arborescentes (Les Arbres) (890 Ko) (Cours PDF)