在树结构中查找最高 parent

Question

我有一个由下面的数据组成的树结构。当我输入任何人的 _id 值时，我需要一个搜索算法来找到最高领导者，无论领导者还是 child。

例如，如果输入是 "615e8215c3055d1addc216b0"（Rahman 的 ID）或 "61164b4bc08f86505e7dcdd8"（Aaron Aziz 的 ID），它应该 return “Aaron Aziz”的 ID因为他是领导者。

数据结构本质上有一个 2 级结构，其中每个 top-level 条目都有对其直接 children 的引用。请注意，child 可能再次作为领导者（在顶层）出现，以便指定更深层次的连接：

"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"
                    }
                }
            ]
        }
    ]

我创建了一个递归函数。但是当我输入没有 children 的 child 时，它是 return 兄弟而不是 parent。

  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;
  };

我怎样才能让它发挥作用？

Answer 1

由于您总是想要第一个条目，因此您可以使用 families[0] 之类的东西来访问它。您不需要搜索算法：

x = {your json data}
x["families"][0]["leader"]["name"]

输出：

'Aaron Aziz'

Answer 2

我会建议一个函数来首先转换结构，这样每个人都可以在恒定时间内通过 id 查找，给出他们的领导参考、children 参考和其他属性。

所以这里有一个 makeGraph 函数可以做到这一点，然后 getTopLeader 函数可以在该图中搜索给定的 child:

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 变量对于其他查找任务也很有用。

在树结构中查找最高 parent

Finding highest parent in a tree structure

javascript

algorithm

data-structures