中级算法题：实现数组和树的相互转换（ts版）
theme: fancy
持续创作，加速成长！这是我参与「掘金日新计划 · 6 月更文挑战」的第24天，点击查看活动详情
这段时间重新捡起了数据结构和算法，发现里面的树和图是真的掉头发。本文基于一个面试题，详细分析如何实现数组和树的相互转换。
前言
树或者图是个比较抽象的概念，并不存在这样的数据类型。我们看一下树的结构，一层嵌套一层，同层次可能还会有多个节点，这种结构的数据可以使用{}对象来表示。数组就比较简单了，因此数组和树的转换可以理解为数组和对象之间的转换，只是需要转换的数组和对象都是比较特殊的数据。为了更好的看清楚转换过程，本文采用ts的语法，使用js的话没有类型约束，看起来就更容易晕了。
数组转换为树
我们先来一个简单点的，将数组转换为树。
结合树，我们看一下数组的结构：BC是A的子节点，DE是B的子节点，F是C的子节点。想要实现这个效果，我们先来捋一下实现思路：
- 遍历数组
- 将数组项转换为树的叶子节点，并使用Map来维持id与节点直接的关系，便于快速查找
- 根据parentId查找到可能存在的父节点，并建立叶子节点和父节点之间的关系
- 找到根节点，最终返回的也就是根节点
文字描述可能不太具体，我们看一下实现代码：
ts
// 定义数组项的数据类型，包含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
实现效果：
其实就是一个对象，对象的层次就像是树一样展开。
树转换为数组
同样也是这个例子，只不过是需要将树转换为数组了。
数组和树在数据结构上最大的差异就是树没有parentId的属性，如果一个节点有子节点，那么该节点的id就应该是其子节点的parentId。老规矩，先来捋一下思路：
- 遍历树节点，使用广度优先。树的遍历可分为广度优先和深度优先，广度优先表示横向遍历，深度优先表示纵向遍历
- 将遍历出的树节点添加到队列中，实现先进先出。队列并不是js中的数据类型，但是我们可以使用数组来实现队列
- 将树节点转换为数组项
- 根据节点的父子关系，设置数组项的parentId，并将数组项添加到数组中
- 为了查找遍历，可使用Map来维持父节点和子节点的关系
实现代码:
```ts
// 定义数据结构
...
function tree2Array(root: TreeNode): ArrayItem[] {
// 定义子节点和父节点的映射关系，map<子节点，父节点>
const childToParent: 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) ```
运行结果:
可以发现，结果符合预期。
总结
总结一下，数组和树之间相互转换一开始还挺蒙的，但是看完代码发现，其实也并不复杂。
- 数组转换为树：从数组的第一项开始，根据parentId，找到每一项的归属；若找不到，则表示当前数组项为根节点
- 树转换为数组：树的每一个节点都可能会有很多子节点，按照广度优先，从根节点开始遍历，将每一个节点以及其子节点都添加到队列中，按照先进先出的原则，逐一将节点都转换为数组项并添加到数组中
- 在实现的过程中，可结合图例，一步一步分析，最终实现结果