JavaScript 處理樹數據結構的方法示例

來源：懂視網責編：小采時間：2020-11-27 21:55:10

JavaScript 處理樹數據結構的方法示例

JavaScript 處理樹數據結構的方法示例:JavaScript 處理樹結構數據場景即便在前端，也有很多時候需要操作樹結構的情況，最典型的場景莫過于無限級分類。之前吾輩曾經遇到過這種場景，但當時沒有多想直接手撕 JavaScript 列表轉樹了，并沒有想到進行封裝。后來遇到的場景多了，想到如何封裝樹

推薦度：

點擊下載本文 文檔為doc格式

導讀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)
 }
}

實現列表轉樹

列表轉樹，除了遞歸之外，也可以使用循環實現，這里便以循環為示例。

思路

在外層遍歷子節點
如果是根節點，就添加到根節點中并不在找其父節點。
否則在內層循環中找該節點的父節點，找到之后將子節點追加到父節點的子節點列表中，然后結束本次內層循環。

/**
 * 將列表轉換為樹節點
 * 注：該函數默認樹的根節點只有一個，如果有多個，則返回一個數組
 * @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 中處理樹結構數據就到這里了。當然，樹結構數據還有其他的更多操作尚未實現，例如常見的查詢子節點列表，節點過濾，最短路徑查找等等。但目前列表與樹的轉換才是最常用的，而且其他操作基本上也是基于它們做的，所以這里也便點到為止了。

聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。TEL:177 7030 7066 E-MAIL:11247931@qq.com