JavaScript 处理树结构数据
场景
即便在前端，也有很多时候需要操作 树结构 的情况，最典型的场景莫过于 无限级分类。之前吾辈曾经遇到过这种场景，但当时没有多想直接手撕 JavaScript 列表转树了，并没有想到进行封装。后来遇到的场景多了，想到如何封装树结构操作，但考虑到不同场景的树节点结构的不同，就没有继续进行下去了。
直到吾辈开始经常运用了 ES6 Proxy 之后，吾辈想到了新的解决方案！
思考
问: 之前为什么停止封装树结构操作了？
答: 因为不同的树结构节点可能有不同的结构，例如某个项目的树节点父节点 id 字段是 parent，而另一个项目则是 parentId
问: Proxy 如何解决这个问题呢？
答: Proxy 可以拦截对象的操作，当访问对象不存在的字段时，Proxy 能将之代理到已经存在的字段上
问: 这点意味着什么？
答: 它意味着 Proxy 能够抹平不同的树节点结构之间的差异！
问: 我还是不太明白 Proxy 怎么用，能举个具体的例子么？
答: 当然可以，我现在就让你看看 Proxy 的能力
下面思考一下如何在同一个函数中处理这两种树节点结构
/**
* 系统菜单
*/
class SysMenu {
/**
* 构造函数
* @param {Number} id 菜单 id
* @param {String} name 显示的名称
* @param {Number} parent 父级菜单 id
*/
constructor(id, name, parent) {
this.id = id
this.name = name
this.parent = parent
}
}
/**
* 系统权限
*/
class SysPermission {
/**
* 构造函数
* @param {String} uid 系统唯一 uuid
* @param {String} label 显示的菜单名
* @param {String} parentId 父级权限 uid
*/
constructor(uid, label, parentId) {
this.uid = uid
this.label = label
this.parentId = parentId
}
}
下面让我们使用 Proxy 来抹平访问它们之间的差异
const sysMenuMap = new Map().set('parentId', 'parent')
const sysMenu = new Proxy(new SysMenu(1, 'rx', 0), {
get(_, k) {
if (sysMenuMap.has(k)) {
return Reflect.get(_, sysMenuMap.get(k))
}
return Reflect.get(_, k)
},
})
console.log(sysMenu.id, sysMenu.name, sysMenu.parentId) // 1 'rx' 0
const sysPermissionMap = new Map().set('id', 'uid').set('name', 'label')
const sysPermission = new Proxy(new SysPermission(1, 'rx', 0), {
get(_, k) {
if (sysPermissionMap.has(k)) {
return Reflect.get(_, sysPermissionMap.get(k))
}
return Reflect.get(_, k)
},
})
console.log(sysPermission.id, sysPermission.name, sysPermission.parentId) // 1 'rx' 0
定义桥接函数
现在，差异确实抹平了，我们可以通过访问相同的属性来获取到不同结构对象的值！然而，每个对象都写一次代理终究有点麻烦，所以我们实现一个通用函数用以包装。
/**
* 桥接对象不存在的字段
* @param {Object} map 代理的字段映射 Map
* @returns {Function} 转换一个对象为代理对象
*/
export function bridge(map) {
/**
* 为对象添加代理的函数
* @param {Object} obj 任何对象
* @returns {Proxy} 代理后的对象
*/
return function(obj) {
return new Proxy(obj, {
get(target, k) {
if (Reflect.has(map, k)) {
return Reflect.get(target, Reflect.get(map, k))
}
return Reflect.get(target, k)
},
set(target, k, v) {
if (Reflect.has(map, k)) {
Reflect.set(target, Reflect.get(map, k), v)
return true
}
Reflect.set(target, k, v)
return true
},
})
}
}
现在，我们可以用更简单的方式来做代理了。
const sysMenu = bridge({
parentId: 'parent',
})(new SysMenu(1, 'rx', 0))
console.log(sysMenu.id, sysMenu.name, sysMenu.parentId) // 1 'rx' 0
const sysPermission = bridge({
id: 'uid',
name: 'label',
})(new SysPermission(1, 'rx', 0))
console.log(sysPermission.id, sysPermission.name, sysPermission.parentId) // 1 'rx' 0
定义标准树结构
想要抹平差异，我们至少还需要一个标准的树结构，告诉别人我们需要什么样的树节点数据结构，以便于在之后处理树节点的函数中统一使用。
/**
* 基本的 Node 节点结构定义接口
* @interface
*/
export class INode {
/**
* 构造函数
* @param {Object} [options] 可选项参数
* @param {String} [options.id] 树结点的 id 属性名
* @param {String} [options.parentId] 树结点的父节点 id 属性名
* @param {String} [options.child] 树结点的子节点数组属性名
* @param {String} [options.path] 树结点的全路径属性名
* @param {Array.<Object>} [options.args] 其他参数
*/
constructor({ id, parentId, child, path, ...args } = {}) {
/**
* @field 树结点的 id 属性名
*/
this.id = id
/**
* @field 树结点的父节点 id 属性名
*/
this.parentId = parentId
/**
* @field 树结点的子节点数组属性名
*/
this.child = child
/**
* @field 树结点的全路径属性名
*/
this.path = path
Object.assign(this, args)
}
}
实现列表转树
列表转树，除了递归之外，也可以使用循环实现，这里便以循环为示例。
思路
/**
* 将列表转换为树节点
* 注：该函数默认树的根节点只有一个，如果有多个，则返回一个数组
* @param {Array.<Object>} list 树节点列表
* @param {Object} [options] 其他选项
* @param {Function} [options.isRoot] 判断节点是否为根节点。默认根节点的父节点为空
* @param {Function} [options.bridge=returnItself] 桥接函数，默认返回自身
* @returns {Object|Array.<String>} 树节点，或是树节点列表
*/
export function listToTree(
list,
{ isRoot = node => !node.parentId, bridge = returnItself } = {},
) {
const res = list.reduce((root, _sub) => {
if (isRoot(sub)) {
root.push(sub)
return root
}
const sub = bridge(_sub)
for (let _parent of list) {
const parent = bridge(_parent)
if (sub.parentId === parent.id) {
parent.child = parent.child || []
parent.child.push(sub)
return root
}
}
return root
}, [])
// 根据顶级节点的数量决定如何返回
const len = res.length
if (len === 0) return {}
if (len === 1) return res[0]
return res
}
抽取通用的树结构遍历逻辑
首先，明确一点，树结构的完全遍历是通用的，大致实现基本如下
/**
* 返回第一个参数的函数
* 注：一般可以当作返回参数自身的函数，如果你只关注第一个参数的话
* @param {Object} obj 任何对象
* @returns {Object} 传入的第一个参数
*/
export function returnItself(obj) {
return obj
}
/**
* 遍历并映射一棵树的每个节点
* @param {Object} root 树节点
* @param {Object} [options] 其他选项
* @param {Function} [options.before=returnItself] 遍历子节点之前的操作。默认返回自身
* @param {Function} [options.after=returnItself] 遍历子节点之后的操作。默认返回自身
* @param {Function} [options.paramFn=(node, args) => []] 递归的参数生成函数。默认返回一个空数组
* @returns {INode} 递归遍历后的树节点
*/
export function treeMapping(
root,
{
before = returnItself,
after = returnItself,
paramFn = (node, ...args) => [],
} = {},
) {
/**
* 遍历一颗完整的树
* @param {INode} node 要遍历的树节点
* @param {...Object} [args] 每次递归遍历时的参数
*/
function _treeMapping(node, ...args) {
// 之前的操作
let _node = before(node, ...args)
const childs = _node.child
if (arrayValidator.isEmpty(childs)) {
return _node
}
// 产生一个参数
const len = childs.length
for (let i = 0; i < len; i++) {
childs[i] = _treeMapping(childs[i], ...paramFn(_node, ...args))
}
// 之后的操作
return after(_node, ...args)
}
return _treeMapping(root)
}
使用 treeMapping 遍历树并打印
const tree = {
uid: 1,
childrens: [
{
uid: 2,
parent: 1,
childrens: [{ uid: 3, parent: 2 }, { uid: 4, parent: 2 }],
},
{
uid: 5,
parent: 1,
childrens: [{ uid: 6, parent: 5 }, { uid: 7, parent: 5 }],
},
],
}
// 桥接函数
const bridge = bridge({
id: 'uid',
parentId: 'parent',
child: 'childrens',
})
treeMapping(tree, {
// 进行桥接抹平差异
before: bridge,
// 之后打印每一个
after(node) {
console.log(node)
},
})
实现树转列表
当然，我们亦可使用 treeMapping 简单的实现 treeToList，当然，这里考虑了是否计算全路径，毕竟还是要考虑性能的！
/**
* 将树节点转为树节点列表
* @param {Object} root 树节点
* @param {Object} [options] 其他选项
* @param {Boolean} [options.calcPath=false] 是否计算节点全路径，默认为 false
* @param {Function} [options.bridge=returnItself] 桥接函数，默认返回自身
* @returns {Array.<Object>} 树节点列表
*/
export function treeToList(
root,
{ calcPath = false, bridge = returnItself } = {},
) {
const res = []
treeMapping(root, {
before(_node, parentPath) {
const node = bridge(_node)
// 是否计算全路径
if (calcPath) {
node.path = (parentPath ? parentPath + ',' : '') + node.id
}
// 此时追加到数组中
res.push(node)
return node
},
paramFn: node => (calcPath ? [node.path] : []),
})
return res
}
现在，我们可以转换任意树结构为列表了
const tree = {
uid: 1,
childrens: [
{
uid: 2,
parent: 1,
childrens: [{ uid: 3, parent: 2 }, { uid: 4, parent: 2 }],
},
{
uid: 5,
parent: 1,
childrens: [{ uid: 6, parent: 5 }, { uid: 7, parent: 5 }],
},
],
}
const fn = bridge({
id: 'uid',
parentId: 'parent',
child: 'childrens',
})
const list = treeToList(tree, {
bridge: fn,
})
console.log(list)
总结
那么，JavaScript 中处理树结构数据就到这里了。当然，树结构数据还有其他的更多操作尚未实现，例如常见的查询子节点列表，节点过滤，最短路径查找等等。但目前列表与树的转换才是最常用的，而且其他操作基本上也是基于它们做的，所以这里也便点到为止了。