递归遍历家谱时出现问题

Question

我有一个Person类，它具有以下属性：名称、出生和其他Person类数组形式的后代。

现在，我正在尝试实现一个函数，该函数可以从原始的Person类开始遍历这个家谱，并返回一个数组，该数组包含出生年份在1970年之后的所有Person类，但在实现递归方面非常困难。

我的问题是，在检查了家谱的第一层和第二层的出生日期后，我不知道如何在家谱的更深处递归。

只是想知道是否有人有什么线索。

class Person {
constructor(name, birth) {
this.name = name;
this.birth = birth;
this.desc = [];
}
adddesc(person) {
this.desc.push(person);
}
post1970() {
let res = [];
let birth = this.birth;
let descendants = this.desc;

if (birth > 1970) return this;
for (let i = 0; i < descendants.length; i++) {
let child = descendants[i];
let curr = child.post1970(); //What should I do after this line?
console.log(curr)
}
return res;
}
}
const original = new Person('root', 1900)
let desc1 = new Person("andrew", 1940);
let desc2 = new Person("sarah", 1960);
let desc3 = new Person("charlie", 1980);
let desc4 = new Person("david", 1990);
let desc5 = new Person("ethan", 2000);
original.adddesc(desc1); //Andrew + Charlie
original.adddesc(desc3);
desc1.adddesc(desc2); //Andrew: Sarah
desc3.adddesc(desc4); //Charlie: David
desc4.adddesc(desc5); //David: Ethan

original.post1970();

Answer 1

我有一些预先设计建议：

• post1970()过于刚性。年份应该是一个参数。否则，您必须重新编写整个函数，以便在1969年或任何其他年份进行筛选。像bornAfter(year)这样的约定是更好的方法，或者进一步推广，使其成为像filterDescendants(predicateFunction)这样的任意谓词
• 除非绝对必须使用let，否则应避免使用它。const使代码更安全、更具表现力。每当我看到let时，我就觉得程序员在试图告诉我"我打算重新分配这个变量"；。在大多数情况下，这只是转移注意力，包括这个——使用const。重新分配是一种支撑，往往会使代码难以遵循
• CCD_ 8让我思考"；描述"；。CCD_ 9更加清晰。我也会让它成为构造函数的数组；如果你也想要adder/setter/getters，那也可以，但不允许在一次拍摄中构建对象，并且必须将其存储在一个中间变量中以增量设置其属性，这有点尴尬
• 在Person类上具有这些面向树的过滤函数有点奇怪。您可能想要一个具有根Person的FamilyTree类。这使得代码读起来像FamilyTree.filterBy(e => e.birthDate > 1970)，而不是不那么直观的Person.filterDescendantsBy(e => e.birthDate > 1970)
• 如果你经常这样做非分层过滤，那么树数据结构可能是错误的选择。您可以有一个一次性构建的辅助阵列，也可以直接使用该阵列而不使用树。如果没有更多关于您的用例和数据集大小的信息，就不可能在这里提出建议，只需注意，在每次筛选操作中遍历整棵树会感觉很浪费——对于下面的代码，根本不需要树抽象；直接进入一个数组并过滤掉。我想您稍后会添加其他方法，这些方法在树上实际上是有意义的

无论如何，树到数组转换的核心是通用的descendantsToArray，它使用Array#flatMap递归地构建子数组，然后将它们展平为最终结果数组。一旦构建了整个树的结果数组，就可以使用Array#filter调用来获得所需的结果。最后，我使用了Array#map来简化输出，这样您就不会看到一堆嵌套的对象。

class Person {
constructor(name, birthDate, descendants=[]) {
this.name = name;
this.birthDate = birthDate;
this.descendants = descendants;
}

descendantsToArray() {
return [this].concat(
...this.descendants.flatMap(e => e.descendantsToArray())
);
}
filterDescendants(predicate) {
return this.descendantsToArray().filter(predicate);
}
}
const root = new Person(
"root",
1900,
[
new Person(
"andrew",
1940,
[new Person("sarah", 1960)]
),
new Person(
"charlie",
1980,
[
new Person(
"david",
1990,
[new Person("ethan", 1990)]
)
]
),
],
);
const peopleBornAfter1970 = root
.filterDescendants(e => e.birthDate > 1970)
.map(e => e.name)
;
console.log(peopleBornAfter1970);

如果效率是一个大问题，那么作为第二步的过滤有点浪费，所以你可以尝试生成器函数来注意空间。不过，整体递归模式是相同的。

Answer 2

几个注意事项：

首先，我同意ggorlen的前四点，部分同意第五点。这都是很好的建议，请考虑一下。

第二个，如果你正在寻找对现有代码的最小更改，它可能看起来像这样：

