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' 0const 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' 0const 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 中處理樹結構數據就到這里了。當然，樹結構數據還有其他的更多操作尚未實現，例如常見的查詢子節點列表，節點過濾，最短路徑查找等等。但目前列表與樹的轉換才是最常用的，而且其他操作基本上也是基于它們做的，所以這里也便點到為止了。
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VeVb武林網。
新聞熱點
疑難解答
