我有一個由以下資料組成的樹結構。當我輸入任何人的_id價值時，無論是領導者還是孩子，我都需要一種搜索??演算法來找到最高領導者。
例如，如果輸入是"615e8215c3055d1addc216b0"（Rahman 的 id）或"61164b4bc08f86505e7dcdd8"（Aaron Aziz 的 id），它應該回傳“Aaron Aziz”的 id，因為他是領導者。
資料結構本質上有一個 2 級結構，其中每個頂級條目都有對其直接子項的參考。請注意，孩子可能會再次作為領導者出現（在頂層），以便指定更深層次的聯系：
"families": [
{
"datecreated": "2021-10-06T07:39:28.988Z",
"_id": "615d52cb7cc6d32978afa694",
"leader": {
"_id": "61164b4bc08f86505e7dcdd8",
"name": "Aaron Aziz"
},
"children": [
{
"datejoined": "2021-10-06T07:39:28.988Z",
"_id": "615d52cb7cc6d32978afa695",
"child": {
"_id": "615c15c66dd91a2d4385ac84",
"name": "Amirul Adha"
}
},
{
"datejoined": "2021-10-06T08:04:52.122Z",
"_id": "615d58cf0f045f320cb28706",
"child": {
"_id": "615d58b40f045f320cb28701",
"name": "Samirul Ali"
}
}
]
},
{
"datecreated": "2021-10-07T05:12:22.671Z",
"_id": "615e8475c3055d1addc216b5",
"leader": {
"_id": "615c15c66dd91a2d4385ac84",
"name": "Amirul Adha"
},
"children": [
{
"datejoined": "2021-10-07T05:12:22.671Z",
"_id": "615e8475c3055d1addc216b6",
"child": {
"_id": "615e8215c3055d1addc216b0",
"name": "Rahman"
}
}
]
},
{
"datecreated": "2021-10-07T08:52:47.840Z",
"_id": "615eb630e0cc0d22281bb282",
"leader": {
"_id": "615e8215c3055d1addc216b0",
"name": "Rahman"
},
"children": [
{
"datejoined": "2021-10-07T08:52:47.840Z",
"_id": "615eb630e0cc0d22281bb283",
"child": {
"_id": "615eb60de0cc0d22281bb27d",
"name": "Aizi"
}
}
]
}
]
我創建了一個遞回函式。但是當我輸入一個沒有孩子的孩子時，它會回傳兄弟姐妹而不是父母。
const findLeader = (childId) => {
let leader;
for (const family of familiesCopy) {
const isChild = family.children.find((i) => i.child._id == childId);
leader = family.leader;
if (isChild) {
findLeader(family.leader._id);
}
if (!isChild) {
return leader;
}
}
return leader;
};
我怎樣才能讓它作業？
uj5u.com熱心網友回復：
因為您總是想要第一個條目，所以您可以使用 family[0] 之類的東西來訪問它。您不需要搜索演算法：
x = {your json data}
x["families"][0]["leader"]["name"]
輸出：
'Aaron Aziz'
uj5u.com熱心網友回復：
我建議先使用一個函式來轉換結構，這樣每個人都可以在恒定時間內通過 id 查找，給出他們的領導者參考、子級參考和其他屬性。
所以這里有一個makeGraph函式可以做到這一點，然后getTopLeader函式來搜索給定孩子的圖形：
function makeGraph(families) {
// Collect children and key by their id
let graph = Object.fromEntries(families.flatMap(({ leader: { _id }, children }) =>
children.map(({ child, ...relation }) => [child._id, {
...child,
leader: _id,
relation,
children: [],
}])
));
// Collect leaders and key by their id, possibly extending existing entry
for (let { leader, children, ...creation } of families) {
Object.assign(graph[leader._id] ??= {}, {
...leader,
creation,
children: children.map(({child}) => child._id)
});
}
return graph;
}
function getTopLeader(graph, id) {
if (!graph[id]) return; // Not found
while (graph[id].leader) id = graph[id].leader;
return id;
}
// Example run on question's data
let obj = {"families": [{"datecreated": "2021-10-06T07:39:28.988Z","_id": "615d52cb7cc6d32978afa694","leader": {"_id": "61164b4bc08f86505e7dcdd8","name": "Aaron Aziz"},"children": [{"datejoined": "2021-10-06T07:39:28.988Z","_id": "615d52cb7cc6d32978afa695","child": {"_id": "615c15c66dd91a2d4385ac84","name": "Amirul Adha"}},{"datejoined": "2021-10-06T08:04:52.122Z","_id": "615d58cf0f045f320cb28706","child": {"_id": "615d58b40f045f320cb28701","name": "Samirul Ali"}}]},{"datecreated": "2021-10-07T05:12:22.671Z","_id": "615e8475c3055d1addc216b5","leader": {"_id": "615c15c66dd91a2d4385ac84","name": "Amirul Adha"},"children": [{"datejoined": "2021-10-07T05:12:22.671Z","_id": "615e8475c3055d1addc216b6","child": {"_id": "615e8215c3055d1addc216b0","name": "Rahman"}}]},{"datecreated": "2021-10-07T08:52:47.840Z","_id": "615eb630e0cc0d22281bb282","leader": {"_id": "615e8215c3055d1addc216b0","name": "Rahman"},"children": [{"datejoined": "2021-10-07T08:52:47.840Z","_id": "615eb630e0cc0d22281bb283","child": {"_id": "615eb60de0cc0d22281bb27d","name": "Aizi"}}]}]};
let graph = makeGraph(obj.families);
let childid = "615e8215c3055d1addc216b0"; // Rahman
let leaderid = getTopLeader(graph, childid); // 61164b4bc08f86505e7dcdd8 = Aaron Aziz
console.log(`Leader of ${childid} is ${leaderid}`);該graph變數對于其他查找任務也很有用。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313550.html
標籤：javascript 算法 数据结构
上一篇：給定一個雙正則圖，如何找到在一側具有給定數量的頂點的最大邊完全二分/雙派子圖？
下一篇：計算組成字串的方法數