Skip to content

将平铺数组转为树状结构

面试了十几个高级前端,竟然连(扁平数据结构转Tree)都写不出来 - 掘金

递归调用实现

时间复杂度 O(n^2) ,空间复杂度:O(n^2) 缺点: 不适合大规模数据

javascript
const nodes = [
  { id: 1, name: "Node 1", parentId: null },
  { id: 2, name: "Node 2", parentId: 1 },
  { id: 3, name: "Node 3", parentId: 1 },
  { id: 4, name: "Node 4", parentId: 2 },
  { id: 5, name: "Node 5", parentId: 2 },
  { id: 6, name: "Node 6", parentId: null },
];

// 定义一个函数,用于将数组转换为树状结构
function arrayToTree(array, parentId = null) {
  const tree = [];
  // 如果当前节点的父节点ID等于给定的父节点ID
  array.forEach((item) => {
    if (item.parentId === parentId) {
      // 递归查找当前节点的子节点,并将子节点添加到当前节点的children属性中
      // 这里是递归调用,构建子树 将子树赋值给当前节点的 children 属性
      item.children = arrayToTree(array, item.id);
      // 将当前节点添加到树中
      tree.push(item);
    }
  });
  return tree;
}

//      1      6  
//    2   3
//  4  5 

const res = arrayToTree(nodes);
console.log(res);

递归调用简化版本 filter+map

注意有性能问题

javascript
const arrayToTree = (nodes, parentId = null) => {
  return nodes
    .filter((node) => node.parentId === parentId)
    .map((node) => ({
      ...node,
      children: arrayToTree(nodes, node.id),
    }));
};
const tree = arrayToTree(nodes, null);
console.log(tree);
// 1. 使用 filter 方法筛选出所有具有指定父节点 ID 的节点。
// 2. 使用 map 方法对筛选出的节点进行处理。
// 3. 对于每个节点,递归调用 arrayToTree 函数来构建其子树。
// 4. 注意map箭头函数返回一个对象需要加 =>({})括号

使用循环(哈希映射)

时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n) 适合大规模数据

image.png

javascript
const arrayToTree = (array) => {
  const map = {};
  const tree = [];

  // 1. 创建map映射
  array.forEach((item) => {
    // 构建一个map对象,key为节点id,值为原对象每个加上children属性
    map[item.id] = { ...item, children: [] };
  });
  // map结果如上图

  // 2. 遍历节点数组
  array.forEach((item) => {
    if (item.parentId !== null) {
      // 如果当前节点有父节点,将其添加到父节点的子节点数组中
      map[item.parentId].children.push(map[item.id]);
    } else {
// 否则,将其作为根节点添加到最终的树结构中
      tree.push(map[item.id]);
    }
  });

  return tree;
};

const res = arrayToTree(array);
console.log(res);

for of简化一点点

javascript
function arrayToTreeLoop(nodes) {
  const map = {};
  const tree = [];

  for (const node of nodes) {
    map[node.id] = { ...node, children: [] };
  }

  // Object.values获取对象的所有属性值,返回数组
  for (const node of Object.values(map)) {
    if (node.parentId === null) {
      tree.push(node);
    } else {
      map[node.parentId].children.push(node);
    }
  }

  return tree;
}

const tree = arrayToTreeLoop(nodes);

使用reduce

javascript
function arrayToTreeReduce(nodes) {
  // 1. 构建map结构,注意这步的map构建不能放在reduce中写
  const map = {};
  for (const node of nodes) {
    map[node.id] = { ...node, children: [] };
  }

  // 2. reduce遍历,其实和前面一样的
  const tree = nodes.reduce((acc, node) => {
    // map[node.id] = { ...node, children: [] };
    // 这里写map会有问题,Error
    // 如果颠倒pid顺序 map未构建出来,children取不到报错
    if (node.parentId === null) {
      acc.push(map[node.id]);
    } else {
      map[node.parentId].children.push(map[node.id]);
    }

    return acc;
  }, []);

  return tree;
}

const tree = arrayToTreeReduce(nodes);

console.log(tree);
javascript
//  颠倒顺序是指:
const nodes = [
  { id: 1, name: "Node 1", parentId: null },
  // id为4,pid2放在前面,这时候map还未完全构建好
  { id: 4, name: "Node 4", parentId: 2 },
  { id: 2, name: "Node 2", parentId: 1 },
  { id: 3, name: "Node 3", parentId: 1 },
  { id: 5, name: "Node 5", parentId: 2 },
  { id: 6, name: "Node 6", parentId: null },
];

哈希表 new Map 最优解!!

时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 适合大规模数据,而且由于使用了 Map,能够更方便地进行节点的查找和删除。

