JavaScript - Comment puis-je retourner la branche d'un arbre dans une recherche de noeud?

Question

Ma structure de données ressemblera à ceci:

var tree = [ 
    { 
     id: 1, 
     children: [] 
    }, { 
     id: 2, 
     children: [ 
      { 
       id: 3, 
       children: [] 
      } 
     ] 
    } 
]; 

Il peut y avoir un certain nombre de nœuds ou d'enfants sur une branche.

Mon but est de commencer par le nœud supérieur (racine), de rechercher un nœud donné et de retourner la branche sur laquelle il se trouve.

Ainsi, dans l'exemple de Plunker: https://plnkr.co/edit/PyR3H7mM0vrFyno1l7R5?p=catalogue

Je veux rechercher l'identifiant de noeud # 31, de sorte que l'algorithme retourne le tableau (branche) que 31 est une partie.

J'ai démarré l'algorithme mais si je le fais de façon récursive, je ne sais pas comment revenir en arrière.

function traverse(branch) { 

    for (var i = 0; i < branch.length; i++) { 
    if (branch[i].id == node.id) { 
     return branch; 
    } 
    } 

    for (var j = 0; j < branch.length; j++) { 
    if (branch[j].children.length > 0) { 
     return traverse(branch[j].children); 
    } 
    } 

} 

console.log(traverse(tree)); 

Par exemple, si je regarde vers le bas au dernier nœud enfant sans trouver un match alors je dois revenir en arrière à la branche mère d'essayer la prochaine série d'options.

Comment puis-je modifier mon algorithme pour revenir en arrière?

Answer 1

Votre algorithme est très proche, il vous suffit d'ajouter une déclaration if afin qu'elle ne retourne que le résultat récurrent de traverse si une correspondance a été trouvée:

function traverse(branch) { 

    for (var i = 0; i < branch.length; i++) { 
    if (branch[i].id == node.id) { 
     return branch; 
    } 
    } 

    for (var j = 0; j < branch.length; j++) { 
    var result = traverse(branch[j].children); 
    if (result !== undefined) { 
     return result; 
    } 
    } 

    return undefined; // no match found 

} 

console.log(traverse(tree)); 

Answer 2

Vous pouvez utiliser une variable temporaire pour le résultat des enfants et quitter la boucle si la valeur est véridique.

function traverse(branch) { 
    var result; 
    for (var i = 0; i < branch.length; i++) { 
     if (branch[i].id === node.id) { 
      return branch; 
     } 
     if (branch[j].children.length > 0) { 
      result = traverse(branch[j].children); 
      if (result) { 
       return result; 
      } 
     } 
    } 
} 

Answer 3

Cela a fait l'affaire de retourner la branche plutôt que le nœud lui-même:

function traverse(branch) { 

     for (var i = 0; i < branch.length; i++) { 
      if (branch[i].id == node.id) { 
       return branch[i].children; 
      } 
     } 

     for (var j = 0; j < branch.length; j++) { 
      var result = traverse(branch[j].children); 
      if (result !== null) { 
       return result; 
      } 
     } 

     return null; // no match found 
    }