我有一個具有以下屬性的 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();
uj5u.com熱心網友回復：
我有一些前期的設計建議：
post1970()是過于剛性。年份應該是一個引數。否則，您必須重新撰寫整個函式，以便按 1969 年或任何其他年份進行過濾。像bornAfter(year)這樣的契約會是更好的方法，或者進一步概括并使其成為像 那樣的任意謂詞filterDescendants(predicateFunction)。let除非您絕對必須使用它，否則請避免使用它。const使您的代碼更安全、更具表現力。每當我看到let，我都覺得程式員試圖告訴我“我打算重新分配這個變數”。在大多數情況下，這是一個紅鯡魚，包括這個 - 使用const。重新分配是一個拐杖，往往會使代碼難以遵循。desc讓我想到“描述”。descendants清楚多了。我也會把它作為建構式的陣列；如果您還想要加法器/設定器/獲取器，那也很好，但是不允許一次性構建物件并且必須將其存盤在中間變數中以增量設定其屬性有點尷尬。- 在
Person類上擁有這些面向樹的過濾功能有點奇怪。您可能想要一個FamilyTree具有 root的類Person。這使得代碼讀起來像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);如果效率是一個大問題，作為第二步的過濾有點浪費，所以你可以嘗試一個具有空間意識的生成器函式。整體遞回模式是相同的。
uj5u.com熱心網友回復：
幾個注意事項：
首先，我同意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。）這將回傳一個接受謂詞的函式——為謂詞提供一個值，并報告我們是否要包含該值。它回傳一個接受樹的函式，并將樹的匹配元素作為平面陣列回傳。
這個柯里化版本的優點是我們可以post1970在任何類似結構的樹上重用我們的簡單。我們可以重用familyTreeFilter為此類descendant-child 結構創建其他過濾器。也許我們想要所有birth2000 年之前的人，或者以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)
)轉載請註明出處，本文鏈接：https://www.uj5u.com/net/383341.html
標籤：javascript 递归 树 深度优先搜索
下一篇：二叉樹中數字的總和