JSON 数据的棘手转换

Question

我有主管给受主管的 json 数据。我需要将其放入嵌套形式才能使用 lib_ggOrgChart。问题是……太难了！努力寻找一种简单的方法来做到这一点。也许递归或者其他什么...有人有什么想法吗？

我知道我可以编写一些强力代码......但我希望有一个更优雅的解决方案。任何帮助表示感谢！

{
    {"Supervisor_ID": 1, "Supervisee_ID": 2},
    {"Supervisor_ID": 1, "Supervisee_ID": 3},
    {"Supervisor_ID": 1, "Supervisee_ID": 4},
    {"Supervisor_ID": 2, "Supervisee_ID": 5},
    {"Supervisor_ID": 3, "Supervisee_ID": 6},
    {"Supervisor_ID": 4, "Supervisee_ID": 7},
    {"Supervisor_ID": 4, "Supervisee_ID": 8},
    {"Supervisor_ID": 4, "Supervisee_ID": 9}
}

我需要把它变成这样的形式：

{
    'root':{
        'id': 1,
        'children': {
            {
                'id': 2,
                'children': {
                    {
                        'id': 5
                    }
                }
             },
             {
                'id': 3,
                'children': {
                    {
                        'id': 6
                    }
                }
             },
             {
                'id': 4,
                'children': {
                    {
                        'id': 7
                    },
                    {
                        'id': 8
                    },
                    {
                        'id': 9
                    }
                }
             }
        }
}

Answer 1

这样就可以解决问题了。

/**
 * @typedef TInput
 * @property {number} Supervisor_ID Employee-ID of supervisor
 * @property {number} Supervisee_ID Employee-ID of supervisee
 */
const input = [
  { Supervisor_ID: 1, Supervisee_ID: 2 },
  { Supervisor_ID: 1, Supervisee_ID: 3 },
  { Supervisor_ID: 1, Supervisee_ID: 4 },
  { Supervisor_ID: 2, Supervisee_ID: 5 },
  { Supervisor_ID: 3, Supervisee_ID: 6 },
  { Supervisor_ID: 4, Supervisee_ID: 7 },
  { Supervisor_ID: 4, Supervisee_ID: 8 },
  { Supervisor_ID: 4, Supervisee_ID: 9 },
];

/**
 * Create organization tree from given input.
 * @param {TInput[]} input input
 * @returns {Map<number, Set<number>>} OrgTree
 */
function createOrgTree(input) {
  const rootNodes = new Map();

  input.forEach((relation) => {
    if (rootNodes.has(relation.Supervisor_ID)) {
      rootNodes.get(relation.Supervisor_ID).add(relation.Supervisee_ID);
    } else {
      // I am using a set here to make sure there are no duplicate entries
      // but probably not necessary to use it as there should be no duplicates -> use array instead
      const children = new Set();
      children.add(relation.Supervisee_ID);
      rootNodes.set(relation.Supervisor_ID, children);
    }
  });

  return rootNodes;
}

/**
 * Creates OrgChart for all employees.
 * @param {TInput[]} input input
 * @returns {Object} OrgChart
 */
function createOrgChartAllEmployees(input) {
  const orgTree = createOrgTree(input);
  // loop over all entries here
  const endResult = [...orgTree.entries()].map(([parent, children]) => {
    return buildEmployee(parent, children, orgTree);
  });
  return endResult;
}

/**
 * Creates OrgChart for a given Employee ID.
 * @param {TInput[]} input input
 * @param {number} empId Employee ID
 * @returns {Object} OrgChart
 */
function createOrgChartForEmployee(input, empId) {
  const orgTree = createOrgTree(input);
  if (!orgTree.has(empId)) {
    console.error(`Employee-ID ${empId} does not exist`);
    return null;
  }
  return buildEmployee(empId, orgTree.get(empId), orgTree);
}

/**
 * Recursive function to build an Employee with all their children.
 * @param {number} parent Supervisor ID
 * @param {Set<number>} children Supervisee IDs
 * @param {Map<number, Set<number>>} orgTree Lookup table for parents and children
 */
function buildEmployee(parent, children, orgTree) {
  // Base case: recursion ends here
  if (children === undefined) {
    return {
      id: parent,
    };
  }
  // recursive call
  // children will be the new parent and lookup the children of that child node in rootChodes
  const childArray = [...children.entries()].map(([child, child2]) =>
    buildEmployee(child, orgTree.get(child), orgTree)
  );
  return {
    id: parent,
    children: childArray,
  };
}

/**
 * Pretty-print organization chart.
 * @param {Object} orgChart OrgChart
 * @param {string} title title for OrgChart
 */
function printOrgChart(orgChart, title) {
  console.log(`
-------------------------
 OrgChart: ${title}
-------------------------
`);
  console.log(JSON.stringify(orgChart, null, 4));
}

// this is I believe what you want
// OrgChart for Employee with ID 1 (CEO?)
const ceoOrgChart = createOrgChartForEmployee(input, 1);
printOrgChart(ceoOrgChart, "CEO");

const allEmployeeChart = createOrgChartAllEmployees(input);
printOrgChart(allEmployeeChart, "All Employees");

关键步骤

创建 OrgTree

首先，使用您的输入创建一个 OrgTree，它实际上是一个 Map> 并将每个员工 ID 映射到员工 ID 集合，该集合是该人员员工ID属于主管。
这是下一步的基础。

给定 n 个关系 (Supervisor => Supervise) 以及 Set 和 Map 的恒定查找时间，这需要 O(n).

创建所需的对象结构

考虑函数 createOrgChartForEmployee()，它为给定的 Employee 创建 OrgChart。
在这里，我们首先构建 OrgTree，如上所述，然后从给定的员工开始，即查找他/她的孩子，然后调用 buildEmployee()。
这就是递归的开始。在 buildEmployee() 中，我们需要检查子项是否未定义，对于本身不监督任何员工的员工来说，确实会发生这种情况。在这种情况下，我们只返回员工的 ID。这是我们的基本情况并结束递归。

现在，所有其他员工都将有员工进行监督，因此对所有子员工递归调用 buildEmployee() 并将每个 buildEmployee() 调用的结果映射到包含所有员工的数组中孩子并返回该数组。

有一些特殊的输入需要考虑：

注意：x -> y 表示x 监督 y

退化为列表：

输入：1 -> 2-> 3-> 4-> 5-> 6-> ...-> n

这将导致最大树深度为 n - 1 = O(n)。

无限循环

输入：1 -> 2-> 3-> 1

像这样的输入将导致无限循环，并且迟早会出现错误超出最大调用堆栈大小。但对于 OrgCharts 来说，这个输入不应成为问题。

Answer 2

我不知道我是否正确理解了您想要实现的目标，因为我发现示例我需要将其变成这种形式有点令人困惑（似乎第一个主管出于某种原因包装了所有内容？ ）。无论如何，请尝试一下：

// Supposing this is your array
const supervisorToSupervisee = [
    {"Supervisor_ID": 1, "Supervisee_ID": 2},
    {"Supervisor_ID": 1, "Supervisee_ID": 3},
    {"Supervisor_ID": 1, "Supervisee_ID": 4},
    {"Supervisor_ID": 2, "Supervisee_ID": 5},
    {"Supervisor_ID": 3, "Supervisee_ID": 6},
    {"Supervisor_ID": 4, "Supervisee_ID": 7},
    {"Supervisor_ID": 4, "Supervisee_ID": 8},
    {"Supervisor_ID": 4, "Supervisee_ID": 9}
];

// Backup variable to store the new object
const yourResult = { root: []};
// For of all the Supervisor_ID unique values
for (const id of [...new Set(supervisorToSupervisee.map((x) => x.Supervisor_ID))]) {
    // Pushing to the new object the id of the supervisor and a children 
    // with objects { id: Supervisee_ID }, filtering from the original array 
    // and mapping to the correct format
    yourResult.root.push({
        id,
        children: supervisorToSupervisee
            .filter((x) => x.Supervisor_ID == id)
            .map((x) => ({ id: x.Supervisee_ID }))
    });
}

// Smile
console.log(yourResult);