array 转 tree（广度优先）

  1. function array2tree(array) {
  2.   const newList = []
  3.   for (let i = 0; i < array.length; i++) {
  4.     if (array[i][pid] === 0) { //获取最顶层元素，它的父节点ID=0
  5.       newList.push(array[i])
  6.     } else { 
  7.       // 获取当前节点的父节点
  8.       const parent = array.find(item => item[id] === array[i][pid]) 
  9.       if (parent) {
  10.         // 把当前节点 加入到 父节点中
  11.         if (parent.children) {       
  12.           parent.children.push(array[i])
  13.         } else {
  14.           parent.children = [array[i]]
  15.         }
  16.       }
  17.     }
  18.   }
  19.   return newList
  20. }

树形结构数据

开发中经常要对数据做一些处理，大多情况下数据是固定层级和结构的，
但也有一些情况下数据的层级和结构是不固定的，比如文件目录、功能菜单、权限树等，
这种结构的数据的处理需要涉及到树的遍历算法。

  1.     const data = {
  2.     name: 'all',
  3.     children: [
  4.         {
  5.             name: '图片',
  6.             children: [
  7.                 {
  8.                     name: 'image1.jpg'
  9.                 },
  10.                 {
  11.                     name: '风景',
  12.                     children: [
  13.                         {
  14.                             name: 'guilin.jpg'
  15.                         },
  16.                         {
  17.                             name: 'hainan.jpg'
  18.                         }
  19.                     ]
  20.                 },
  21.                 {
  22.                     name: 'image2.jpg'
  23.                 }
  24.             ],
  25.         },
  26.         {
  27.             name: '视频',
  28.             children: [
  29.                 {
  30.                     name: 'video1.mp4'
  31.                 },
  32.                 {
  33.                     name: 'video2.mp4'
  34.                 }
  35.             ]
  36.         },
  37.         {
  38.             name: '文档',
  39.             children: [
  40.                 {
  41.                     name: 'document1.doc'
  42.                 },
  43.                 {
  44.                     name: '小说',
  45.                     children: [
  46.                         {
  47.                             name: 'novel.txt'
  48.                         },
  49.                         {
  50.                             name: 'novel2.txt'
  51.                         }
  52.                     ]
  53.                 },
  54.                 {
  55.                     name: 'document2.doc'
  56.                 }
  57.             ]
  58.         }
  59.     ]
  60. }

树的遍历算法

树的遍历有深度优先和广度优先两种方式。

  1. 深度优先遍历的形式是递归：
    1. 优点是代码简洁直观，
    2. 缺点是层级过深的时候可能会栈溢出，只适用于层级较少的情况；
  2. 广度优先遍历：
    1. 优点是不会栈溢出，适应任意层级深度，
    2. 但缺点是需要引入一个队列来存储待遍历的节点，空间复杂度较高。

深度优先（dfs）

  1. //深度优先（递归）
  2. // ope() ：是对每一个元素做附加操作的
  3. const dfs = (tree, ope) => {
  4.     const walk = (tree, depth = 1) => {
  5.         ope(tree.name, depth)
  6.         if(tree.children) {
  7.             tree.children.forEach((node) => {
  8.                 walk(node, depth + 1)
  9.             })
  10.         }
  11.     }
  12.     walk(tree)
  13. }
  14. // 测试
  15. // 参数二（函数） ：是对每一个元素做附加操作的
  16. dfs(data, (name, depth) => {
  17.     let pre = '';
  18.     for(let i =0; i < depth; i++) {
  19.         pre += '--'
  20.     }
  21.     console.log(pre + name)
  22. })

