JavaScript 處理樹結(jié)構(gòu)數(shù)據(jù)
場景
即便在前端，也有很多時(shí)候需要操作 樹結(jié)構(gòu) 的情況，最典型的場景莫過于 無限級(jí)分類。之前吾輩曾經(jīng)遇到過這種場景，但當(dāng)時(shí)沒有多想直接手撕 JavaScript 列表轉(zhuǎn)樹了，并沒有想到進(jìn)行封裝。后來遇到的場景多了，想到如何封裝樹結(jié)構(gòu)操作，但考慮到不同場景的樹節(jié)點(diǎn)結(jié)構(gòu)的不同，就沒有繼續(xù)進(jìn)行下去了。
直到吾輩開始經(jīng)常運(yùn)用了 ES6 Proxy 之后，吾輩想到了新的解決方案！
思考
問: 之前為什么停止封裝樹結(jié)構(gòu)操作了？
答: 因?yàn)椴煌臉浣Y(jié)構(gòu)節(jié)點(diǎn)可能有不同的結(jié)構(gòu)，例如某個(gè)項(xiàng)目的樹節(jié)點(diǎn)父節(jié)點(diǎn) id 字段是 parent，而另一個(gè)項(xiàng)目則是 parentId
問: Proxy 如何解決這個(gè)問題呢？
答: Proxy 可以攔截對(duì)象的操作，當(dāng)訪問對(duì)象不存在的字段時(shí)，Proxy 能將之代理到已經(jīng)存在的字段上
問: 這點(diǎn)意味著什么？
答: 它意味著 Proxy 能夠抹平不同的樹節(jié)點(diǎn)結(jié)構(gòu)之間的差異！
問: 我還是不太明白 Proxy 怎么用，能舉個(gè)具體的例子么？
答: 當(dāng)然可以，我現(xiàn)在就讓你看看 Proxy 的能力
下面思考一下如何在同一個(gè)函數(shù)中處理這兩種樹節(jié)點(diǎn)結(jié)構(gòu)
/**
* 系統(tǒng)菜單
*/
class SysMenu {
/**
* 構(gòu)造函數(shù)
* @param {Number} id 菜單 id
* @param {String} name 顯示的名稱
* @param {Number} parent 父級(jí)菜單 id
*/
constructor(id, name, parent) {
this.id = id
this.name = name
this.parent = parent
}
}
/**
* 系統(tǒng)權(quán)限
*/
class SysPermission {
/**
* 構(gòu)造函數(shù)
* @param {String} uid 系統(tǒng)唯一 uuid
* @param {String} label 顯示的菜單名
* @param {String} parentId 父級(jí)權(quán)限 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
定義橋接函數(shù)
現(xiàn)在，差異確實(shí)抹平了，我們可以通過訪問相同的屬性來獲取到不同結(jié)構(gòu)對(duì)象的值！然而，每個(gè)對(duì)象都寫一次代理終究有點(diǎn)麻煩，所以我們實(shí)現(xiàn)一個(gè)通用函數(shù)用以包裝。
/**
* 橋接對(duì)象不存在的字段
* @param {Object} map 代理的字段映射 Map
* @returns {Function} 轉(zhuǎn)換一個(gè)對(duì)象為代理對(duì)象
*/
export function bridge(map) {
/**
* 為對(duì)象添加代理的函數(shù)
* @param {Object} obj 任何對(duì)象
* @returns {Proxy} 代理后的對(duì)象
*/
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
},
})
}
}
現(xiàn)在，我們可以用更簡單的方式來做代理了。
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
定義標(biāo)準(zhǔn)樹結(jié)構(gòu)
想要抹平差異，我們至少還需要一個(gè)標(biāo)準(zhǔn)的樹結(jié)構(gòu)，告訴別人我們需要什么樣的樹節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，以便于在之后處理樹節(jié)點(diǎn)的函數(shù)中統(tǒng)一使用。
/**
* 基本的 Node 節(jié)點(diǎn)結(jié)構(gòu)定義接口
* @interface
*/
export class INode {
/**
* 構(gòu)造函數(shù)
* @param {Object} [options] 可選項(xiàng)參數(shù)
* @param {String} [options.id] 樹結(jié)點(diǎn)的 id 屬性名
* @param {String} [options.parentId] 樹結(jié)點(diǎn)的父節(jié)點(diǎn) id 屬性名
* @param {String} [options.child] 樹結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組屬性名
* @param {String} [options.path] 樹結(jié)點(diǎn)的全路徑屬性名
* @param {Array.<Object>} [options.args] 其他參數(shù)
*/
constructor({ id, parentId, child, path, ...args } = {}) {
/**
* @field 樹結(jié)點(diǎn)的 id 屬性名
*/
this.id = id
/**
* @field 樹結(jié)點(diǎn)的父節(jié)點(diǎn) id 屬性名
*/
this.parentId = parentId
/**
* @field 樹結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組屬性名
*/
this.child = child
/**
* @field 樹結(jié)點(diǎn)的全路徑屬性名
*/
this.path = path
Object.assign(this, args)
}
}
實(shí)現(xiàn)列表轉(zhuǎn)樹
列表轉(zhuǎn)樹，除了遞歸之外，也可以使用循環(huán)實(shí)現(xiàn)，這里便以循環(huán)為示例。
思路
/**
* 將列表轉(zhuǎn)換為樹節(jié)點(diǎn)
* 注：該函數(shù)默認(rèn)樹的根節(jié)點(diǎn)只有一個(gè)，如果有多個(gè)，則返回一個(gè)數(shù)組
* @param {Array.<Object>} list 樹節(jié)點(diǎn)列表
* @param {Object} [options] 其他選項(xiàng)
* @param {Function} [options.isRoot] 判斷節(jié)點(diǎn)是否為根節(jié)點(diǎn)。默認(rèn)根節(jié)點(diǎn)的父節(jié)點(diǎn)為空
* @param {Function} [options.bridge=returnItself] 橋接函數(shù)，默認(rèn)返回自身
* @returns {Object|Array.<String>} 樹節(jié)點(diǎn)，或是樹節(jié)點(diǎn)列表
*/
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
}, [])
// 根據(jù)頂級(jí)節(jié)點(diǎn)的數(shù)量決定如何返回
const len = res.length
if (len === 0) return {}
if (len === 1) return res[0]
return res
}
抽取通用的樹結(jié)構(gòu)遍歷邏輯
首先，明確一點(diǎn)，樹結(jié)構(gòu)的完全遍歷是通用的，大致實(shí)現(xiàn)基本如下
/**
* 返回第一個(gè)參數(shù)的函數(shù)
* 注：一般可以當(dāng)作返回參數(shù)自身的函數(shù)，如果你只關(guān)注第一個(gè)參數(shù)的話
* @param {Object} obj 任何對(duì)象
* @returns {Object} 傳入的第一個(gè)參數(shù)
*/
export function returnItself(obj) {
return obj
}
/**
* 遍歷并映射一棵樹的每個(gè)節(jié)點(diǎn)
* @param {Object} root 樹節(jié)點(diǎn)
* @param {Object} [options] 其他選項(xiàng)
* @param {Function} [options.before=returnItself] 遍歷子節(jié)點(diǎn)之前的操作。默認(rèn)返回自身
* @param {Function} [options.after=returnItself] 遍歷子節(jié)點(diǎn)之后的操作。默認(rèn)返回自身
* @param {Function} [options.paramFn=(node, args) => []] 遞歸的參數(shù)生成函數(shù)。默認(rèn)返回一個(gè)空數(shù)組
* @returns {INode} 遞歸遍歷后的樹節(jié)點(diǎn)
*/
export function treeMapping(
root,
{
before = returnItself,
after = returnItself,
paramFn = (node, ...args) => [],
} = {},
) {
/**
* 遍歷一顆完整的樹
* @param {INode} node 要遍歷的樹節(jié)點(diǎn)
* @param {...Object} [args] 每次遞歸遍歷時(shí)的參數(shù)
*/
function _treeMapping(node, ...args) {
// 之前的操作
let _node = before(node, ...args)
const childs = _node.child
if (arrayValidator.isEmpty(childs)) {
return _node
}
// 產(chǎn)生一個(gè)參數(shù)
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 }],
},
],
}
// 橋接函數(shù)
const bridge = bridge({
id: 'uid',
parentId: 'parent',
child: 'childrens',
})
treeMapping(tree, {
// 進(jìn)行橋接抹平差異
before: bridge,
// 之后打印每一個(gè)
after(node) {
console.log(node)
},
})
實(shí)現(xiàn)樹轉(zhuǎn)列表
當(dāng)然，我們亦可使用 treeMapping 簡單的實(shí)現(xiàn) treeToList，當(dāng)然，這里考慮了是否計(jì)算全路徑，畢竟還是要考慮性能的！
/**
* 將樹節(jié)點(diǎn)轉(zhuǎn)為樹節(jié)點(diǎn)列表
* @param {Object} root 樹節(jié)點(diǎn)
* @param {Object} [options] 其他選項(xiàng)
* @param {Boolean} [options.calcPath=false] 是否計(jì)算節(jié)點(diǎn)全路徑，默認(rèn)為 false
* @param {Function} [options.bridge=returnItself] 橋接函數(shù)，默認(rèn)返回自身
* @returns {Array.<Object>} 樹節(jié)點(diǎn)列表
*/
export function treeToList(
root,
{ calcPath = false, bridge = returnItself } = {},
) {
const res = []
treeMapping(root, {
before(_node, parentPath) {
const node = bridge(_node)
// 是否計(jì)算全路徑
if (calcPath) {
node.path = (parentPath ? parentPath + ',' : '') + node.id
}
// 此時(shí)追加到數(shù)組中
res.push(node)
return node
},
paramFn: node => (calcPath ? [node.path] : []),
})
return res
}
現(xiàn)在，我們可以轉(zhuǎn)換任意樹結(jié)構(gòu)為列表了
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)
總結(jié)
那么，JavaScript 中處理樹結(jié)構(gòu)數(shù)據(jù)就到這里了。當(dāng)然，樹結(jié)構(gòu)數(shù)據(jù)還有其他的更多操作尚未實(shí)現(xiàn)，例如常見的查詢子節(jié)點(diǎn)列表，節(jié)點(diǎn)過濾，最短路徑查找等等。但目前列表與樹的轉(zhuǎn)換才是最常用的，而且其他操作基本上也是基于它們做的，所以這里也便點(diǎn)到為止了。
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com
Copyright ? 2019-2025 51dongshi.com 版權(quán)所有
違法及侵權(quán)請(qǐng)聯(lián)系：TEL:177 7030 7066 E-MAIL:11247931@qq.com 本站由北京市萬商天勤律師事務(wù)所王興未律師提供法律服務(wù)
