递归函数，用于查找给定 id 的顶级父级

Question

给定以下数据集：

const accounts = [
{id: 2, children: [1,22,69], parentId: null},
{id: 3, children: [140, 122, 580], parentId: null},
{id: 1, children: [4,5,6], parentId: 2},
{id: 22, children: [8,9,2], parentId: 2},
{id: 4, children: [45,54,61], parentId: 1},
{id: 6, children: [40,89,20], parentId: 1},
{id: 40, children: [], parentId: 6},
....
]

我需要创建一个函数，该函数将 and id 作为参数并返回一棵树，从最顶层的父级开始，它是子级(和兄弟姐妹(。

在上面的例子中，只有 2 个顶级"帐户"，id：2 和 id：3。所以函数调用可能看起来像findTree(89)，它应该返回以帐户 id 2 开头的树，它是子项，但显然会省略帐户 ID 3 和它的子项，因为该顶级帐户与 id 2 的顶级帐户无关，因此理想的响应是：

{
id: 2,
children: [
{ id: 1, children: [{id: 540, children: [{ id: 78},{}], parentId:1], parentId: 2},
.....
],
parentId: null
}

最好的方法是什么？我已经尝试了一个递归函数，但我还没有接近解决方案。

编辑：这是代码的一部分： (groupArray 是一个数组，包含平面列表中的所有项目，没有层次结构(

const makeTreeById = itemId => {
const startNode = _.find(groupArray, {id: itemId}) // grab the actual item, not the id
findTopParent(startNode)
}

然后查找 TopParent fn

const findTop = item => {
let top = item;
if(top.parentId) {
top = _.find(groupArray, {id: top.parentId}
return findTop(top)
}
return top;
}

我正在创建该函数以简单地让它返回顶级帐户，然后我计划从那里构建实际的树，问题是 top 确实让我获得了顶级，但在某些时候它被重新分配给直接父级。

第二次编辑：很抱歉所有的困惑，正如你所看到的，我真的是新手。 我有一个数组，其中包含我需要的所有项目。所以它看起来像这样：

// children here are only ids, not the actual elements, the element are part of // the list, but the children array for each element is just a reference.
data = [
{id: 1, children: [4,5,6], parentId: null}, 
{id: 2, children: [7,8,9], parentId: null},
{id: 3, children: [10,11,12], parentId: null},
{id: 4, children: [13,14,15], parentId: 1},
{id: 10, children: [20,21,22], parentId: 3}
{id: 14, children: [], parentId: 4}
....
]

Answer 1

您可以使用函数topParent找到所需的结果。只需在每次迭代中查找父级为 null。

const accounts = [
{id: 2, children: [1,22,69], parentId: null},
{id: 3, children: [140, 122, 580], parentId: null},
{id: 1, children: [4,5,6], parentId: 2},
{id: 22, children: [8,9,2], parentId: 2},
{id: 4, children: [45,54,61], parentId: 1},
{id: 6, children: [40,89,20], parentId: 1},
{id: 40, children: [], parentId: 6}
];
function topParent(id) {
var obj = accounts.find((v) => v.id == id);
return obj.parentId == null ? obj : topParent(obj.parentId)
}
console.log(topParent(6));

Answer 2

实际上它们是实现预期树的多种方法。在性能方面，您应该确定您的树深处是否会有复杂性(就迭代而言(或 |以及您将拥有总共多少件物品。

我假设复杂性将更多地在于您将拥有总共多少项目。

示例：大量帐户，只有少量嵌套子帐户。

---

简介：下面是类型和示例数组。

interface IEntity {
id: number;
children: number[];
parentId?: number;
}
interface IEntityNested {
id: number;
children: IEntityNested[];
parentId?: number;
}
const accounts: IEntity[] = [
{id: 1, children: [3], parentId: null},
{id: 2, children: [], parentId: null},
{id: 3, children: [4], parentId: 1},
{id: 4, children: [], parentId: 3},
];

为此，我建议您从搜索任何特定的id开始，什么是树的顶部。没有任何其他顶级元素的元素。

const findTopParent = (id: number): IEntity => {
let account = accounts.find(acc => acc.id === id);
if(account.parentId !== null) {
account = findTopParent(account.parentId);
}
return account;
};

对于 id 4，它应返回帐户 ID 1

const topParent = findTopParent(4);
console.log(topParent.id); // Print 1.

然后，您可以从topParent从上到下构建嵌套树。

const buildTreeFromSpecificAccount = (account: IEntity): IEntityNested => {
const nestedAccount = {...account,children: []};
account.children.forEach(childId => {
nestedAccount.children.push(
buildTreeFromSpecificAccount(
accounts.find(acc => acc.id === childId)
)
);
})
return nestedAccount;
}
// Build the tree from the top parent.
const tree = buildTreeFromSpecificAccount(topParent);

瞧！

---

旁注 ：

您可以通过按索引对象更改数据数组来提高性能，如下所示：

const accountOrdered: {[id: number]: IEntity} = {
1: {id: 1, children: [3], parentId: null},
2: {id: 2, children: [], parentId: null},
3: {id: 3, children: [4], parentId: 1},
4: {id: 4, children: [], parentId: 3},
};

像这样，而不是在数组上执行accounts.find(acc => acc.id === childId)循环以按 id 查找条目。 你可以做accountOrdered[childId]

---

现场样品