Discussion :

[arundel]

Bonjour à tous,

Je développe en Access VBA et je bute sur la difficulté algorithmique suivante. A partir d'une base de données je construis un arbre à l'aide de deux modules de classe:

Classe Sommet:

Code VBA :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Option Compare Database
Option Explicit
Option Base 1
 
Public lngIDSommet As Long
Public intRank As Integer
Public lngIDPere As Long, colFils As New Collection
 
Property Let SetColFils(objNode As Sommet)
 colFils.Add objNode
End Property
 
Private Sub Class_Terminate()
 Set colFils = Nothing
End Sub

Classe Graphe :

Code VBA :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
Option Compare Database
Option Explicit
Option Base 1
 
Public colSommet As New Collection
Public dicSommet As New Dictionary 'Collections des identifiants des sommets
 
Private Sub Class_Terminate()
 dicSommet.RemoveAll
 Set colSommet = Nothing: Set dicSommet = Nothing
End Sub

Comme j'ai par ailleurs une relation de chronologie entre les feuilles de l'arbre, j'ai un traitement qui numérote celles-ci. Je stocke ce numéro dans la variable intRank des sommets de type feuille.

Grâce à un parcours en largeur d'abord je peux numéroter les sommets de l'arbre de manière lexicographique (comme les n° de paragraphes en Word). Le pb c'est que je voudrais que cette numérotation respecte l'ordre des feuilles terminales comme le montrent les deux schémas suivants :



Bref cela revient à actualiser le n° lexicographique en fonction de l'ordre qu'on veut (comme dans le mode Plan de Word).

Si quelqu'un peut me suggérer une piste, cela me rendrait un grand service.

Merci d'avance pour votre aide.

[yahiko]

Je ne suis pas sûr d'avoir saisi ton besoin, mais il semble qu'il s'agit simplement d'inverser récursivement toutes les branches de ton arbre.
Ça peut se faire via ton parcours en largeur d'abord, par exemple.

[arundel]

Merci de t'intéresser à mon problème.

Il ne s'agit pas d'inverser l'ordre des feuilles (le schéma volontairement simplifié a pu le laisser croire), il s'agit de piloter la numérotation de tous les sommets de l'arbre en cohérence avec la chronologie des feuilles.

A mon sens le défaut de la récursivité c'est qu'il faut partir de la racine de l'arbre alors que les infos de base pour le tri sont aux extrémités.

[yahiko]

Dans ce cas, à vue de nez, je pense qu'il te faut des fonctions auxiliaires comme :

Hauteur(nœud) --> hauteur du nœud dans l'arbre
Frères(nœud) --> ensemble des nœuds ayant le même père
Père(nœud) --> père du nœud
Min(nœuds) --> nœud ayant l'ordre chronologique le plus faible parmi les autres nœuds

Par rapport à ton exemple avec trois niveaux, la numérotation de chaque feuille est de la forme x.y.z, sachant que le nombre d'indices pour un nœud quelconque est égal à sa hauteur dans l'arbre.

Il te faut donc déterminer la feuille F ayant l'ordre chronologique le plus petit.
Les indices x, y et z de F vaut donc 1 (1.1.1).
Cela implique que les frères de F ont les mêmes indices x et y qui valent 1 (1.1.z). Seul l'indice z change suivant leur ordre chronologique.
Tu peux aussi en déduire la numérotation de tous les ascendants (père, grand-père, etc) de F.

Une fois cela fait, tu peux t'attaquer aux cousins de F en remontant par le père de F puis les frères du père de F.
En appliquant la même logique pour chaque cousin de F que celle appliquée pour F, tu peux en déduire la numérotation de toutes les feuilles de F et par extension de tous les nœuds de ton arbre.

[arundel]

OK, je regarde ça de près et ferai un retour sur ce qu'il en est.
Merci et à bientôt.

[tbc92]

Reste un point qui n'est pas clairement décrit dans l'énoncé.

Dans ton illustration, les 2 fils de 1.2 sont D et E ; les 2 fils de 1.1 sont F et G ; il n'y a donc pas d'ambiguïté, 1.2 doit venir avant 1.1.

Maintenant, imaginons cette configuration :
1.2 a 2 fils : D et G ; 1.1 a 2 fils E et F
Qui doit venir en premier ?

On classe les individus selon l'âge des fils aînés ( D est plus âgé que F ... et donc 1.2 est avant 1.1)
Ou bien on classe les individus selon l'âge des fils cadets ( G est plus jeune que F, et donc 1.2 est après 1.1)

Il faudra arbitrer ce point avant de mettre en place la solution proposée par Yahiko.