post1970() {
let res = [];
let birth = this.birth;
let descendants = this.desc;
// if (birth > 1970) return this; // No, we will need to return an array of people
if (birth > 1970) res .push (this)

for (let i = 0; i < descendants.length; i++) {
let child = descendants[i];
let curr = child.post1970(); // Q: What should I do after this line?
res = res .concat (curr)     // A: this!  :-)
// console.log(curr)
}
return res;
}

(但请注意，这立即拒绝了ggorlen的const-over-let建议，因为我们一路上重新分配了res。这也是我个人不喜欢这个代码的原因之一。)

第三，我同意ggorlen的目标，即使此代码更加灵活。在这里，我建议使用普通函数而不是类方法。这也可以继续使用普通对象，而不是整个树的类实例，但相同的代码都可以使用。以下是我的处理方法：

const treeFilter = (getChildren) => (pred) => (node) => [
... (pred (node) ? [node] : []),
... (getChildren (node) || []) .flatMap (treeFilter (getChildren) (pred))
]
const familyTreeFilter = treeFilter (n => n .desc)
const post1970 = familyTreeFilter (n => n .birth > 1970)
const original = {name: "root", birth: 1900, desc: [{name: "andrew", birth: 1940, desc: [{name: "sarah", birth: 1960, desc: []}]}, {name: "charlie", birth: 1980, desc: [{name: "david", birth: 1990, desc: [{name: "ethan", birth: 2000,desc: []}]}]}]}
console .log (
post1970 (original) /* for display --> */ .map (n => n .name)
)

我们从treeFilter开始，它采用了一个描述树结构的函数(这里我们的孩子在节点desc[是的，听起来像是"描述"而不是"后代"]，但可能有其他可能性，例如children。)这返回一个接受谓词的函数——为谓词提供一个值，它会报告我们是否要包含该值。它返回一个采用树的函数，并将树的匹配元素作为平面数组返回。

这个curried版本的优点是，我们可以在任何类似结构的树上重用我们的简单post1970。我们可以重用familyTreeFilter来为这样的descendant子结构创建其他过滤器。也许我们希望所有在2000年之前拥有birth的人，或者name以'c'开头的人，或至少有四个后代的人。用这种方式写每一个都是微不足道的。我们可以重用treeFilter来描述完全不同树结构上的过滤器，同样，使用琐碎的实现。

第四，如果这些抽象级别是压倒性的，那么很容易将它们组合起来，一个接一个地内联它们，以获得适合您用例的自定义函数。我很少觉得这是必要的，但我可能会在性能密集型代码块上这样做，或者如果我需要添加一些简短的函数(比如在Stack Overflow帖子上的评论)

const treeFilter = (getChildren) => (pred) => (node) => [
... (pred (node) ? [node] : []),
... (getChildren (node) || []) .flatMap (treeFilter (getChildren) (pred))
]
const familyTreeFilter = treeFilter (n => n .desc)
const post1970 = familyTreeFilter (n => n .birth > 1970)

和内联familyTreeFilter，将其转换为

const treeFilter = (getChildren) => (pred) => (node) => [
... (pred (node) ? [node] : []),
... (getChildren (node) || []) .flatMap (treeFilter (getChildren) (pred))
]
const post1970 = treeFilter (n => n .desc) (n => n .birth > 1970)

然后我们可以内联treeFilter以获得

const post1970 = (node) => [
... (node .birth > 1970 ? [node] : []),
... (node .desc || []) .flatMap (post1970)
]

此代码本身更简单。但我们之前所做的分解不仅帮助我们找到了这些代码，还为我们构建其他工具提供了更大的灵活性。

最后，为了完整性，我们应该证明这段代码在基于class的实现中是一样的。你可以通过扩展这个片段来看到：

const treeFilter = (getChildren) => (pred) => (node) => [
... (pred (node) ? [node] : []),
... (getChildren (node) || []) .flatMap (treeFilter (getChildren) (pred))
]
const familyTreeFilter = treeFilter (n => n .desc)
const post1970 = familyTreeFilter (n => n .birth > 1970)
class Person {
constructor(name, birth) {
this.name = name;
this.birth = birth;
this.desc = [];
}
adddesc(person) {
this.desc.push(person);
}
}
const original = new Person('root', 1900)
let desc1 = new Person("andrew", 1940);
let desc2 = new Person("sarah", 1960);
let desc3 = new Person("charlie", 1980);
let desc4 = new Person("david", 1990);
let desc5 = new Person("ethan", 2000);
original.adddesc(desc1); //Andrew + Charlie
original.adddesc(desc3);
desc1.adddesc(desc2); //Andrew: Sarah
desc3.adddesc(desc4); //Charlie: David
desc4.adddesc(desc5); //David: Ethan

console .log (
post1970 (original) /* for display --> */ .map (n => n .name)
)