TypeScript数组转树

软件发布|下载排行|最新软件

当前位置:首页IT学院IT技术

TypeScript数组转树

诸葛小愚   2022-06-28 我要评论

这段时间重新捡起了数据结构和算法,发现里面的树和图是真的掉头发。本文基于一个面试题,详细分析如何实现数组和树的相互转换。

前言

树或者图是个比较抽象的概念,并不存在这样的数据类型。我们看一下树的结构,一层嵌套一层,同层次可能还会有多个节点,这种结构的数据可以使用{}对象来表示。数组就比较简单了,因此数组和树的转换可以理解为数组和对象之间的转换,只是需要转换的数组和对象都是比较特殊的数据。为了更好的看清楚转换过程,本文采用ts的语法,使用js的话没有类型约束,看起来就更容易晕了。

数组转换为树

我们先来一个简单点的,将数组转换为树。

树.png

结合树,我们看一下数组的结构:BC是A的子节点,DE是B的子节点,F是C的子节点。想要实现这个效果,我们先来捋一下实现思路:

  • 遍历数组
  • 将数组项转换为树的叶子节点,并使用Map来维持id与节点直接的关系,便于快速查找
  • 根据parentId查找到可能存在的父节点,并建立叶子节点和父节点之间的关系
  • 找到根节点,最终返回的也就是根节点

文字描述可能不太具体,我们看一下实现代码:

// 定义数组项的数据类型,包含id、name、parentId基本属性
interface ArrayItem {
  id: number,
  name: string,
  parentId: number
}
// 定义树节点的数据类型,包含id、name、可能存在的子节点
interface TreeNode {
  id: number,
  name: string,
  children?: TreeNode[], // 叶子节点没有子节点
}
function array2Tree(arr: ArrayItem[]): TreeNode | null {
  // 用于id和TreeNode的映射,map<key, value>,可通过id快速查找到树节点,时间复杂度为O(1)
  const treeNode: Map<number, TreeNode> = new Map();
  let root = null; // 树根节点
  arr.forEach(item => {
    const {id, name, parentId} = item; // 解构赋值
    // 定义树节点tree node,并使用Map维持id与节点之间的关系
    const node: TreeNode = {id, name}
    treeNode.set(id, node);
​
    // 使用parentId找出parentNode
    const parentNode = treeNode.get(parentId);
    if (parentNode) {
      if (parentNode.children == null) {
        parentNode.children = [];
      }
      // 找到父节点后,将当前数组项转换的节点添加到子节点列表中
      parentNode.children.push(node)
    }
​
    // 在第一次循环中找到根节点,我们假定id=0的表示根节点
    if (parentId === 0) {
      root = node;
    }
  })
  return root;
}
const tree = array2Tree(arrs); // 需要定义arrs
console.log(tree);

代码是使用ts完成的,清晰的展示了树节点数据类型的定义,在转换过程中数据类型的变化。直接运行ts代码是看不出来打印的结果的,我们可以新建一个vue-ts的项目,或者嫌麻烦的话可以直接使用官网提供的运行环境:playground

实现效果:

其实就是一个对象,对象的层次就像是树一样展开。

树转换为数组

同样也是这个例子,只不过是需要将树转换为数组了。

image-20220622144731183.png

数组和树在数据结构上最大的差异就是树没有parentId的属性,如果一个节点有子节点,那么该节点的id就应该是其子节点的parentId。老规矩,先来捋一下思路:

  • 遍历树节点,使用广度优先。树的遍历可分为广度优先和深度优先,广度优先表示横向遍历,深度优先表示纵向遍历
  • 将遍历出的树节点添加到队列中,实现先进先出。队列并不是js中的数据类型,但是我们可以使用数组来实现队列
  • 将树节点转换为数组项
  • 根据节点的父子关系,设置数组项的parentId,并将数组项添加到数组中
  • 为了查找遍历,可使用Map来维持父节点和子节点的关系

实现代码:

// 定义数据结构
...
function tree2Array(root: TreeNode): ArrayItem[] {
  // 定义子节点和父节点的映射关系,map<子节点,父节点>
  const childToParent: Map<TreeNode, TreeNode> = new Map();

  const arr: ArrayItem[] = []; // 返回的数组

  // 广度优先遍历树,使用队列保存节点
  const queue: TreeNode[] = [];
  queue.unshift(root); // 入队,从头部入队
  while(queue.length) {
    const curNode = queue.pop(); // 出队,从尾部出队,保证先进先出
    if (curNode == null) break; // 循环结束,使用==包括了null和undefined的情况

    const {id, name, children = []} = curNode; // 结构赋值,叶子节点没有children属性,所以默认为空数组

    const parentNode = childToParent.get(curNode); // 获取当前节点的父节点
    const parentId = parentNode?.id || 0; // 获取父节点id,根节点设置为0
    const item = {id, name, parentId}; // 定义数组项
    arr.push(item); // 插入到数组中

    // 继续遍历子节点,并且子节点入队
    children.forEach(child => {
      // 如果有子节点,则把子节点和当前节点通过Map保持关系
      childToParent.set(child, curNode);

      // 入队
      queue.unshift(child);
    })
  }

  return arr;
}
const array = tree2Array(obj); // 这个obj对象就是数组转换为树打印出的结果
console.log(array)

运行结果:

树.png

可以发现,结果符合预期。

总结

总结一下,数组和树之间相互转换一开始还挺蒙的,但是看完代码发现,其实也并不复杂。

  • 数组转换为树:从数组的第一项开始,根据parentId,找到每一项的归属;若找不到,则表示当前数组项为根节点
  • 树转换为数组:树的每一个节点都可能会有很多子节点,按照广度优先,从根节点开始遍历,将每一个节点以及其子节点都添加到队列中,按照先进先出的原则,逐一将节点都转换为数组项并添加到数组中
  • 在实现的过程中,可结合图例,一步一步分析,最终实现结果

Copyright 2022 版权所有 软件发布 访问手机版

声明:所有软件和文章来自软件开发商或者作者 如有异议 请与本站联系 联系我们