Cours d'informatique pour le lycée

Arbres

Définition

En informatique nous parlerons d'un type de graphe particulier : les arbres enracinés ou arborescence. Par abus de language on ommettra souvent le terme « enraciné » et nous parlerons simplement d'arbre. En voici une définition :

Un arbre (enraciné) ou une arborescence est un graphe orienté dont :

Voici donc un arbre enraciné :

A est ici la racine.

Informatique

En informatique, nous simplifierons la représentation des arbres en ommettant les flèches et en mettant la racine en haut. Voici le même arbre simplifié :

Un arborescence est donc un arbre :

/
├── home
│	├── eleve
│	│	└── fichier.txt
│	└── administrateur
├── lost+found
├── media
└── var
	└── www
		└── index.html

Vocabulaire

Pour l'arbre ci-dessus, A est la racine, A, C et D sont des nœuds internes et B, E, F et G sont des feuilles.

Propriétés

Voici les principales propriétés d'un arbre :

Pour l'arbre ci-dessus, la profondeur de A est 0 et celle de E est 2. Sa hauteur est 2 et sa taille est 7.

11) Pour l'arbre ci-dessous, répondre aux questions suivantes :

12) Pour l'arborescence linux ci-dessous, répondre aux questions suivantes :

/
├── home
│	├── eleve
│	│	└── fichier.txt
│	└── administrateur
├── lost+found
├── media
└── var
	└── www
		└── index.html