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

我不知道我是否正确理解了您想要实现的目标，因为我发现这个示例 I need to get it into this form 有点令人困惑（好像第一个主管出于某种原因正在包装所有内容？）。无论如何，试一试：

// 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);

Answer 2

这样就可以了。

/**
 * @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，它实际上是一个 Map<number, Set<number>> 并将每个员工 ID 映射到员工 ID 集，该员工 ID 所属的人负责监督。这是下一步的基础。

给定 n 关系（Supervisor => Supervisee）和 Set 和 Map 的恒定查找时间，这需要 O(n)。

正在创建所需的 object 结构

考虑为给定员工创建 OrgChart 的函数 createOrgChartForEmployee()。在这里，我们首先构建 OrgTree，如上所述，然后从给定的员工 i 开始。 e.查找他/她的 children 然后调用 buildEmployee()。这就是递归的开始。在 buildEmployee() 中，我们需要检查 children 是否未定义，这确实发生在自己不监督任何员工的员工身上。在那种情况下，我们只是 return 员工的 ID。这是我们的基本情况并结束递归。

现在，所有其他员工都将有员工监督，因此递归调用 buildEmployee() 所有 children 并将每个 buildEmployee() 调用的结果映射到包含所有 buildEmployee() 的数组中=63=] 和 return 那个数组。

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

Note: x -> y means x supervises y

退化到列表：

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

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

无限循环

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

像这样的输入将导致无限循环，迟早会导致错误 Maximum call stack size exceeded。但是对于 OrgCharts，这个输入不应该是一个问题。

JSON 数据的棘手转换

Tricky transformation of JSON data

javascript

json

orgchart

关键步骤

创建组织树

正在创建所需的 object 结构

退化到列表：

无限循环