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 中处理树结构数据就到这里了。当然，树结构数据还有其他的更多操作尚未实现，例如常见的查询子节点列表，节点过滤，最短路径查找等等。但目前列表与树的转换才是最常用的，而且其他操作基本上也是基于它们做的，所以这里也便点到为止了。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持。