JavaScript 處理樹(shù)數(shù)據(jù)結(jié)構(gòu)的方法示例

更新時(shí)間：2019年06月16日 09:39:42 作者：rxliuli

這篇文章主要介紹了JavaScript 處理樹(shù)數(shù)據(jù)結(jié)構(gòu)的方法示例，小編覺(jué)得挺不錯(cuò)的，現(xiàn)在分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧

JavaScript 處理樹(shù)結(jié)構(gòu)數(shù)據(jù)

場(chǎng)景

即便在前端，也有很多時(shí)候需要操作樹(shù)結(jié)構(gòu) 的情況，最典型的場(chǎng)景莫過(guò)于無(wú)限級(jí)分類(lèi)。之前吾輩曾經(jīng)遇到過(guò)這種場(chǎng)景，但當(dāng)時(shí)沒(méi)有多想直接手撕 JavaScript 列表轉(zhuǎn)樹(shù)了，并沒(méi)有想到進(jìn)行封裝。后來(lái)遇到的場(chǎng)景多了，想到如何封裝樹(shù)結(jié)構(gòu)操作，但考慮到不同場(chǎng)景的樹(shù)節(jié)點(diǎn)結(jié)構(gòu)的不同，就沒(méi)有繼續(xù)進(jìn)行下去了。

直到吾輩開(kāi)始經(jīng)常運(yùn)用了 ES6 Proxy 之后，吾輩想到了新的解決方案！

思考

問(wèn): 之前為什么停止封裝樹(shù)結(jié)構(gòu)操作了？
答: 因?yàn)椴煌臉?shù)結(jié)構(gòu)節(jié)點(diǎn)可能有不同的結(jié)構(gòu)，例如某個(gè)項(xiàng)目的樹(shù)節(jié)點(diǎn)父節(jié)點(diǎn) id 字段是 parent，而另一個(gè)項(xiàng)目則是 parentId
問(wèn): Proxy 如何解決這個(gè)問(wèn)題呢？
答: Proxy 可以攔截對(duì)象的操作，當(dāng)訪(fǎng)問(wèn)對(duì)象不存在的字段時(shí)，Proxy 能將之代理到已經(jīng)存在的字段上
問(wèn): 這點(diǎn)意味著什么？
答: 它意味著 Proxy 能夠抹平不同的樹(shù)節(jié)點(diǎn)結(jié)構(gòu)之間的差異！
問(wèn): 我還是不太明白 Proxy 怎么用，能舉個(gè)具體的例子么？
答: 當(dāng)然可以，我現(xiàn)在就讓你看看 Proxy 的能力

下面思考一下如何在同一個(gè)函數(shù)中處理這兩種樹(shù)節(jié)點(diǎn)結(jié)構(gòu)

/**
 * 系統(tǒng)菜單
 */
class SysMenu {
 /**
  * 構(gòu)造函數(shù)
  * @param {Number} id 菜單 id
  * @param {String} name 顯示的名稱(chēng)
  * @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 來(lái)抹平訪(fǎng)問(wèn)它們之間的差異

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í)抹平了，我們可以通過(guò)訪(fǎng)問(wèn)相同的屬性來(lái)獲取到不同結(jié)構(gòu)對(duì)象的值！然而，每個(gè)對(duì)象都寫(xiě)一次代理終究有點(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)在，我們可以用更簡(jiǎn)單的方式來(lái)做代理了。

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)樹(shù)結(jié)構(gòu)

想要抹平差異，我們至少還需要一個(gè)標(biāo)準(zhǔn)的樹(shù)結(jié)構(gòu)，告訴別人我們需要什么樣的樹(shù)節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)，以便于在之后處理樹(shù)節(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] 樹(shù)結(jié)點(diǎn)的 id 屬性名
  * @param {String} [options.parentId] 樹(shù)結(jié)點(diǎn)的父節(jié)點(diǎn) id 屬性名
  * @param {String} [options.child] 樹(shù)結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組屬性名
  * @param {String} [options.path] 樹(shù)結(jié)點(diǎn)的全路徑屬性名
  * @param {Array.<Object>} [options.args] 其他參數(shù)
  */
 constructor({ id, parentId, child, path, ...args } = {}) {
  /**
   * @field 樹(shù)結(jié)點(diǎn)的 id 屬性名
   */
  this.id = id
  /**
   * @field 樹(shù)結(jié)點(diǎn)的父節(jié)點(diǎn) id 屬性名
   */
  this.parentId = parentId
  /**
   * @field 樹(shù)結(jié)點(diǎn)的子節(jié)點(diǎn)數(shù)組屬性名
   */
  this.child = child
  /**
   * @field 樹(shù)結(jié)點(diǎn)的全路徑屬性名
   */
  this.path = path
  Object.assign(this, args)
 }
}

