Problème : Système de fichiers (Dos - Unix)

Dans l'arbre m-aire, un répertoire est décrit par son chemin. Un répertoire feuille est décrit par une branche. Exemples: /bd (chemin) est un répertoire, /bdf (branche) est un répertoire feuille.

On appelle épine droite d'un nœud d'adresse n (dans un arbre binaire) l'ensemble des nœuds formé du fg(n), fd(fg(n)), fd(fd(fg(n))), ....

Exemple : L'épine droite du nœud avec l'information '/' est l'ensembles des nœuds avec les informations 'a', 'b', 'x' et 'y'.

Construction :

(i) Ecrire le module Rech qui recherche un nœud avec l'information Nom dans l'épine droite d'un nœud d'adresse N.

(ii) Utiliser Rech pour écrire l'algorithme qui lit les répertoires branches (a) et qui construit directement l'arbre binaire (d)

Exploration de l'arbre binaire

(i) Donner les répertoires feuilles

(ii) Rechercher un répertoire donné

(iii) Déterminer le répertoire qui a le plus de répertoires fils.

Outils :

Le nom d'un répertoire est une chaîne de caractères commençant par le caractère '/'.

La lecture d'un répertoire se fait par lire(Rep), o� Rep est une chaîne.

Longchaine(Rep) donne la longueur de la chaîne Rep

Caract(Rep, i) donne le i-ème caractère de la chaîne Rep.

(a) Répertoires feuilles à créer (branches) : /a, /bc, /bdf, /bdg, /be, /x, /yu, /yz

( Un répertoire est identifié par une seule lettre alphabétique)

(b) Répertoires sous forme d'un arbre m-aire

 (c) Tous les répertoires possibles ( chemins ) : /, /a, /b, /bc, /bd, /bdf, /bdg, /be, /x, /y, /yu, /yz

(d) Répertoires sous forme d'un arbre binaire