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

時間:2019-06-16來源/作者:rxliuli 編輯:源碼庫 文章熱度:

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 中處理樹結構數據就到這里了。當然,樹結構數據還有其他的更多操作尚未實現,例如常見的查詢子節點列表,節點過濾,最短路徑查找等等。但目前列表與樹的轉換才是最常用的,而且其他操作基本上也是基于它們做的,所以這里也便點到為止了。

以上就是本文的全部內容,希望對大家的學習有所幫助,也希望大家多多支持ASPKU源碼庫。


注:相關教程知識閱讀請移步到JavaScript/Ajax教程頻道。
相關JavaScript/Ajax教程
熱門標簽

JavaScript/Ajax教程Rss訂閱JavaScript/Ajax教程搜索

陕西福彩快乐十分爱彩乐