学习时长两年半的前端还不会这个？

前言

我的朋友小菜同学是一个学习时长两年半的前端boy。面试的时候，面试官让他写一个扁平数据结构转Tree.他思考片刻不好意思的说“你干嘛啊，哎呦”。可想而知之，这次的面试以失败告终了。

“斯人已去，生者如斯”，让我们看看这个东西到底怎么写！

Main

扁平数据结构：扁平数据结构是指所有数据都在同一层级上的数据结构。如下所示。

const flatData = [
  {id: 1, name: 'Node 1', parentId: null},
  {id: 2, name: 'Node 1.1', parentId: 1},
  {id: 3, name: 'Node 1.1.1', parentId: 2},
  {id: 4, name: 'Node 1.1.2', parentId: 2},
  {id: 5, name: 'Node 1.2', parentId: 1},
  {id: 6, name: 'Node 2', parentId: null},
  {id: 7, name: 'Node 2.1', parentId: 6},
  {id: 8, name: 'Node 2.2', parentId: 6},
  {id: 9, name: 'Node 2.2.1', parentId: 8},
  {id: 10, name: 'Node 2.2.2', parentId: 8}
];

树形结构: 树形数据结构则是一种多级嵌套的数据结构。如下所示。

[
  {
    id: 1,
    name: 'Node 1',
    parentId: null,
    children: [
      {
        id: 2,
        name: 'Node 1.1',
        parentId: 1,
        children: [
          {id: 3, name: 'Node 1.1.1', parentId: 2},
          {id: 4, name: 'Node 1.1.2', parentId: 2}
        ]
      },
      {id: 5, name: 'Node 1.2', parentId: 1}
    ]
  },

代码实现

1.递归算法实现

function buildTree(flatData, parentId = null) {
  const tree = [];

  flatData.forEach((node) => {
    if (node.parentId === parentId) {
      const children = buildTree(flatData, node.id);

      if (children.length > 0) {
        node.children = children;
      }
    
      tree.push(node);
    }

  });

  return tree;
}

const treeData = buildTree(flatData, null);
console.log(treeData);

代码中的 buildTree 函数接收两个参数：flatData 表示扁平数据结构，parentId 表示要构建树的父节点。在函数中，我们首先创建一个空数组 tree 用于保存生成的树节点。

接下来，我们遍历扁平数据结构中的每个节点，如果节点的 parentId 与指定的父节点匹配，则将该节点加入到树中。

在将节点加入树中之前，我们通过递归调用 buildTree 函数来生成该节点的子节点。如果子节点存在，则将其添加到节点的 children 属性中。

最后，我们返回树形结构。

2.迭代

采用迭代的方式来构建树形结构，可以使用一个哈希表来存储每个节点的引用。遍历扁平数据结构时，如果该节点的父节点已经在哈希表中，则将该节点添加到父节点的 children 属性中，否则将该节点添加到哈希表中。

function buildTree(flatData) {
  const tree = [];
  const nodes = {};

  flatData.forEach((node) => {
    nodes[node.id] = {...node, children: []};
  });

  Object.values(nodes).forEach((node) => {
    const parentId = node.parentId;
    if (parentId === null) {
      tree.push(node);
    } else {
      nodes[parentId].children.push(node);
    }
  });

  return tree;
}

在代码中，我们首先使用 forEach 方法遍历扁平数据结构，并将每个节点添加到哈希表中。哈希表中的键为节点的 id，值为一个新的对象，其中包含该节点的所有属性以及一个空数组 children 用于存储其子节点。

接下来，我们再次使用 forEach 方法遍历哈希表中的每个节点，如果该节点的 parentId 为 null，则将该节点添加到根节点中，否则将该节点添加到其父节点的 children 属性中。

由于哈希表可以实现常数时间的查找操作，因此该算法的时间复杂度为 O(n)。

结束语

本章的内容就到此结束了，希望对大家有所帮助。点个赞吧 :+1: