Fonction de recherche arborescente récursive JavaScript ne détectant pas les enfants imbriqués

Question

Essayer de créer une fonction récursive qui recherche correctement la classe Tree et tous ses descendants pour une valeur et renvoie true si cette valeur est trouvée, false sinon.

La fonction contains() récursive est particulièrement importante. Essayer d'obtenir le code pour passer le linter. Je reçois seulement une erreur de ne pas détecter les enfants imbriqués. Tout le reste passe.

Mon code:

/* eslint-disable no-trailing-spaces */ 
/* eslint-disable no-unused-vars */ 
class Tree { 
    constructor(value) { 
    this.value = value; 
    this.children = []; 
    } 
    // Adds a new Tree node with the input value to the current Tree node 
    addChild(value) { 
    this.children.push(new Tree(value)); 
    } 
    // Checks this node's children to see if any of them matches the given value 
    // Continues recursively until the value has been found or all of the children 
    // have been checked 
    contains(value) { 
    const thisNode = this; 
    function checkNode(node) { 
     if (node.value === value) { 
     return true; 
     } 
     if (node.children.length > 0) { 
     for (let i = 0; i < node.children.length; i++) { 
      return checkNode(node.children[i]); 
     } 
     } 
     return false; 
    } 
    return checkNode(thisNode); 
    } 
} 

module.exports = Tree; 

Voici le fichier qui le teste:

/* eslint-disable no-undef */ 
const Tree = require('../src/tree'); 

describe('Tree',() => { 
    let tree; 

    beforeEach(() => { 
    tree = new Tree(true); 
    }); 

    it('should have methods named "addChild" and "contains"',() => { 
    expect(typeof tree.addChild).toBe('function'); 
    expect(typeof tree.contains).toBe('function'); 
    }); 

    it('should add children to the tree',() => { 
    tree.addChild(5); 
    expect(tree.children[0].value).toBe(5); 
    }); 

    it('should return true for a value that the tree contains',() => { 
    tree.addChild(5); 
    expect(tree.contains(5)).toBe(true); 
    }); 

    it('should return false for a value that was not added',() => { 
    tree.addChild(5); 
    expect(tree.contains(6)).toBe(false); 
    }); 

    it('should be able to add children to a tree\'s child',() => { 
    tree.addChild(5); 
    tree.children[0].addChild(6); 
    expect(tree.children[0].children[0].value).toBe(6); 
    }); 

    it('should correctly detect nested children',() => { 
    tree.addChild(5); 
    tree.addChild(6); 
    tree.children[0].addChild(7); 
    tree.children[1].addChild(8); 
    expect(tree.contains(7)).toBe(true); 
    expect(tree.contains(8)).toBe(true); 
    }); 
}); 

Et voici l'erreur de peluchage:

Tree 
    ✓ should have methods named "addChild" and "contains" (5ms) 
    ✓ should add children to the tree (1ms) 
    ✓ should return true for a value that the tree contains (3ms) 
    ✓ should return false for a value that was not added (1ms) 
    ✓ should be able to add children to a tree's child (1ms) 
    ✕ should correctly detect nested children (9ms) 

Answer 1

Vous revenez sans conditions à l'intérieur du lucratif boucle, de sorte que vous ne vérifiez que le premier enfant.

for (let i = 0; i < node.children.length; i++) { 
     return checkNode(node.children[i]); 
    } 

Devrait être

for (let i = 0; i < node.children.length; i++) { 
     if (checkNode(node.children[i])) return true; 
    } 

Answer 2

Je pense, c'est ce que votre code devrait ressembler à:

for (let childIndex = 0; childIndex < node.children.length; childIndex++) { 
    const foundInChildren = checkNode(node.children[childIndex]); 
    if (foundInChildren) 
    return true; 
} 

Answer 3

Votre problème est dans ce morceau de code ici:

if (node.children.length > 0) { 
    for (let i = 0; i < node.children.length; i++) { 
     return checkNode(node.children[i]); 
    } 
    } 

Cette ligne de code reviendra de la fonction quel que soit le résultat de checkNode est pour le premier enfant, vrai ou faux. Si le résultat est faux, vous devez continuer à vérifier.

Essayez ceci:

if (node.children.length > 0) { 
    for (let i = 0; i < node.children.length; i++) { 
     if (checkNode(node.children[i])) { 
     return true; 
     } 
    } 
    }