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 :

• un seul sommet n'a aucun parent, on l'appellera la racine ;
• tous les autres sommets n'ont qu'un seul parent.

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

• les feuilles sont les nœuds ne possédant pas de fils ;
• les nœuds internes sont les nœuds possédant des fils.

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 :

• la profondeur d'un nœud est la distance (nombre d'arêtes) entre la racine et ce nœud ;
• la hauteur d'un arbre est la plus grande profondeur d'une feuille de l'arbre ;
• la taille d'un arbre est le nombre de nœuds.

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 :

• Quelle est la racine ?
• Combien a-t-il de feuilles ?
• Qui sont les fils de D ?
• Quelle est la profondeur de H ?
• Quelle est la profondeur de P ?
• Quelle est la hauteur de cet arbre ?
• Quelle est la taille de cet arbre ?

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

• Quelle est la racine ?
• Combien a-t-il de feuilles ?
• Quelle est la profondeur de index.html ?
• Quelle est la profondeur de administrateur ?
• Quelle est la hauteur de cet arbre ?
• Quelle est la taille de cet arbre ?

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