高级前端面试手写扁平数据结构转Tree

针对“高级前端面试手写扁平数据结构转Tree”的完整攻略，我会从以下几个方面进行讲解：

1. 数据结构：一些常见的扁平数据结构类型及其特点
2. Tree结构：解释Tree结构及其作用
3. 将扁平数据结构转换为Tree结构的思路和方法
4. 代码示例：提供两个转换示例

数据结构

在前端开发中，我们常见到的扁平数据结构类型主要包括对象数组和 JSON 数组两大类型。这两种类型都有共同点，即它们只有一层结构，所有数据都在同一层中。

• 对象数组：由一组对象组成，每个对象都包含相同的属性。
• JSON 数组：由一组 JSON 对象组成，每个对象都包含不同的属性。

Tree结构

在前端开发中，我们经常需要将一个扁平的数据结构转换成为一棵树形数据结构，以便于进行数据展示、操作等。

树形结构是一种层次结构，它由多个节点组成，其中每个节点都包含一个值和指向后继节点的指针。树结构中的节点可以是父节点、子节点、兄弟节点等，每个节点可以包含任意多个子节点。

Tree结构也可以有多种形态，例如二叉树、B树、红黑树等，不同的树形结构有不同的性质和用途。

转换思路和方法

将扁平数据结构转换为Tree结构的关键思路是构建每个节点之间的关系。具体实现方案可以有多种，以下提供一种通用的思路：

1. 定义一个空的树形结构对象，用于存放最终的结果。
2. 遍历扁平的数据结构，将每个节点转换为一个树节点，保存到一个字典对象中，以便后续查找。
3. 遍历每个节点，将它的父节点从字典对象中查找出来，如果找到就将该节点加入到父节点的子节点列表中，否则将该节点添加到根节点。
4. 返回根节点作为最终结果。

具体代码实现时可以借助递归或者循环的方式进行，根据实际情况灵活运用。

代码示例

以下提供两个代码示例，一个使用对象数组，一个使用 JSON 数组。

// 示例1
const arr = [
   { id: 1, name: '根节点', parentId: null },
   { id: 2, name: '节点1', parentId: 1 },
   { id: 3, name: '节点2', parentId: 1 },
   { id: 4, name: '节点3', parentId: 2 },
   { id: 5, name: '节点4', parentId: 2 },
   { id: 6, name: '节点5', parentId: 4 },
];

function toTree(arr) {
  const map = {};
  const result = [];

  // 存入map
  arr.forEach(item => map[item.id] = {...item, children: []});

  // 遍历
  arr.forEach(item => {
    const parent = map[item.parentId];
    if (parent) {
      parent.children.push(map[item.id]);
    } else {
      result.push(map[item.id]);
    }
  })
  return result;
}

const result = toTree(arr);
console.log(result);

// 示例2
const jsonArr = [
   { "id": 1, "name": "根节点", "children": [] },
   { "id": 2, "name": "节点1", "parentId": 1, "children": [] },
   { "id": 3, "name": "节点2", "parentId": 1, "children": [] },
   { "id": 4, "name": "节点3", "parentId": 2, "children": [] },
   { "id": 5, "name": "节点4", "parentId": 2, "children": [] },
   { "id": 6, "name": "节点5", "parentId": 4, "children": [] }
];

function toTree(jsonArr) {
  const map = {};

  // 存入map
  jsonArr.forEach((item, index) => {
    map[item.id] = jsonArr[index];
    map[item.id].children = [];
  });

  // 遍历
  jsonArr.forEach(item => {
    const parent = map[item.parentId];
    if (parent) {
      parent.children.push(item);
    }
  });

  return jsonArr.filter(item => item.parentId === null);
}

const result = toTree(jsonArr);
console.log(result);