广度优先（bfs）

  1. //广度优先（使用队列存储子节点）
  2. // ope() ：是对每一个元素做附加操作的
  3. const bfs = (tree, ope) => {
  4.     const walk = (tree, depth = 1) => {
  5.         const queue = []
  6.         ope(tree.name, depth)
  7.         if(tree.children){
  8.             queue.push({
  9.                 nodes: tree.children,
  10.                 depth: depth + 1
  11.             })
  12.         }
  13.         while(queue.length) {
  14.             const item = queue.pop()
  15.             item.nodes && item.nodes.forEach(node => {
  16.                 ope(node.name, item.depth)
  17.                 if(node.children) {
  18.                     queue.push({
  19.                         nodes: node.children,
  20.                         depth: item.depth + 1
  21.                     })
  22.                 }
  23.             })
  24.         }
  25.     }
  26.     walk(tree)
  27. }
  28. //测试 
  29. // 参数二（函数） ：是对每一个元素做附加操作的
  30. bfs(data,(name, depth) => {
  31.     let pre = '';
  32.     for(let i =0; i < depth; i++) {
  33.         pre += '--'
  34.     }
  35.     console.log(pre + name)
  36. })

树形数据的过滤

很多情况下，我们不只需要遍历这棵树，可能还需要对这棵树进行一些过滤，返回过滤以后的数据，
比如权限树的过滤、文件目录结构的过滤、功能菜单的过滤。大多数情况下过滤后的数据依然要保留树形结构。

其实，对树形结构的各种操作都是建立在遍历的基础之上，实现过滤的功能只需要在遍历的时候加一个判断，
并且把符合条件的节点按照层级关系复制一份。

深度优先过滤（dfs-filter）

  1. // 参数一 ： 属性数据
  2. // 参数二 ： 节点附加操作函数
  3. // 参数三 ： 节点过滤函数
  4. const dfs = (tree, ope, filter) => {
  5.     const walkAndCopy = (tree, depth = 1) => {
  6.         if(filter(tree.name)) {
  7.             const copy = {}
  8.             ope(tree.name, depth)
  9.             copy.name = tree.name
  10.             if(tree.children) {
  11.                 copy.children = []
  12.                 tree.children.forEach((node) => {
  13.                     const subTree = walkAndCopy(node, depth + 1)
  14.                     subTree && copy.children.push(subTree)
  15.                 })
  16.             }       
  17.             return copy
  18.         }
  19.     }
  20.     return walkAndCopy(tree)
  21. }
  22. // 测试（过滤掉所有名字中含有1的文件和目录）
  23. const copy = dfs(data,(name, depth) => {}, (name) => {
  24.     return name.indexOf('1') === -1
  25. })
  26. console.log(copy)

广度优先过滤（bfs-filter）

  1. // 参数一 ： 属性数据
  2. // 参数二 ： 节点附加操作函数
  3. // 参数三 ： 节点过滤函数
  4. const bfs = (tree, ope, filter) => {
  5.     const walkAndCopy = (tree, depth = 1) => {
  6.         const queue = []
  7.         if (filter(tree.name)) {
  8.             const copy = {}
  9.             ope(tree.name, depth)
  10.             copy.name = tree.name
  11.             if(tree.children){
  12.                 copy.children = []
  13.                 queue.push({
  14.                     nodes: tree.children,
  15.                     depth: depth + 1,
  16.                     copyNodes: copy.children
  17.                 })
  18.             }
  19.             while(queue.length) {
  20.                 const item = queue.pop()
  21.                 item.nodes && item.nodes.forEach(node => {
  22.                     if(filter(node.name)) {
  23.                         const copyNode = {}
  24.                         ope(node.name, item.depth)
  25.                         copyNode.name = node.name
  26.                         if(node.children) {
  27.                             copyNode.children = []
  28.                             queue.push({
  29.                                 nodes: node.children,
  30.                                 depth: item.depth + 1,
  31.                                 copyNodes: copyNode.children
  32.                             })
  33.                         }
  34.                         item.copyNodes.push(copyNode)
  35.                     }
  36.                 })
  37.             }
  38.             return copy
  39.         }
  40.     }
  41.     return walkAndCopy(tree)
  42. }
  43. // 测试（过滤掉所有名字中含有1的文件和目录）
  44. const copy = bfs(data,(name, depth) => {}, (name) => {
  45.     return name.indexOf('1') === -1
  46. })
  48. console.log(copy)

