likes
comments
collection
share

js多维数组结构和Tree结构的互相转换

作者站长头像
站长
· 阅读数 39

引言

JavaScript中的多维数组和树结构是常用的数据结构之一，在处理各种问题时都有广泛的应用。多维数组是由一个或多个数组嵌套而成的数据结构，而树结构则由一个根节点和零个或多个子节点组成。在实际开发中，我们可能需要将多维数组转换为树结构，也可能需要将树结构转换为多维数组。本文将介绍如何使用 JavaScript 实现多维数组和树结构之间的互相转换

多维数组结构转换为Tree结构

  • 多维数组结构转换为树形结构可以使用Map数据结构和递归的方式来实现
function arrayToTree(arr) {
  const map = new Map();
  const roots = [];
  for (let i = 0; i < arr.length; i++) {
    const node = arr[i];
    node.children = [];
    map.set(node.id, node);
    if (!node.parentId) {
      roots.push(node);
    } else {
      const parent = map.get(node.parentId);
      parent.children.push(node);
    }
  }
  return roots;
}
  • 我们首先创建一个Map数据结构用于保存节点信息。然后，我们遍历多维数组中的每一个节点，将节点信息保存到Map中，并查找该节点的父节点，如果父节点存在则将当前节点添加到父节点的children数组中，否则将当前节点添加到根节点数组中。
  • 这里假设多维数组结构中每个节点都有一个唯一的id属性和一个parentId属性，parentId为null表示该节点为根节点，否则表示该节点的父节点为对应的parentId。如果数组中有多个根节点，需要对这些节点进行特殊处理。
  • 时间复杂度分析：
    • 对于每一个节点，我们需要将其添加到Map数据结构中，并查找其父节点。由于Map数据结构的查找操作的时间复杂度为 O(1)O(1)O(1)，因此对于 n 个节点，总的时间复杂度为 O(n)O(n)O(n)。
  • 空间复杂度分析：
    • 在函数中，我们使用了一个Map数据结构和一个roots数组来保存节点信息。其中Map数据结构的空间复杂度为 O(n)O(n)O(n)，因为我们需要保存每一个节点的信息，roots数组的空间复杂度为 O(r)O(r)O(r)，其中 r 表示根节点的数量。因此，总的空间复杂度为 O(n+r)O(n+r)O(n+r)。需要注意的是，由于在递归过程中我们没有使用额外的空间来保存节点信息，因此函数的空间复杂度为 O(1)O(1)O(1)。但是，在整个递归过程中我们需要多次调用该函数，并且每次调用都会创建新的Map数据结构和roots数组，因此总的空间复杂度为 O(n+r)O(n+r)O(n+r)。由于树的深度可能会非常大，因此在实际使用中可能需要进行优化，比如在遍历树的过程中使用迭代的方式代替递归，或者使用其他的数据结构来保存节点信息。

Tree结构数据转换为一维数组结构，每条数据包含完整路径

  • Tree结构转换为一维数组结构，每条数据包含完整路径，可以使用迭代的方式来实现
function treeToArray(tree) {
  const result = [];
  const stack = [{ node: tree, path: [] }];

  while (stack.length > 0) {
    const { node, path } = stack.pop();
    const newPath = path.concat(node.name);

    if (node.children.length === 0) {
      result.push({ name: node.name, path: newPath });
    } else {
      for (let i = node.children.length - 1; i >= 0; i--) {
        stack.push({ node: node.children[i], path: newPath });
      }
    }
  }

  return result;
}
  • 我们使用了一个栈来保存节点信息。首先，将根节点压入栈中。然后，重复以下步骤，直到栈为空：
    1. 从栈中弹出一个节点。
    2. 计算当前节点的完整路径newPath，将其与节点名称一起保存到结果数组中。
    3. 如果当前节点有子节点，则将每一个子节点按相反的顺序压入栈中。
  • 通过使用迭代的方式，我们避免了递归所带来的额外空间开销，同时也避免了使用递归带来的函数调用开销，从而使得时间复杂度和空间复杂度都达到了最优，时间复杂度为O(n)O(n)O(n)，其中 n 表示树形结构中节点的数量，空间复杂度为O(1)O(1)O(1)。

Tree结构数据转换为多维数组结构

  • 可以使用深度优先搜索（DFS）算法将树结构转换为多维数组结构
function treeToArray(tree) {
  const result = [];
  const dfs = (node, level) => {
    if (!result[level]) {
      result[level] = [];
    }
    result[level].push(node.value);
    if (node.children && node.children.length > 0) {
      node.children.forEach(child => {
        dfs(child, level + 1);
      });
    }
  };
  dfs(tree, 0);
  return result;
}
  • 时间复杂度为 O(n)O(n)O(n)，其中 nnn 是树中节点的个数，因为需要遍历每个节点一次。空间复杂度为 O(h)O(h)O(h)，其中 hhh 是树的高度，因为需要存储每个深度上的节点值。
转载自:https://juejin.cn/post/7217773631370461221
评论
请登录