實(shí)現(xiàn)列表轉(zhuǎn)樹(shù)

列表轉(zhuǎn)樹(shù)，除了遞歸之外，也可以使用循環(huán)實(shí)現(xiàn)，這里便以循環(huán)為示例。

思路

在外層遍歷子節(jié)點(diǎn)
如果是根節(jié)點(diǎn)，就添加到根節(jié)點(diǎn)中并不在找其父節(jié)點(diǎn)。
否則在內(nèi)層循環(huán)中找該節(jié)點(diǎn)的父節(jié)點(diǎn)，找到之后將子節(jié)點(diǎn)追加到父節(jié)點(diǎn)的子節(jié)點(diǎn)列表中，然后結(jié)束本次內(nèi)層循環(huán)。

/**
 * 將列表轉(zhuǎn)換為樹(shù)節(jié)點(diǎn)
 * 注：該函數(shù)默認(rèn)樹(shù)的根節(jié)點(diǎn)只有一個(gè)，如果有多個(gè)，則返回一個(gè)數(shù)組
 * @param {Array.<Object>} list 樹(shù)節(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>} 樹(shù)節(jié)點(diǎn)，或是樹(shù)節(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
}

抽取通用的樹(shù)結(jié)構(gòu)遍歷邏輯

首先，明確一點(diǎn)，樹(shù)結(jié)構(gòu)的完全遍歷是通用的，大致實(shí)現(xiàn)基本如下

遍歷頂級(jí)樹(shù)節(jié)點(diǎn)
遍歷樹(shù)節(jié)點(diǎn)的子節(jié)點(diǎn)列表
遞歸調(diào)用函數(shù)并傳入子節(jié)點(diǎn)

/**
 * 返回第一個(gè)參數(shù)的函數(shù)
 * 注：一般可以當(dāng)作返回參數(shù)自身的函數(shù)，如果你只關(guān)注第一個(gè)參數(shù)的話(huà)
 * @param {Object} obj 任何對(duì)象
 * @returns {Object} 傳入的第一個(gè)參數(shù)
 */
export function returnItself(obj) {
 return obj
}
/**
 * 遍歷并映射一棵樹(shù)的每個(gè)節(jié)點(diǎn)
 * @param {Object} root 樹(shù)節(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} 遞歸遍歷后的樹(shù)節(jié)點(diǎn)
 */
export function treeMapping(
 root,
 {
  before = returnItself,
  after = returnItself,
  paramFn = (node, ...args) => [],
 } = {},
) {
 /**
  * 遍歷一顆完整的樹(shù)
  * @param {INode} node 要遍歷的樹(shù)節(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 遍歷樹(shù)并打印

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)樹(shù)轉(zhuǎn)列表

當(dāng)然，我們亦可使用 treeMapping 簡(jiǎn)單的實(shí)現(xiàn) treeToList，當(dāng)然，這里考慮了是否計(jì)算全路徑，畢竟還是要考慮性能的！

/**
 * 將樹(shù)節(jié)點(diǎn)轉(zhuǎn)為樹(shù)節(jié)點(diǎn)列表
 * @param {Object} root 樹(shù)節(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>} 樹(shù)節(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)換任意樹(shù)結(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 中處理樹(shù)結(jié)構(gòu)數(shù)據(jù)就到這里了。當(dāng)然，樹(shù)結(jié)構(gòu)數(shù)據(jù)還有其他的更多操作尚未實(shí)現(xiàn)，例如常見(jiàn)的查詢(xún)子節(jié)點(diǎn)列表，節(jié)點(diǎn)過(guò)濾，最短路徑查找等等。但目前列表與樹(shù)的轉(zhuǎn)換才是最常用的，而且其他操作基本上也是基于它們做的，所以這里也便點(diǎn)到為止了。

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章: