最新文章专题视频专题问答1问答10问答100问答1000问答2000关键字专题1关键字专题50关键字专题500关键字专题1500TAG最新视频文章推荐1 推荐3 推荐5 推荐7 推荐9 推荐11 推荐13 推荐15 推荐17 推荐19 推荐21 推荐23 推荐25 推荐27 推荐29 推荐31 推荐33 推荐35 推荐37视频文章20视频文章30视频文章40视频文章50视频文章60 视频文章70视频文章80视频文章90视频文章100视频文章120视频文章140 视频2关键字专题关键字专题tag2tag3文章专题文章专题2文章索引1文章索引2文章索引3文章索引4文章索引5123456789101112131415文章专题3
问答文章1 问答文章501 问答文章1001 问答文章1501 问答文章2001 问答文章2501 问答文章3001 问答文章3501 问答文章4001 问答文章4501 问答文章5001 问答文章5501 问答文章6001 问答文章6501 问答文章7001 问答文章7501 问答文章8001 问答文章8501 问答文章9001 问答文章9501
当前位置: 首页 - 科技 - 知识百科 - 正文

JavaScript 处理树数据结构的方法示例

来源:懂视网 责编:小采 时间:2020-11-27 21:55:10
文档

JavaScript 处理树数据结构的方法示例

JavaScript 处理树数据结构的方法示例:JavaScript 处理树结构数据 场景 即便在前端,也有很多时候需要操作 树结构 的情况,最典型的场景莫过于 无限级分类。之前吾辈曾经遇到过这种场景,但当时没有多想直接手撕 JavaScript 列表转树了,并没有想到进行封装。后来遇到的场景多了,想到如何封装树
推荐度:
导读JavaScript 处理树数据结构的方法示例:JavaScript 处理树结构数据 场景 即便在前端,也有很多时候需要操作 树结构 的情况,最典型的场景莫过于 无限级分类。之前吾辈曾经遇到过这种场景,但当时没有多想直接手撕 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)
 }
}

实现列表转树

列表转树,除了递归之外,也可以使用循环实现,这里便以循环为示例。

思路

  1. 在外层遍历子节点
  2. 如果是根节点,就添加到根节点中并不在找其父节点。
  3. 否则在内层循环中找该节点的父节点,找到之后将子节点追加到父节点的子节点列表中,然后结束本次内层循环。
/**
 * 将列表转换为树节点
 * 注:该函数默认树的根节点只有一个,如果有多个,则返回一个数组
 * @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
}

抽取通用的树结构遍历逻辑

首先,明确一点,树结构的完全遍历是通用的,大致实现基本如下

  1. 遍历顶级树节点
  2. 遍历树节点的子节点列表
  3. 递归调用函数并传入子节点
/**
 * 返回第一个参数的函数
 * 注:一般可以当作返回参数自身的函数,如果你只关注第一个参数的话
 * @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 中处理树结构数据就到这里了。当然,树结构数据还有其他的更多操作尚未实现,例如常见的查询子节点列表,节点过滤,最短路径查找等等。但目前列表与树的转换才是最常用的,而且其他操作基本上也是基于它们做的,所以这里也便点到为止了。

声明:本网页内容旨在传播知识,若有侵权等问题请及时与本网联系,我们将在第一时间删除处理。TEL:177 7030 7066 E-MAIL:11247931@qq.com

文档

JavaScript 处理树数据结构的方法示例

JavaScript 处理树数据结构的方法示例:JavaScript 处理树结构数据 场景 即便在前端,也有很多时候需要操作 树结构 的情况,最典型的场景莫过于 无限级分类。之前吾辈曾经遇到过这种场景,但当时没有多想直接手撕 JavaScript 列表转树了,并没有想到进行封装。后来遇到的场景多了,想到如何封装树
推荐度:
标签: 方法 解决 js
  • 热门焦点

最新推荐

猜你喜欢

热门推荐

专题
Top