Discussion :

[itokia]

Bonjour,

Je souhaiterai calculer la moyenne d'un noeud d'un arbre par ses feuilles enfants en récursif.
Je n'ai pas l'habitude de travailler en récursif et je sèche vraiment.

Mon tableau est de la forme ci-dessous :

T[0]['id']=>27
    ['libelle']=>Feuille 1
    ['valeur']=>?
    ['noeudEnfant']=>T[0]['id']=>26
            ['libelle']=>Feuille 1.1
            ['valeur']=>1
            ['noeudEnfant']=> null
        T[1]['id']=>25
            ['libelle']=>Feuille 1.2
            ['valeur']=>?
            ['noeudEnfant']=> T[0]['id']=>24
                    ['libelle']=>Feuille 1.2.1
                    ['valeur']=>4
                    ['noeudEnfant']=> null
                T[1]['id']=>23
                    ['libelle']=>Feuille 1.2.2
                    ['valeur']=>1
                    ['noeudEnfant']=>null
                T[...]...
T[...]...

Comment puis je procéder?

J'arrive bien à faire la somme pour un noeud mais je ne pense pas que cela soit optimisé et de plus c'est la moyenne qui m'interesse.
Fonction pour calculer la somme que j'ai crée :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function SommeNoeudsRecursif($tabGlobal){
    foreach($tabGlobal as $tab){
        $tab['valeur']=$this->SommeRecursif($tab);
    }
 
    return $tabGlobal;
}
 
function SommeRecursif($noeud){
    $somme=0;
    if(count($noeud['indicateurSuivant'])>0){
        foreach($noeud['indicateurSuivant'] as $enfant){
            if(count($enfant['indicateurSuivant'])>0){
                $somme += $this->SommeRecursif($enfant);
            } else {
                 $somme +=  $enfant['valeur'];
            }
        }
    } else {
         $somme +=  $noeud['valeur'];
    }
 
    return $somme;
}

Help please.

[Micmaya]

Bonjour,
Je ne connaissais pas cette notion d'arbre en programmation, bien que je l'ai déjà fait sur papier
Sinon, je peux te conseiller d'aller voir sur le site suivant: http://fr.wikipedia.org/wiki/Arbre_binaire pour savoir comment parcourir correctement un arbre "binaire".
ou encore: http://zanotti.univ-tln.fr/algo/PARCOURS-FIXE.html & http://recursivite.developpez.com/?page=page_8 (ce sont des algorithmes, reste à transformer cela en PHP)
Et pour calculer la moyenne je sais qu'il faut faire la somme divisé par le nombre de noeud. Maintenant, reste à savoir si tu veux calculer la moyenne de tout ton arbre ou bien de chaque noeud (premier noeud de l'arbre ou encore ceux qui contient plus 1 enfant).

Bien à toi,

[Spartacusply]

Voici un algorithme qui calcul récursivement la moyenne par parcours en profondeur pré-fixé (le noeud est traité avant les enfants). On recalcule à chaque fois la moyenne directement et on la passe en paramètre pour les noeuds enfants :

Code :

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

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
<?php
 
$array = array(
    array(
        'valeur' => 7,
        'noeudEnfant' => array(
            array('valeur' => 15),
            array('valeur' => 16),
        )
    ),
    array(
        'valeur' => 7,
        'noeudEnfant' => array(
            array(
                'valeur' => 15,
                'noeudEnfant' => array(
                    array('valeur' => 18)
                )
            ),
            array('valeur' => 16),
        )
    )
);
 
function moyenneRecursive($array, $moyenne = 0, $ponderation = 0) {
    foreach ($array as $key => $tab) {
        $moyenne = ($moyenne * $ponderation + $tab['valeur']) / ( ++$ponderation);
        if (isset($tab['noeudEnfant']) AND is_array($tab['noeudEnfant']) AND ! empty($tab['noeudEnfant'])) {
            $moyenne = moyenneRecursive($tab['noeudEnfant'], $moyenne, $ponderation);
        }
    }
    return $moyenne;
}
 
echo moyenneRecursive($array);

