culcul des noeuds d'un arbre

Présentation


J'ai développé une procédure qui calcule valeurs des nœuds d'un arbre donné.
La procédure base sur l'idée de récursivité, c’est vraiment un casse tête pour l’implémenter.
Donc, j'ai pensé à modéliser mon idée sous un SQL/Oracle en mettant la requête générique valable pour n'importe quel arbre .
L'arbre doit être introduit dans une table. cette dernière comporte 03 champs: pere, fils et valeur.

[b]Exemples:[/b]
Les noeuds sont presentés comme suite dans la table:

pere | fils | valeur
A | B | null

Les feuilles sont présentés comme suite dans la table:
pere | fils | valeur
B | null| 3

REQUETE est sur le lien de téléchargement.
Détails
Avatar de islamov islamov
Membre expérimenté
Voir tous les téléchargements de l'auteur
Licence : Autre
Date de mise en ligne : 16 mai 2017




Avatar de JeitEmgie JeitEmgie - Membre expert https://www.developpez.com
le 01/06/2018 à 7:30
http://sqlfiddle.com/#!4/1210c6/74

Code : Sélectionner tout
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
with tab as 
( 
 select 'A' pere, 'B' fils, null valeur from dual union
 select 'A', 'C', null from dual union
select 'B', 'D', null from dual union
select 'B', 'E', null from dual union
select 'D', 'H', null from dual union
select 'E', 'I', null from dual union
select 'E', 'J', null from dual union
select 'J', null, 8 from dual union
select 'I', null, 15 from dual union
select 'H', null, 32 from dual union
select 'C', 'F', null from dual union
select 'F', null, 7 from dual union
select 'C', 'G', null from dual union
select 'G', 'K', null from dual union
select 'G', 'L', null from dual union
select 'L', 'M', null from dual union
select 'K', null, 2 from dual union
select 'M', null, 22 from dual 
),
rec(lvl, path, root, pere, fils, valeur, is_leaf) as
(
  select level, sys_connect_by_path(pere,'/'), connect_by_root pere as root, pere, fils, nvl(valeur,0),
  connect_by_isleaf
  from tab
  start with pere in (
    select pere from tab t1 where
      not exists(select t2.fils from tab t2 where t2.fils = t1.pere)
   )
  connect by prior fils = pere
),
rec_dep as (
select distinct r1.path as path, r2.path as depending_on, r2.valeur, r2.is_leaf, r1.lvl from rec r1
  join rec r2 on instr(r2.path, r1.path, 1,1) > 0 and r1.path <> r2.path
),
results as (
select substr(path,instr(path,'/',-1)+1) as node, path, sum(valeur) as valeur
from rec_dep group by path
union
select substr(depending_on,instr(depending_on,'/',-1)+1), depending_on, valeur from rec_dep 
  where depending_on not in (select path from rec_dep) and is_leaf = 1
    and regexp_count(path,'/') = regexp_count(depending_on,'/')-1
)
select * from results order by node;

 
Developpez.com décline toute responsabilité quant à l'utilisation des différents éléments téléchargés.
Contacter le responsable de la rubrique Oracle