javascript - 递归方式层次树的构建逻辑

Question

var cellData = [];
function constructCells(graph, cell) {
  var cellDataObj = {};
  var outgoingEdges = graph.getOutgoingEdges(cell);
  cellDataObj.id = cell.id;
  cellDataObj.value = cell.value;

  if (outgoingEdges.length) {
    cellDataObj.children = [];
    _.each(outgoingEdges, vertex => {
      const target = vertex.target;
      var targetEdges = graph.getOutgoingEdges(target);
      if (targetEdges.length) {
        cellDataObj.children.push({
          id: target.id,
          value: target.value,
          children: getChildrens(graph, target)
        });
      } else {
        cellDataObj.children.push({ id: target.id, value: target.value });
      }
    });
  }
  cellData.push(cellDataObj);
}

function getChildrens(graph, cell) {
  var cells = [];
  var outgoingEdges = graph.getOutgoingEdges(cell);
  _.each(outgoingEdges, vertex => {
    cells.push({
      id: vertex.target.id,
      value: vertex.target.value
    });
  });
  return cells;
}

上面的代码在第一级和第二级(即 v3 节点)之前工作得很好，并且它构造 v4 和 v5 作为其子节点。但我在这里失去了逻辑，并且无法为下面的节点构建(如果它包含子节点)。

结果是:

Looking forward for logic correction required for multilevel nesting i.e for the level of V6 and V7 level nodes.

您可以考虑以下图片作为预期的引用:

平面到 json 的转换，抱歉，我无法发布代码，因为它由库数据组成，并且需要清理代码。

Answer 1

要从平面列表变为树，不需要递归。反过来说，这确实有道理。

---

以下是如何使用单个循环从平面列表获取嵌套结构:

• 创建一个空对象，用于按节点 ID 存储节点
• 创建一个空对象来存储在我们处理其父节点之前出现的节点
• 查看所有条目
  • 创建节点
  • 检查我们之前是否见过引用此 id 作为其父级的节点
    • 如果我们这样做了，请用这些节点预先填充子数组
  • 使用节点 id 作为键将节点添加到对象
  • 检查对象是否已包含该节点的父节点
    • 如果是，则将新节点推送到其父子数组
    • 如果不存在，则将该节点索引为临时孤立节点
  • 检查该节点是否为根节点，如果是则存储
• 返回根节点

在代码中:

const flat = [
  { id: 1, parentId: 3 },
  { id: 3, parentId: 8 },
  { id: 4, parentId: 6 },
  { id: 6, parentId: 3 },
  { id: 7, parentId: 6 },
  { id: 8, parentId: null },
  { id: 10, parentId: 8 },
  { id: 13, parentId: 14 },
  { id: 14, parentId: 10 }
];

const toTree = nodes => {
  const index = {};
  const orphans = {};
  let root = null;
  
  nodes.forEach(
    ({ id, parentId }) => {
      const node = { id, children: orphans[id] || [] };
      index[id] = node;

      const parent = index[parentId];
      
      if (!parent) {
        if (orphans[parentId]) orphans[parentId].push(node)
        else orphans[parentId] = [node];
      } else {
        parent.children.push(node);
      }

      if (parentId === null) root = node;
    }
  );
  
  return root;
}
  

console.log(JSON.stringify(toTree(flat), null, 2));

---

要返回到平面列表:

• 从根节点开始调用展平
• 将根节点连接到结果数组
• 如果它有子节点，则使用根节点 id 作为父节点 id 来展平它们(即递归)

const tree = {"id":8,"children":[{"id":3,"children":[{"id":1,"children":[]},{"id":6,"children":[{"id":4,"children":[]},{"id":7,"children":[]}]}]},{"id":10,"children":[{"id":14,"children":[{"id":13,"children":[]}]}]}]};

const flatten = (node, parentId = null) => 
  [{ id: node.id, parentId }].concat(
    node.children.flatMap(
      child => flatten(child, node.id)
    )
  );
    
console.log(flatten(tree));