以分层树结构打印姓氏

Question

有一个数据对象数组，其中有父子关系。我想按级别打印树的结构，只打印名称。如果没有指明父节点信息则为根节点。

示例输入：

data = [
  {
      id: 1,
      name: "ABC",
      parent: 2
  },
  {
      id: 2,
      name: "BCA"
  },
  {
     id: 3,
     name: "CBA",
     parent: 1
  },
  {
    id: 4,
    name: "DDA",
    parent: 1
  },
  {
    id: 5,
    name: "EFG",
    parent: 2
  }
];

输出：

BCA
    ABC
        CBA
        DDA
    EFG

我尝试使用reduce 获取对象结构但无法获取遍历逻辑。有没有更好的方法来获得解决方案，以便所有子对象都在一个数组下？

const data = [{ id: 1, name: "ABC", parent: 2 },
{ id: 2, name: "BCA" },
{ id: 3, name: "CBA", parent: 1 },
{ id: 4, name: "DDA", parent: 1 }];

let root = null;

const obj = data.reduce((r, o) => {
    Object.assign(r[o.id] = r[o.id] || {}, o);
    if (!o.parent) {
        root = o.id;
    }
    r[o.parent] = r[o.parent] || {};
    r[o.parent][o.id] = r[o.id];
    return r;
}, {});
console.log(obj[root]);

Answer 1

reduce 是正确的操作，因为我们要构建从每个节点到其子节点的平面映射，然后是 return 根节点。需要每个节点的 children 数组，以便我们可以自上而下地遍历和打印树。如果 parent 个引用就足够了，我们就完成了，因为原始结构已经有了这些。

生成嵌套结构的一种方法是：

const unflattenTree = data => {
  const nodes = {};
  let root;

  for (const node of data) {
    nodes[node.id] = {children: [], ...nodes[node.id], ...node};
    
    if (node.parent) {
      nodes[node.parent] = {children: [], ...nodes[node.parent]};
      nodes[node.parent].children.push(nodes[node.id]);
    }
    else {
      root = nodes[node.id];
    }
  }

  return root;
};

const printTree = (root, gap=4, level=0) => {
  if (root) {
    console.log(" ".repeat(level), root.name);
    root.children?.forEach(e => printTree(e, gap, level + gap));
  }
};

const data = [
  {
    id: 1,
    name: "ABC",
    parent: 2
  },
  {
    id: 2,
    name: "BCA"
  },
  {
    id: 3,
    name: "CBA",
    parent: 1
  },
  {
    id: 4,
    name: "DDA",
    parent: 1
  },
  {
    id: 5,
    name: "EFG",
    parent: 2
  }
];

printTree(unflattenTree(data));

Answer 2

一种非常简单但效率低下的方法就是扫描其父节点与特定 ID 匹配的节点，然后使用它们的 ID 重复查找它们的子节点。

const display = (data, id = null, d = 0) => data 
  .filter (({parent}) => parent == id)
  .map (node => '    ' .repeat (d) + node.name  + `\n` +  
        display (data, node.id, d + 1)) .join('')


const data = [{id: 1, name: "ABC", parent: 2}, {id: 2, name: "BCA"}, {id: 3, name: "CBA", parent: 1}, {id: 4, name: "DDA", parent: 1}, {id: 5, name: "EFG", parent: 2}];

console .log (display (data))

.as-console-wrapper {max-height: 100% !important; top: 0}

如果你想生成数据结构（不是树，而是森林，因为可能有多个根），就这么简单：

const renest = (data, id = null) => data 
  .filter (({parent}) => parent == id)
  .map ((node) => ({...node, children: renest (data, node.id)}))

const data = [{id: 1, name: "ABC", parent: 2}, {id: 2, name: "BCA"}, {id: 3, name: "CBA", parent: 1}, {id: 4, name: "DDA", parent: 1}, {id: 5, name: "EFG", parent: 2}];

console .log (renest (data))

.as-console-wrapper {max-height: 100% !important; top: 0}

以分层树结构打印姓氏

Print family names in a hierarchical tree structure

javascript

algorithm

data-structures

tree

treeview