创建一个函数以按级别记录数组顺序中的所有层次结构
Creating a function to log all the hierarchies in the array order by the level
我正在尝试创建一个函数，它按级别按数组顺序记录所有层次结构。
尝试了很多东西，但无法真正弄明白。
如果你能帮助我，我会很高兴。
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" }
];
const func = (arr, level) => {
}
所以等级 3 的等级将是 person2 => person1（因为 parent_id 是 1）=> person3（因为 parent_id 是 8）
感谢您的帮助！
一种方法是更改函数，以便您可以递归调用它，然后我们可以调用 'ourself' 直到找不到父项：
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" }
];
const getMatch = (arr, level, isParent = false) => {
const key = (isParent) ? 'id' : 'level';
const match = arr.filter(a => a[key] === level)[0];
if (!match) { return false; }
const parent = getMatch(arr, match.parent_id, true);
return (parent) ? { ...match, parent } : match;
}
const res = getMatch(arr, 3);
console.log(res);
{
"id": 2,
"parent_id": 1,
"level": 3,
"name": "person2",
"parent": {
"id": 1,
"parent_id": 8,
"level": 2,
"name": "person1",
"parent": {
"id": 8,
"parent_id": 0,
"level": 1,
"name": "person3"
}
}
}
这是针对您的问题的另一个迭代 解决方案，它也适用于同一级别的多个员工。
此解决方案使用 Maps 将查找时间加快到 O(1)，而不是数组查找，后者的最坏情况运行时间为 O(n)。
一张地图将人员 ID 映射到人员详细信息，另一张地图将级别映射到人员 ID。这些地图需要在开始时填充一次，然后可以用来加速树木的创建。
Pre-processing
这里 pre-processing 需要填写地图：
/**
* @typedef TPerson
* @property {number} id
* @property {number} parent_id
* @property {number} level
* @property {string} name
*/
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 4, parent_id: 1, level: 3, name: "person4" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" },
];
// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
if (levels.has(person.level)) levels.get(person.level).push(person.id);
else levels.set(person.level, [person.id]);
persons.set(person.id, person);
});
/**
* Print map for demo purposes (as console.log(map) does not work in SO snippets)
* @param {Map<any, any} map some map
*/
function printMap(map) {
console.log(`Map (${map.size})`);
map.forEach((value, key) =>
console.log(`${key} => ${JSON.stringify(value)}`)
);
}
console.log("Map of person ID to person details:");
printMap(persons);
console.log("Map of level to person IDs of persons on that level:");
printMap(levels);
.as-console-wrapper { max-height: 100% !important; top: 0; }
可能的结果
对于实际算法，有两种方法可以查看它，根据您的描述，其中任何一种都可能是您真正想要的。
获取给定人员的层次结构
这会使用他/她的 ID 获取特定人员的层次结构。参见函数 hierarchyForPerson() 或 hierarchyForPersonNested().
获取给定级别的层次结构
给定级别的层次结构。在这种情况下，我们可以有多个层次结构，例如以下层次结构
1
/ \
2 3
/ / \
4 5 6
在这种情况下，4、5 和 6 将处于同一级别，但具有不同的层次结构。为了考虑 hierarchyForAllPersonsOnLevel() 或 hierarchyForAllPersonsOnLevelNested() return 的功能 object 层次结构，其中包含给定级别上每个人的一个层次结构。
组织结果
还有两种不同的方式来组织结果
线性
层次结构被 return 编辑为数组，其中数组中索引为 i 的人是数组中索引为 j 的人的 child所有 0 <= i < j <= array.length。
以这个层次结构为例：
1
/
2
此处第 2 个人的结果为 [2, 1]，这意味着 2 是 1 的 child。
所有名称末尾没有 Nested 的函数都将创建线性结果。
嵌套
层次结构被 return 编辑为嵌套的 object，其中包含 parent 属性，其中包含 parent。如果没有parent，就没有parent 属性（这个也可以改）。
如果我们采用与上面相同的层次结构，结果将是：
{
id: 2,
parent: {
id: 1,
}
}
名称末尾带有 Nested 的所有函数都将创建嵌套结果。
实施
此处使用 pre-processing 实现了实际算法（但没有不必要的输出）。
为了表明该实施适用于所描述的同一级别的多个人，我在您的示例中又添加了一个人 ({ id: 4, parent_id: 1, level: 3, name: "person4" },)，这是第 3 级的另一个人。因此层次结构现在看起来像这样：
8
\
1
/ \
2 4
/**
* @typedef TPerson
* @property {number} id
* @property {number} parent_id
* @property {number} level
* @property {string} name
*/
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 4, parent_id: 1, level: 3, name: "person4" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" },
];
// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
if (levels.has(person.level)) levels.get(person.level).push(person.id);
else levels.set(person.level, [person.id]);
persons.set(person.id, person);
});
/**
* Prints hierarchy for all persons on a level in a linear (non-nested way).
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {Map<number, number>} levels Map of levels to person IDs on that level
* @param {number} level level that is supposed to be printed
* @returns one hierarchy for each person on a specified level
*/
function hierarchyForAllPersonsOnLevel(persons, levels, level) {
if (!levels.has(level))
throw new Error(`there is no person on level ${level}`);
const allOnLevel = levels.get(level);
return allOnLevel.reduce((allHierarchies, personId) => {
allHierarchies[personId] = hierarchyForPerson(persons, personId);
return allHierarchies;
}, {});
}
/**
* Prints hierarchy for all persons on a level in a nested way.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {Map<number, number>} levels Map of levels to person IDs on that level
* @param {number} level level that is supposed to be printed
* @returns one hierarchy for each person on a specified level
*/
function hierarchyForAllPersonsOnLevelNested(persons, levels, level) {
if (!levels.has(level))
throw new Error(`there is no person on level ${level}`);
const allOnLevel = levels.get(level);
return allOnLevel.reduce((allHierarchies, personId) => {
// only difference to non-nested structure is the call to hierarchyForPersonNested() instead of hierarchyForPerson()
allHierarchies[personId] = hierarchyForPersonNested(persons, personId);
return allHierarchies;
}, {});
}
/**
* Creates hierarchy for a given person.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {number} id person ID
* @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
*/
function hierarchyForPerson(persons, id) {
let curId = id;
const hierarchy = [];
while (persons.has(curId)) {
const person = persons.get(curId);
hierarchy.push(person);
curId = person.parent_id;
}
return hierarchy;
}
/**
* Creates hierarchy for a given person.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {number} id person ID
* @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
*/
function hierarchyForPersonNested(persons, id) {
let curId = id;
let curHierarchy = {};
let hierarchy = {};
let isRoot = true;
while (persons.has(curId)) {
const person = persons.get(curId);
if (isRoot) {
curHierarchy = {...person};
// let hierarchy always point to top most object
hierarchy = curHierarchy;
isRoot = false;
} else {
curHierarchy.parent = {...person};
curHierarchy = curHierarchy.parent;
}
curId = person.parent_id;
}
return hierarchy;
}
console.log(`
+-----------------------------------
| Hierarchy for person with ID 2
+-----------------------------------`);
console.log("> Linear")
console.log(hierarchyForPerson(persons, 2));
console.log("> Nested")
console.dir(hierarchyForPersonNested(persons, 2), { depth: null });
console.log(`
+-----------------------------------
| Hierarchy for all persons on level 3
+-----------------------------------`);
console.log("> Linear");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevel(persons, levels, 3), null, 2));
console.log("> Nested");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevelNested(persons, levels, 3), null, 2));
.as-console-wrapper { max-height: 100% !important; top: 0; }
我正在尝试创建一个函数，它按级别按数组顺序记录所有层次结构。
尝试了很多东西，但无法真正弄明白。
如果你能帮助我，我会很高兴。
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" }
];
const func = (arr, level) => {
}
所以等级 3 的等级将是 person2 => person1（因为 parent_id 是 1）=> person3（因为 parent_id 是 8）
感谢您的帮助！
一种方法是更改函数，以便您可以递归调用它，然后我们可以调用 'ourself' 直到找不到父项：
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" }
];
const getMatch = (arr, level, isParent = false) => {
const key = (isParent) ? 'id' : 'level';
const match = arr.filter(a => a[key] === level)[0];
if (!match) { return false; }
const parent = getMatch(arr, match.parent_id, true);
return (parent) ? { ...match, parent } : match;
}
const res = getMatch(arr, 3);
console.log(res);
{
"id": 2,
"parent_id": 1,
"level": 3,
"name": "person2",
"parent": {
"id": 1,
"parent_id": 8,
"level": 2,
"name": "person1",
"parent": {
"id": 8,
"parent_id": 0,
"level": 1,
"name": "person3"
}
}
}
这是针对您的问题的另一个迭代 解决方案，它也适用于同一级别的多个员工。
此解决方案使用 Maps 将查找时间加快到 O(1)，而不是数组查找，后者的最坏情况运行时间为 O(n)。
一张地图将人员 ID 映射到人员详细信息，另一张地图将级别映射到人员 ID。这些地图需要在开始时填充一次，然后可以用来加速树木的创建。
Pre-processing
这里 pre-processing 需要填写地图：
/**
* @typedef TPerson
* @property {number} id
* @property {number} parent_id
* @property {number} level
* @property {string} name
*/
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 4, parent_id: 1, level: 3, name: "person4" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" },
];
// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
if (levels.has(person.level)) levels.get(person.level).push(person.id);
else levels.set(person.level, [person.id]);
persons.set(person.id, person);
});
/**
* Print map for demo purposes (as console.log(map) does not work in SO snippets)
* @param {Map<any, any} map some map
*/
function printMap(map) {
console.log(`Map (${map.size})`);
map.forEach((value, key) =>
console.log(`${key} => ${JSON.stringify(value)}`)
);
}
console.log("Map of person ID to person details:");
printMap(persons);
console.log("Map of level to person IDs of persons on that level:");
printMap(levels);
.as-console-wrapper { max-height: 100% !important; top: 0; }
可能的结果
对于实际算法，有两种方法可以查看它，根据您的描述，其中任何一种都可能是您真正想要的。
获取给定人员的层次结构
这会使用他/她的 ID 获取特定人员的层次结构。参见函数 hierarchyForPerson() 或 hierarchyForPersonNested().
获取给定级别的层次结构
给定级别的层次结构。在这种情况下，我们可以有多个层次结构，例如以下层次结构
1
/ \
2 3
/ / \
4 5 6
在这种情况下，4、5 和 6 将处于同一级别，但具有不同的层次结构。为了考虑 hierarchyForAllPersonsOnLevel() 或 hierarchyForAllPersonsOnLevelNested() return 的功能 object 层次结构，其中包含给定级别上每个人的一个层次结构。
组织结果
还有两种不同的方式来组织结果
线性
层次结构被 return 编辑为数组，其中数组中索引为 i 的人是数组中索引为 j 的人的 child所有 0 <= i < j <= array.length。
以这个层次结构为例：
1
/
2
此处第 2 个人的结果为 [2, 1]，这意味着 2 是 1 的 child。
所有名称末尾没有 Nested 的函数都将创建线性结果。
嵌套
层次结构被 return 编辑为嵌套的 object，其中包含 parent 属性，其中包含 parent。如果没有parent，就没有parent 属性（这个也可以改）。
如果我们采用与上面相同的层次结构，结果将是：
{
id: 2,
parent: {
id: 1,
}
}
名称末尾带有 Nested 的所有函数都将创建嵌套结果。
实施
此处使用 pre-processing 实现了实际算法（但没有不必要的输出）。
为了表明该实施适用于所描述的同一级别的多个人，我在您的示例中又添加了一个人 ({ id: 4, parent_id: 1, level: 3, name: "person4" },)，这是第 3 级的另一个人。因此层次结构现在看起来像这样：
8
\
1
/ \
2 4
/**
* @typedef TPerson
* @property {number} id
* @property {number} parent_id
* @property {number} level
* @property {string} name
*/
const arr = [
{ id: 1, parent_id: 8, level: 2, name: "person1" },
{ id: 4, parent_id: 1, level: 3, name: "person4" },
{ id: 2, parent_id: 1, level: 3, name: "person2" },
{ id: 8, parent_id: 0, level: 1, name: "person3" },
];
// pre-processing to have quick lookups in Maps instead of filtering arrays
const persons = new Map();
const levels = new Map();
arr.forEach((person) => {
if (levels.has(person.level)) levels.get(person.level).push(person.id);
else levels.set(person.level, [person.id]);
persons.set(person.id, person);
});
/**
* Prints hierarchy for all persons on a level in a linear (non-nested way).
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {Map<number, number>} levels Map of levels to person IDs on that level
* @param {number} level level that is supposed to be printed
* @returns one hierarchy for each person on a specified level
*/
function hierarchyForAllPersonsOnLevel(persons, levels, level) {
if (!levels.has(level))
throw new Error(`there is no person on level ${level}`);
const allOnLevel = levels.get(level);
return allOnLevel.reduce((allHierarchies, personId) => {
allHierarchies[personId] = hierarchyForPerson(persons, personId);
return allHierarchies;
}, {});
}
/**
* Prints hierarchy for all persons on a level in a nested way.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {Map<number, number>} levels Map of levels to person IDs on that level
* @param {number} level level that is supposed to be printed
* @returns one hierarchy for each person on a specified level
*/
function hierarchyForAllPersonsOnLevelNested(persons, levels, level) {
if (!levels.has(level))
throw new Error(`there is no person on level ${level}`);
const allOnLevel = levels.get(level);
return allOnLevel.reduce((allHierarchies, personId) => {
// only difference to non-nested structure is the call to hierarchyForPersonNested() instead of hierarchyForPerson()
allHierarchies[personId] = hierarchyForPersonNested(persons, personId);
return allHierarchies;
}, {});
}
/**
* Creates hierarchy for a given person.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {number} id person ID
* @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
*/
function hierarchyForPerson(persons, id) {
let curId = id;
const hierarchy = [];
while (persons.has(curId)) {
const person = persons.get(curId);
hierarchy.push(person);
curId = person.parent_id;
}
return hierarchy;
}
/**
* Creates hierarchy for a given person.
* @param {Map<number, TPerson>} persons Map of person IDs to person details
* @param {number} id person ID
* @returns an array where person a[i] is supervised by person a[j] for all i < j e.g. result [{id: 1}, {id: 2}] means 1 is supervised by 2
*/
function hierarchyForPersonNested(persons, id) {
let curId = id;
let curHierarchy = {};
let hierarchy = {};
let isRoot = true;
while (persons.has(curId)) {
const person = persons.get(curId);
if (isRoot) {
curHierarchy = {...person};
// let hierarchy always point to top most object
hierarchy = curHierarchy;
isRoot = false;
} else {
curHierarchy.parent = {...person};
curHierarchy = curHierarchy.parent;
}
curId = person.parent_id;
}
return hierarchy;
}
console.log(`
+-----------------------------------
| Hierarchy for person with ID 2
+-----------------------------------`);
console.log("> Linear")
console.log(hierarchyForPerson(persons, 2));
console.log("> Nested")
console.dir(hierarchyForPersonNested(persons, 2), { depth: null });
console.log(`
+-----------------------------------
| Hierarchy for all persons on level 3
+-----------------------------------`);
console.log("> Linear");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevel(persons, levels, 3), null, 2));
console.log("> Nested");
console.log(JSON.stringify(hierarchyForAllPersonsOnLevelNested(persons, levels, 3), null, 2));
.as-console-wrapper { max-height: 100% !important; top: 0; }