Discussion :

[julien9662]

Bonjour à toutes et à tous,
Je suis débutant en Javascript et j'ai un gros problème avec la récursivité. J'ai passer la journée à chercher une solution en vain, c'est pourquoi je m'en remet à vous.
Mon problème est celui-ci :

J'ai un tableau organisé de manière hiérarchique dont je ne connais pas à l'avance les valeurs, voici un exemple :

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
 
  var tree = [
    { name : "body", 
      relation : "INCLUSION",
      sons :
      [
        {
          name : "header", 
          relation : "INCLUSION",
          sons :
          [
            { name : "logo", relation : "INCLUSION", sons : [] }
          ]
        },
        {
          name : "footer", relation : "INCLUSION", sons : []
        }
      ]
    }
  ];

Mon objectif est de construire une fonction récursive qui prend en paramètre "tree" et un "name" et qui ressort un tableau contenant la liste des parents dans l'ordre depuis le "name".
Voici un exemple du comportement attendu :

Code :

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

1
2
3
 
var parents_list = browseTree (tree,"logo"); 
// parents_list = [ "header", "body" ];

Je vous avoue que je désespère d'y arriver. J'ai beau comprendre les retours que j'ai quand je fait des tests de fonction récursive, impossible de trouver la solution à mon problème..
Merci d'avance.

[danielhagnoul]

var parents_list = browseTree( tree, "logo" ); ?

[julien9662]

Désolé pour le manque de précision.
BrowseTree() est la fonction que je cherche à concevoir.
J'ai mis cette ligne pour illustrer le comportement que je cherche à obtenir. C'est à dire qu'à partir de l'arbre et d'un nom - d'où les paramètres `tree` et `"logo"` - la fonction retourne la liste des parents de "logo". Dans l'exemple que j'ai donné, ses parents sont "header" et "body".
J’espère avoir été plus clair.

[Watilin]

Salut !

Si j’ai bien compris tu as toujours une structure comme ceci :

Code :

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

1
2
3
4
5
6
7
8
[
  {
    name : …
    relation : …
    sons : []
  },
  …
]

autrement dit un tableau d’objets littéraux, et dans ces objets littéraux toujours les trois propriétés name, relation et sons, avec sons pointant sur un sous-arbre structuré de la même manière.

Ainsi tu sais déjà que ton appel récursif devra recevoir tree.sons en paramètre.

Code :

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

1
2
3
4
5
6
function browseTree(tree, name) {
  'use strict';
  …
  … browseTree(tree.sons, name) …
  …
}

Tu as deux conditions d’arrêt :

• tree.name correspond à name ;
• tree.sons est vide.

La difficulté dans ton problème est qu’il y a potentiellement plusieurs branches à explorer pour trouver name. Il faut donc une boucle for pour itérer sur les différents objets de tree.sons. Je ne sais pas s’il faut considérer le cas où name n’est pas présent dans l’arbre, et le cas où il est présent plusieurs fois. Mettons ces cas de côté pour le moment.

Ta valeur de retour étant un tableau, a priori tu devras faire usage de push ou de concat. Selon ta condition d’arrêt, positive (tu as trouvé name) ou négative (sons est vide, autrement dit tu as atteint un cul-de-sac dans l’exploration de l’arbre), tu dois renvoyer un résultat différent. Je propose ceci :

• dans le cas positif, renvoie un tableau vide [] ;
• dans le cas négatif, renvoie false.

Dans l’appel récursif « précédent », ça te permet de distinguer si on peut terminer l’exploration et renvoyer un résultat, ou bien s’il faut continuer à chercher.

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
function browseTree(tree, name) {
  'use strict';
 
  for (var i = 0, l = tree.length; i < l; i++) {
    // conditions d’arrêt
    if (name === tree[i].name) return [];
    if (!tree[i].sons.length) return false;
 
    var result = browseTree(tree[i].sons, name);
 
    // si le niveau inférieur a renvoyé false,
    // poursuit l’exploration avec la branche suivante
    if (!result) continue;
 
    // si result existe, on l’enrichit avec le niveau actuel et on
    // le passe au niveau supérieur
    return [ tree[i].name ].concat(result);
  }
 
  // arrivé ici, si aucun return n’a été pris c’est que l’exploration
  // s’est terminée sans que name ait été trouvé
  // TODO (ou pas)
}

Voilà l’idée générale, je n’ai pas testé. J’espère que c’est assez clair, et que je n’ai rien oublié d’important

[julien9662]

Ca répond exactement à mon problème, merci beaucoup !