JavaScript实现扁平数组与树结构的相互转换

扁平数组转为树结构

题目描述:

给定以下数据格式的扁平数组:

const flatArray = [
  { id: 1, parentId: null, name: 'root1' },
  { id: 2, parentId: 1, name: 'child1' },
  { id: 3, parentId: 1, name: 'child2' },
  { id: 4, parentId: 2, name: 'grandchild1' },
  { id: 5, parentId: 3, name: 'grandchild2' },
];

你需要将其转换为以下树状结构:

const tree = [
    {
        "id": 1,
        "parentId": null,
        "name": "root1",
        "children": [
            {
                "id": 2,
                "parentId": 1,
                "name": "child1",
                "children": [
                    {
                        "id": 4,
                        "parentId": 2,
                        "name": "grandchild1",
                        "children": []
                    }
                ]
            },
            {
                "id": 3,
                "parentId": 1,
                "name": "child2",
                "children": [
                    {
                        "id": 5,
                        "parentId": 3,
                        "name": "grandchild2",
                        "children": []
                    }
                ]
            }
        ]
    }
];

请编写一个名为 flatArrayToTree 的函数,接受上述类型的扁平数组作为参数,并返回相应的树状结构数组。

方案一:使用Map和递归

function flatArrayToTree(flatArray) {
  // 创建一个映射,方便通过id查找节点
  const map = new Map();
  flatArray.forEach(item => {
    map.set(item.id, { ...item, children: [] });
  });

  // 定义一个递归函数,用于构建每个节点的子树
  function buildTree(node) {
    flatArray.forEach(item => {
      if (item.parentId === node.id) {
        const childNode = map.get(item.id);
        // 递归构建子树,并添加到当前节点的children中
        node.children.push(buildTree(childNode)); 
      }
    });
    return node;
  }

  // 过滤出根节点并递归构建整棵树
  return flatArray
    .filter(item => item.parentId === null)
    .map(rootNode => buildTree(map.get(rootNode.id)));
}

const tree = flatArrayToTree(flatArray);

方案一解释

首先,我们创建一个 Map 来存储每个节点及其子节点列表。
接着定义一个递归函数 buildTree 用于构建父子关系。遍历扁平数组时,对于每个节点,将其添加到 Map 中并初始化其 children 属性为空数组。对于有 parentId 的节点,将其添加到相应父节点的 children 数组中。
最后从 Map 中提取 parentIdnull的节点形成结果数组。

方案二:使用对象作为索引和循环

function flatArrayToTree(flatData) {
  const result = [];
  const map = {};

  // 先构建一个id映射表
  flatData.forEach(item => {
    map[item.id] = { ...item, children: [] };
  });

  // 然后根据parentId将子节点添加到父节点的children属性下
  flatData.forEach(item => {
    if (item.parentId !== null) {
      map[item.parentId].children.push(map[item.id]);
    } else {
      result.push(map[item.id]);
    }
  });

  return result;
}

const tree = flatArrayToTree(flatArray);

方案二解释

首先遍历扁平数组,创建一个键值对形式的哈希表,键是每个元素的 id,值是该元素本身。这样我们可以快速通过 id 找到对应的节点。
再次遍历扁平数组,对于每个元素,检查其 parentId 是否存在于哈希表中。如果存在,说明找到了其父节点,将当前元素添加到其父节点的 children 数组中。若不存在 parentId(即为根节点),则直接添加到结果数组中。
最终得到的结果数组就是所求的树形结构。

最深层级

在构建树结构的时候,如果需要记录最深层级,应该怎么做呢?下面是可以记录最深层级的方案:

function flatArrayToTree(flatData) {
  let maxDepth = 0;

  const result = [];
  const map = {};

  // 先构建一个id映射表
  flatData.forEach(item => {
    map[item.id] = { ...item, children: [], depth: 0 };
  });

  // 然后根据parentId将子节点添加到父节点的children属性下,并计算深度
  flatData.forEach(item => {
    if (item.parentId !== null) {
      const parent = map[item.parentId];
      parent.children.push(map[item.id]);

      // 更新当前节点及其父节点的深度
      let currentDepth = parent.depth + 1;
      map[item.id].depth = currentDepth;

      // 更新最大深度
      maxDepth = Math.max(maxDepth, currentDepth);
    } else {
      result.push(map[item.id]);
    }
  });

  return { tree: result, maxDepth };
}

const { tree, maxDepth } = flatArrayToTree(flatArray);
console.log('Tree:', tree);
console.log('Max Depth:', maxDepth);

增加 maxDepth 变量记录最大深度,在每次将子节点添加到父节点的 children 属性下时,记录层级,计算深度。

树结构转扁平数组

以上是扁平数组转为树结构的情况,下面来看针对已有的树形结构,将其转换回扁平数组的情况。

实现

function treeToArray(treeNodes) {
  let result = [];

  //递归函数 traverse,用于处理单个节点
  function traverse(node) {
    const newNode = { ...node };
    delete newNode.children;
    // 将没有子节点的新节点添加到结果数组中
    result.push(newNode);

    // 如果当前节点包含 children 属性(即有子节点)
    if (node.children) {
      node.children.forEach(traverse);
    }
  }

  treeNodes.forEach(traverse);

  return result;
}

const flatArray = treeToArray(tree);

解释

首先定义了一个 treeToArray 函数,该函数内部定义了一个名为 traverse 的递归函数,用于遍历树形结构的每一个节点并将节点添加到扁平数组中。
然后遍历输入的树形结构,对每个节点调用 traverse 函数。在 traverse 函数内部,如果当前节点有子节点,则对其每个子节点进行同样的遍历操作。
最后返回扁平数组。

总结

在解决扁平数组与树结构之间的转换问题时,关键在于识别父子关系并通过建立索引或映射结构进行层次遍历,以实现数据的转换。
在实际业务中,扁平数组与树结构的转化,常见在目录树组件,级联选择组件等情况。

原文链接:https://juejin.cn/post/7354632375446126619 作者:FEWY

(0)
上一篇 2024年4月7日 下午5:10
下一篇 2024年4月8日 上午10:00

相关推荐

发表回复

登录后才能评论