试图制作一个递归函数,该函数能够正确搜索树类及其所有后代的值,并在找到该值时返回true,否则返回false。JavaScript递归树搜索函数未检测到嵌套子代
特别重要的是递归contains()函数。试图让代码通过linter。我只有一个关于未检测到嵌套的孩子的错误。其他一切都在流逝。
我的代码:
/* 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;
下面是测试中,它的文件:
/* 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);
});
});
这里是掉毛的错误:
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)
您是直接从''的循环for'身体return'ing。这意味着只执行循环的第一次迭代。你究竟想要做什么?你真的想要返回检查第一个孩子的结果吗?在编写代码之前尝试描述你想要做什么。 –
有答案你的代码有什么问题。这里有一种方法可以缩短/改善它:'const checkNode = node => node.value === value || node.children.some(checkNode);'然后'返回checkNode(this);' – Thomas
@FelixKling我刚刚编辑我的描述为'尝试做一个递归函数,正确搜索Tree类及其所有后代的值如果找到该值,则返回true,否则返回false。'这对你来说足够描述了吗?如果堆栈溢出对新手来说更加温和一点,对所有人来说都会更有利可图。结束。 –