JavaScript 将树形结构转换一维数组（递归）

将树形结构转换为一维数组是一个常见的任务，通常使用递归或迭代的方法来完成。具体案例实现如下：

function flattenTree(treeData) {
  const result = [];

  function traverse(node) {    
    if (node.children && node.children.length > 0) {
      for (const child of node.children) {
        traverse(child);
      }
    }
    delete node.children
    result.push(node);
  }

  traverse(treeData);
  return result;
}

// 示例数据结构
const treeData = {
  name: "A",
  children: [
    {
      name: "B",
      children: [
        {
          name: "D",
          children: [],
        },
        {
          name: "E",
          children: [],
        },
      ],
    },
    {
      name: "C",
      children: [
        {
          name: "F",
          children: [],
        },
      ],
    },
  ],
};

const flattenedArray = flattenTree(treeData);
console.log(flattenedArray);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

flattenTree 函数递归地遍历树的每个节点，并将节点添加到结果数组中。如果节点具有子节点，它会继续遍历子节点。最终，你将得到一个包含树中所有节点的一维数组。

代码实现如下：

getOneArr (data) {
  let newData = []
  const callback = (item) => {
    (item.children || (item.children = [])).map(v => {
      callback(v)
    })
    delete item.children
    newData.push(item)
  }
  data.map(v => callback(v))
  return newData
},

const flattenedArray = getOneArr(treeData);
console.log(flattenedArray);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

getOneArr 使用了递归方法，它接受一个包含树形结构数据的数组 data，并将其转换为一维数组。将数据结构从多维树状结构变成一维数组，然后删除了原始数据中的子节点，最后输出一个一维数组，其中包含了所有节点的数据，同时删除了子节点属性，使其成为一个扁平的结构。

如何将一维数组转换为树型结构

// 测试案例
const flatData = [
  { id: 1, name: "Root", parentId: null },
  { id: 2, name: "Child 1", parentId: 1 },
  { id: 3, name: "Child 2", parentId: 1 },
  { id: 4, name: "Subchild 1", parentId: 2 },
  { id: 5, name: "Subchild 2", parentId: 2 },
  { id: 6, name: "Child 3", parentId: 1 },
];

function buildTree(data, rootId) {
  // 创建一个空对象 tree，按照其 id 属性进行映射，快速查找和建立父子关系
  const tree = {};

  
  data.forEach(item => {
    if (!tree[item.id]) {
      // 创建一个新节点，包括所有 item 的属性，并初始化一个空的 "children" 数组。
      tree[item.id] = { ...item, children: [] };
    } else {
      // item 对象的属性与现有节点的属性合并。这是为了处理可能出现的多个具有相同 id 的项
      tree[item.id] = { ...tree[item.id], ...item };
    }

	// 确定当前元素的父节点 parent
    const parent = item.parentId || rootId;
    // 如果父节点不存在于 tree 中，创建一个新的父节点对象，初始化一个空的 "children" 数组。
    if (!tree[parent]) {
      tree[parent] = { children: [] };
    }
    // 当前元素添加到其父节点的 "children" 数组中
    tree[parent].children.push(tree[item.id]);
  });

  // 返回树的顶层元素
  return tree[rootId].children;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

buildTree 函数遍历输入数组并构建树形结构。它使用一个对象 tree 来存储节点，并将每个节点添加到相应的父节点的 children 数组中。最后，它返回树的根节点或指定根节点的子节点。该函数接受两个参数：data 是包含元素的扁平数组，rootId 是指定的根节点的 id，通常为 null。

reduce + 递归

使用 reduce 和递归的方式将一维数组转换为树形结构是一种非常优雅和紧凑的方法。具体代码如下：

function buildTree(data, parentId = null) {
  // 使用 reduce 方法对 data 数组进行迭代，并返回一个新的数组 res
  return data.reduce((res, item) => {
  	// 当前元素的 parentId 等于传入 parentId 的子元素，需要将它加入到树中。
    if (item.parentId === parentId) {
      // 使用递归方式调用 buildTree 函数，传入 data 和当前元素的 id 作为新的 parentId。这将返回一个表示当前元素的子元素的数组
      const children = buildTree(data, item.id);
      // children 数组不为空，将赋给当前元素的 children 属性，建立父子关系
      if (children.length > 0) {
        item.children = children;
      }
      // 将当前元素 item 添加到 res 数组中，表示它是树中的一个节点
      res.push(item);
    }
    return res;
  }, []);
}

const treeData = buildTree(flatData);
console.log(treeData)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

buildTree 函数使用 reduce 方法递归地构建了树形结构。它从顶层节点开始，遍历一维数组，查找与当前父节点匹配的子节点，并递归地构建它们的子树。最终，它返回一个包含树形结构的数组，其中每个节点都包含一个 children 属性，其中包含其子节点。

hash 表

通过构建一个哈希表来管理父子关系，然后将节点逐个添加到树中。使用哈希表引用关系是一种有效的方法，可以将一维数组转换为树形结构。代码如下：

function convertToTree(data) {
  const idMapping = {};
   
  data.forEach(item => {
  	// 使用 id 作为 key, item 作为 value 存储在 idMapping 
    idMapping[item.id] = { ...item, children: [] };
  });

  // 创建了根节点对象 root
  const root = { id: null, children: [] };

  data.forEach(item => {
  	// 一个顶级元素，将其添加到根节点的 children 数组中
    if (item.parentId === null) {
      root.children.push(idMapping[item.id]);
    } else {
      // 将其添加到相应的父元素的"children"数组中
      idMapping[item.parentId].children.push(idMapping[item.id]);
    }
  });

  // 返回根节点的"children"数组，其中包含了整个树的顶级元素。
  return root.children;
}

const treeData = convertToTree(flatData);
console.log(JSON.stringify(treeData, null, 2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

首先创建了一个哈希表 idMapping，用于存储每个节点的引用，同时为每个节点添加一个空的 children 数组。然后遍历一维数组，将每个节点添加到其父节点的 children 数组中，最终返回树的根节点。

这种方法非常高效，因为它只需要一次遍历一维数组，并使用哈希表来快速查找父节点和子节点之间的关系。你可以根据需要对节点对象的属性进行调整。

代码优化

const arrayToTree = (arr, rootId) => {
  const map = {};

  // 首先为每个节点创建一个空的 children 数组
  arr.forEach(item => {
    item.children = [];
    // 使用 id 作为 key，item 作为 value 存储在 map
    map[item.id] = item;
  });

  for (const item of arr) {
  	// 查找父节点，并将当前元素添加到父节点的 children 属性中，从而建立父子关系
    const parent = map[item.parentId];
    if (parent) {
      parent.children.push(item);
    }
  }
  // 返回根节点
  return map[rootId];
};

console.log(arrayToTree(flatData, 1), null, 2));
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

arrayToTree 函数接受两个参数：arr 代表扁平数组，rootId 代表树的根节点的 id，将一个包含父子关系信息的扁平数组转换为树形结构，同时可以指定树的根节点（通过rootId参数）。