JavaScript 处理树数据结构的方法示例
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 中处理树结构数据就到这里了。当然,树结构数据还有其他的更多操作尚未实现,例如常见的查询子节点列表,节点过滤,最短路径查找等等。但目前列表与树的转换才是最常用的,而且其他操作基本上也是基于它们做的,所以这里也便点到为止了。
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持。
上一篇: svg动画实例解析
推荐阅读