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 构造为其子节点。但是我在这里的某个地方失去了逻辑，如果有孩子，我就无法为下面的节点构建。

结果是：

期待多级嵌套所需的逻辑校正，即 V6 和 V7 级别节点的级别。

您可以考虑以下图片作为预期的参考：

平面到 json 转换，抱歉，我无法发布代码，因为其中包含库数据和代码需要清理。

标签： javascriptarraysjsonrecursionmxgraph

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

---

回到平面列表：

• flatten从根节点开始调用
• 将根节点连接到结果数组
• 如果它有子节点，则使用根节点 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));