常用方法

  1. /**
  2.  * 数组，对象去除空字符串，使其为null
  3.  * @param object
  4.  */
  5. export function removeEmptyString(object) {
  6.   for (const i in object) {
  7.     if (typeof object[i] === 'string' && (object[i] === '' || object[i].replace(/\s+/g, '') === '')) {
  8.       object[i] = null
  9.     }
  10.   }
  11. }
  13. /**
  14.  * list to  tree
  15.  * @desc 就是不停的获取当前节点的父节点，并把当前节点的加入到父节点的children中
  16.  * @param array
  17.  * @param id 主键名称
  18.  * @param pid 对应node 的 parentId
  19.  * @param rootValue array里根节点的 parentId value
  20.  * @returns {[]}
  21.  */
  22. export function array2tree(array, id, pid, rootValue) {
  23.   const newList = []
  24.   for (let i = 0; i < array.length; i++) {
  25.     if (array[i][pid] === rootValue) {
  26.       newList.push(array[i]) // 把根节点放入新的list中
  27.     } else { // Parent
  28.       const parent = array.find(item => item[id] === array[i][pid]) // 获取 当前节点的父节点
  29.       if (parent) { // 如果当前节点的父节点不为空，就把当前节点放入父节点的 children 数组属性中
  30.         if (parent.children) {
  31.           // 更改原数组就相当于给新数组里面添加了children，因为新数组里面元素的地址和原数组是一个、
  32.           parent.children.push(array[i])
  33.         } else {
  34.           parent.children = [array[i]]
  35.         }
  36.       }
  37.     }
  38.   }
  39.   return newList
  40. }
  42. /**
  43.  *  tree 转 list
  44.  * @desc 利用队列的特性，不停的往队列里存放当前node的children，然后边遍历
  45.  * @param tree 是数组 ，是tree数组
  46.  * @returns {[]}
  47.  */
  48. export function tree2List(trees) {
  49.   const newList = []
  50.   const queue = []
  51.   trees.forEach(tree => {
  52.     // 1. 对根节点的处理
  53.     const { children, ...meta } = tree // 去除子节点集合
  54.     newList.push(meta) // 把当前节点介入到 新的list里
  55.     if (children) { // 如果当前节点的 children 数组属性不为空，就把它加入到队列中
  56.       queue.push(children)
  57.     }
  58.     // 2. 对根节点以外的节点进行处理
  59.     // 遍历队列，可以看出 队列的操作 ： 边遍历,边放入新的元素
  60.     while (queue.length) {
  61.       const item = queue.pop() // 从队列里推出一个元素
  62.       item && item.forEach(node => { // 如果子节点还有子节点，就继续往队列里存放
  63.         // 以下是重复性操作
  64.         const { children, ...meta } = node
  65.         newList.push(meta)
  66.         if (children) {
  67.           queue.push(children)
  68.         }
  69.       })
  70.     }
  71.   })
  72.   return newList
  73. }
  75. /**
  76.  * 获取node 的上级node集合(包含当前节点)，就是获取所以的父节点
  77.  * 获取当前节点的所以子节点，可以自己实现，和这个原理相同
  78.  * @param tree
  79.  * @param nodes 是数组，需要获取上级节点的节点集合
  80.  * @param id 主键名称
  81.  * @param pid 对应node 的 parentId
  82.  * @param rootValue tree 根节点的 parentId value
  83.  * @returns {[]}
  84.  */
  85. export function getParentIds(tree, nodes, id, pid, rootValue) {
  86.   const list = tree2List(tree) // 先把tree 转成 list
  87.   const newList = []
  88.   const queue = []
  89.   nodes.forEach(n => {
  90.     // 1. 对根节点的处理
  91.     // eslint-disable-next-line no-unused-vars
  92.     const { children, ...meta } = n // 去除子节点集合
  93.     const node = meta
  94.     // 把当前节点放入 新的list中
  95.     if (newList.findIndex(r => r[id] === node[id]) < 0) { newList.push(node) } // 目的是去重
  96.     // 如果当前节点有父节点，就把父节点放入队列中
  97.     if (node[pid] !== rootValue) {
  98.       queue.push(list.find(ele => ele[id] === node[pid]))
  99.     }
  100.     // 2. 对根节点以外的节点进行处理
  101.     // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
  102.     while (queue.length) {
  103.       const n = queue.pop() // 从队列里推出一个元素
  104.       // 以下是重复性操作
  105.       // eslint-disable-next-line no-unused-vars
  106.       const { children, ...meta } = n
  107.       const node = meta
  108.       if (newList.findIndex(r => r[id] === node[id]) < 0) { newList.push(node) } // 目的是去重
  109.       if (node[pid] !== rootValue) {
  110.         queue.push(list.find(ele => ele[id] === node[pid]))
  111.       }
  112.     }
  113.   })
  114.   return newList
  115. }
  117. /**
  118.  * 迭代tree
  119.  * @param tree
  120.  * @param handler 对每一个节点的处理函数
  121.  */
  122. export function treeIterator(tree, handler) {
  123.   const walk = (tree) => {
  124.     const queue = []
  125.     // 1. 对根节点的处理
  126.     const { children, ...meta } = tree // 去除子节点集合
  127.     handler(meta) // 对节点进行操作
  128.     // 把当前节点的子节点list放入队列中
  129.     if (children) {
  130.       queue.push(children)
  131.     }
  132.     // 2. 对根节点以外的节点进行处理
  133.     // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
  134.     while (queue.length) {
  135.       const nodes = queue.pop() // 从队列里推出一个元素
  136.       // 一下是重复性操作
  137.       nodes && nodes.forEach(node => {
  138.         const { children, ...meta } = node
  139.         handler(meta)
  140.         if (children) {
  141.           queue.push(children)
  142.         }
  143.       })
  144.     }
  145.   }
  146.   walk(tree)
  147. }
  149. /**
  150.  * tree 过滤
  151.  * @param tree
  152.  * @param handler  处理函数
  153.  * @param filter  过滤函数
  154.  * @returns {{[p: string]: *, [p: number]: *}}
  155.  */
  156. export function treeFilter(tree, handler, filter) {
  157.   const walkAndCopy = (tree) => {
  158.     const queue = []
  159.     // 1. 对根节点的处理
  160.     if (filter(tree)) {
  161.       let newTree = {}
  162.       const { children, ...meta } = tree
  163.       handler(meta) // 处理函数
  164.       newTree = meta // 新节点的元信息，除子节点外的
  165.       // 如果当前节点的存在子节点，就把 当前节点的子节点 和 新tree的子节点 放到队列里
  166.       // 如果原节点有子节点，那么新节点也应该有子节点
  167.       if (children) {
  168.         newTree.children = [] // 每一个节点生成时，自添加一个子节点list 属性，并把这个list属性放入到队列中
  169.         queue.push({
  170.           oldNodes: children,
  171.           newNodes: newTree.children // 新tree 的子节点集合的引用
  172.         })
  173.       }
  174.       // 2. 对根节点以外的节点进行处理
  175.       // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
  176.       while (queue.length) {
  177.         const item = queue.pop() // 从队列里推出一个元素
  178.         // 如果 节点中的子节点集合存在，就遍历子节点集合
  179.         item.oldNodes && item.oldNodes.forEach(node => {
  180.           if (filter(node)) {
  181.             // 以下是重复性操作
  182.             let newNode = {}
  183.             const { children, ...meta } = node
  184.             handler(meta)
  185.             newNode = meta
  186.             if (children) {
  187.               newNode.children = []
  188.               queue.push({
  189.                 oldNodes: children,
  190.                 newNodes: newNode.children
  191.               })
  192.             }
  193.             item.newNodes.push(newNode) // 把当前节点放入到子节点集合中
  194.           }
  195.         })
  196.       }
  197.       return newTree
  198.     }
  199.   }
  200.   return walkAndCopy(tree)
  201. }

原文： https://blog.csdn.net/qq_37377082/article/details/111759153