[Micmaya]

Merci "Spartacusply", j'avais oublié la pondération mais sinon cela me semble correcte Je n'avais simplement pas le temps de faire le test en PHP vu que je suis au boulot, hi!

[itokia]

Merci à vous deux, je regarde ca et vous tiens au courant.

[Spartacusply]

Une remarque: ma méthode précédente donne un résultat très approximatif, car elle arrondit à chaque tour de boucle la moyenne.

Voici un autre algorithme dans la même veine mais beaucoup plus précis : on calcul la somme total, et le nombre total d'élément, pour avoir une moyenne la plus juste possible :

Code :

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

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
<?php
 
$array = array(
    array(
        'valeur' => 7,
        'noeudEnfant' => array(
            array('valeur' => 15),
            array('valeur' => 16),
        )
    ),
    array(
        'valeur' => 7,
        'noeudEnfant' => array(
            array(
                'valeur' => 15,
                'noeudEnfant' => array(
                    array('valeur' => 18)
                )
            ),
            array('valeur' => 16),
        )
    )
);
 
function sumNoeud($array) {
    $sum = 0;
    $ponderation = 0;
    foreach ($array as $key => $tab) {
        $sum += $tab['valeur'];
        $ponderation++;
        if (isset($tab['noeudEnfant']) AND is_array($tab['noeudEnfant']) AND ! empty($tab['noeudEnfant'])) {
            $res = sumNoeud($tab['noeudEnfant']);
            $sum += $res['sum'];
            $ponderation += $res['ponderation'];
        }
    }
    return array('sum' => $sum, 'ponderation' => $ponderation);
}
 
function moyenneRecursive($array, $sum = 0, $ponderation = 0) {
    $res = sumNoeud($array);
 
    return $res['sum'] / $res['ponderation'];
}
 
echo moyenneRecursive($array);

Je ne connaissais pas cette notion d'arbre en programmation, bien que je l'ai déjà fait sur papier

Et encore, en Php ce sont juste des tableaux ordonnés de telle manière qu'ils représentent un arbre. Dans d'autre langage (comme Java par exemple), il y a des structures spécifiques pour représenter des arbres qui possèdent des méthodes assez poussés sur ce type de structure.

pour savoir comment parcourir correctement un arbre "binaire".

Son arbre n'est pas binaire, car chaque noeud n'est pas limité à 2 fils maximums.

[itokia]

Bon j'en étais pas tres loin de cette solution.
Par contre ce que je souhaiterais faire c'est de renseigner chacun des noeuds avec la moyenne de ces enfants.
Donc au plus simple serait de partir du bas vers le haut.

Une idée?

En tout cas merci à vous.

[itokia]

Avec de la persévérance et votre aide je viens de finir.
Désormais je parcours chaque noeud et je renseigne leur valeur par la somme de celle de leurs enfants.
Par contre je ne sais pas si on peut ou non optimiser.

Qu'en pensez vous?

Code :

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

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
 
function SommeNoeudsRecursif($tabGlobal){
    foreach($tabGlobal as $key => $tab){
        $nbEnfants=count($tab['indicateurSuivant']);
        $noeud=$this->SommeRecursif($tab,$nbEnfants);
        $tabGlobal[$key]=$noeud;
    }
    return $tabGlobal;
}
 
function SommeRecursif($noeud,$nbEnfants){
    if(count($noeud['indicateurSuivant'])>0){
        foreach($noeud['indicateurSuivant'] as $key => $enfant){
            $nbEnfants=count($enfant['indicateurSuivant']);
            if($nbEnfants>0){
                $enfant['valeur'] = ($enfant['valeur'] + $this->SommeRecursif($enfant,$nbEnfants)['valeur']) / $nbEnfants;
                $noeud['indicateurSuivant'][$key]= $enfant;
                $noeud['valeur'] = ($noeud['valeur'] + $enfant['valeur']) / count($noeud['indicateurSuivant']);
            } else {
                   $noeud['valeur'] = $noeud['valeur'] + $enfant['valeur'];
            }
        }
    }
 
    return $noeud;
}