javascript
const map = new Map([
  ['name', '张三'],
  ['title', 'Author']
]);
// 新建map对象,成员是双元素数组
javascript
function arrayToTreeMap(nodes) {
  // 将数组转为map对象
  const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
  const tree = [];

  // map.values()返回键值
  // map.get(key) 读取key对应的键值
  for (const node of map.values()) {
    if (node.parentId === null) {
      tree.push(node);
    } else {
      map.get(node.parentId).children.push(node);
    }
  }
  return tree;
}

const tree = arrayToTreeMap(nodes);

使用深度优先搜索

时间复杂度:O(n),其中 n 是节点的数量。 空间复杂度:O(n)。 优缺点:相比于方法二、方法三和方法四,可以更方便地进行深度优先搜索。

javascript
function arrayToTreeDFS(nodes) {
  const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
  const tree = [];
  for (const node of map.values()) {
    if (node.parentId === null) {
      dfs(node, tree);
    }
  }
  function dfs(node, parent) {
    if (parent) {
      parent.children.push(node);
    }
    for (const child of node.children) {
      dfs(map.get(child.id), node);
    }
  }
  return tree;
}
const tree = arrayToTreeDFS(nodes);

使用深度优先搜索(DFS)的方式来实现数组转换为树的方法。它基于递归地遍历树的节点,将每个节点添加到其父节点的 children 数组中。 下面是简要说明:

  1. 首先,通过 nodes.map() 方法创建一个 Map 对象,其中键是节点的 id,值是节点对象,包括 children 属性,初始为空数组。
  2. 然后,遍历 Map 中的每个节点对象。对于每个节点,如果它是树的根节点(即 parentIdnull),则调用 dfs() 函数进行深度优先搜索。
  3. dfs() 函数中,将当前节点添加到其父节点的 children 数组中,并递归调用 dfs() 函数处理当前节点的子节点。
  4. 最后,返回树结构。

这种实现方式利用了深度优先搜索的特性,在遍历树的过程中直接进行了节点的组织,从而构建出树状结构。 如果nodes 数组是事先按照节点的父子关系顺序排列的,那么这种方式会是一个非常高效的方法。

树形结构扁平化

要将树形结构扁平化,可以使用深度优先搜索(DFS)或广度优先搜索(BFS)来遍历树的节点,并将每个节点添加到一个数组中。

深度优先搜索(DFS)

javascript
function treeToArray(tree) {
  let res = []
  for (const item of tree) {
    // 使用解构将children属性剔除
    const { children, ...i } = item
    if (children && children.length) {
      // 递归调用
      res = res.concat(treeToArray(children))
    }
    res.push(i)
  }
  return res
}
  1. 定义了一个 treeToArray 函数,它接受一个树形结构作为参数,并返回一个数组。
  2. 使用 for...of 循环遍历树中的每个节点。
  3. 对于每个节点,使用解构赋值将其 children 属性剔除,因为我们只需要节点本身的数据,而不需要子节点的信息。
  4. 如果当前节点有子节点(即 children 存在且不为空数组),则递归调用 treeToArray 函数来处理子节点,并将结果与当前节点的数据合并。
  5. 将处理后的当前节点数据添加到结果数组中。
  6. 最后返回结果数组。

reduce实现,简洁一点

javascript
function treeToArray(tree) {
  return tree.reduce((res, item) => {
    const { children, ...i } = item
    return res.concat(i, children && children.length ? treeToArray(children) : [])
  }, [])
}

广度优先搜索(BFS)

我们使用一个队列来按层级顺序迭代树的节点。对于每个节点,我们首先将其从队列中取出并添加到结果数组中,然后将其子节点依次添加到队列中。

javascript
function flattenTreeBFS(tree) {
    const flattened = [];
    const queue = [...tree];

    while (queue.length > 0) {
        const node = queue.shift();
        // 剔除当前节点的 children 属性,只保留节点数据
        const { children, ...data } = node; 
        // 将节点数据添加到结果数组中
        flattened.push(data);
        if (children && children.length) {
            queue.push(...children); // 将子节点依次添加到队列末尾中
        }
    }

    return flattened;
}

// 当然用栈结构也可以实现

按照层级顺序依次处理每个节点及其子节点。 在每次循环迭代中,我们从队列中取出一个节点,将其数据(不包含子节点)添加到结果数组中。然后,如果当前节点有子节点,就将子节点依次添加到队列末尾。这样,通过不断地从队列中取出节点并处理,直到队列为空,我们就完成了树形结构的扁平化。

typescript
// 使用哈希表 最优解!
const arrayToTree = (array) => {
  const tree = [];
  // 将原数组转为map对象,key为id,value为对象
  const map = new Map(
    array.map((item) => [item.id, { ...item, children: [] }])
  );

  for (const item of map.values()) {
    // 根节点
    if (item.parentId === null) {
      tree.push(item);
    } else {
      map.get(item.parentId).children.push(item);
    }
  }
  return tree;
};