array 转 tree（广度优先）

function array2tree(array) {
	  const newList = []
	  for (let i = 0; i < array.length; i++) {
	    if (array[i][pid] === 0) { //获取最顶层元素，它的父节点ID=0
	      newList.push(array[i])
	    } else { 
	      const parent = array.find(item => item[id] === array[i][pid])  // 获取当前节点的父节点
	      if (parent) {
	      	// 把当前节点 加入到 父节点中
	        if (parent.children) {       
	          parent.children.push(array[i])
	        } else {
	          parent.children = [array[i]]
	        }
	      }
	    }
	  }
	  return newList
}

树形结构数据

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

	const data = {
    name: 'all',
    children: [
        {
            name: '图片',
            children: [
                {
                    name: 'image1.jpg'
                },
                {
                    name: '风景',
                    children: [
                        {
                            name: 'guilin.jpg'
                        },
                        {
                            name: 'hainan.jpg'
                        }
                    ]
                },
                {
                    name: 'image2.jpg'
                }
            ],
        },
        {
            name: '视频',
            children: [
                {
                    name: 'video1.mp4'
                },
                {
                    name: 'video2.mp4'
                }
            ]
        },
        {
            name: '文档',
            children: [
                {
                    name: 'document1.doc'
                },
                {
                    name: '小说',
                    children: [
                        {
                            name: 'novel.txt'
                        },
                        {
                            name: 'novel2.txt'
                        }
                    ]
                },
                {
                    name: 'document2.doc'
                }
            ]
        }
    ]
}

树的遍历算法

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

• 深度优先（dfs）

//深度优先（递归）
// ope() ：是对每一个元素做附加操作的
const dfs = (tree, ope) => {
    const walk = (tree, depth = 1) => {
        ope(tree.name, depth)
        if(tree.children) {
            tree.children.forEach((node) => {
                walk(node, depth + 1)
            })
        }
    }
    walk(tree)
}
// 测试
// 参数二（函数） ：是对每一个元素做附加操作的
dfs(data, (name, depth) => {
    let pre = '';
    for(let i =0; i < depth; i++) {
        pre += '--'
    }
    console.log(pre + name)
})

• 广度优先（bfs）

//广度优先（使用队列存储子节点）
// ope() ：是对每一个元素做附加操作的
const bfs = (tree, ope) => {
    const walk = (tree, depth = 1) => {
        const queue = []
        ope(tree.name, depth)
        if(tree.children){
            queue.push({
                nodes: tree.children,
                depth: depth + 1
            })
        }
        while(queue.length) {
            const item = queue.pop()
            item.nodes && item.nodes.forEach(node => {
                ope(node.name, item.depth)
                if(node.children) {
                    queue.push({
                        nodes: node.children,
                        depth: item.depth + 1
                    })
                }
            })
        }
    }
    walk(tree)
}
//测试 
// 参数二（函数） ：是对每一个元素做附加操作的
bfs(data,(name, depth) => {
    let pre = '';
    for(let i =0; i < depth; i++) {
        pre += '--'
    }
    console.log(pre + name)
})

树形数据的过滤

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

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

• 深度优先过滤（dfs-filter）

// 参数一 ： 属性数据
// 参数二 ： 节点附加操作函数
// 参数三 ： 节点过滤函数
const dfs = (tree, ope, filter) => {
    const walkAndCopy = (tree, depth = 1) => {
        if(filter(tree.name)) {
            const copy = {}
            ope(tree.name, depth)
            copy.name = tree.name
            if(tree.children) {
                copy.children = []
                tree.children.forEach((node) => {
                    const subTree = walkAndCopy(node, depth + 1)
                    subTree && copy.children.push(subTree)
                })
            }       
            return copy
        }
    }
    return walkAndCopy(tree)
}
// 测试（过滤掉所有名字中含有1的文件和目录）
const copy = dfs(data,(name, depth) => {}, (name) => {
    return name.indexOf('1') === -1
})
console.log(copy)

• 广度优先过滤（bfs-filter）

// 参数一 ： 属性数据
// 参数二 ： 节点附加操作函数
// 参数三 ： 节点过滤函数
const bfs = (tree, ope, filter) => {
    const walkAndCopy = (tree, depth = 1) => {
        const queue = []
        if (filter(tree.name)) {
            const copy = {}
            ope(tree.name, depth)
            copy.name = tree.name
            if(tree.children){
                copy.children = []
                queue.push({
                    nodes: tree.children,
                    depth: depth + 1,
                    copyNodes: copy.children
                })
            }
            while(queue.length) {
                const item = queue.pop()
                item.nodes && item.nodes.forEach(node => {
                    if(filter(node.name)) {
                        const copyNode = {}
                        ope(node.name, item.depth)
                        copyNode.name = node.name
                        if(node.children) {
                            copyNode.children = []
                            queue.push({
                                nodes: node.children,
                                depth: item.depth + 1,
                                copyNodes: copyNode.children
                            })
                        }
                        item.copyNodes.push(copyNode)
                    }
                })
            }
            return copy
        }
    }
    return walkAndCopy(tree)
}
// 测试（过滤掉所有名字中含有1的文件和目录）
const copy = bfs(data,(name, depth) => {}, (name) => {
    return name.indexOf('1') === -1
})

console.log(copy)

常用方法

/**
 * 数组，对象去除空字符串，使其为null
 * @param object
 */
export function removeEmptyString(object) {
  for (const i in object) {
    if (typeof object[i] === 'string' && (object[i] === '' || object[i].replace(/\s+/g, '') === '')) {
      object[i] = null
    }
  }
}

/**
 * list to  tree
 * @desc 就是不停的获取当前节点的父节点，并把当前节点的加入到父节点的children中
 * @param array
 * @param id 主键名称
 * @param pid 对应node 的 parentId
 * @param rootValue array里根节点的 parentId value
 * @returns {[]}
 */
export function array2tree(array, id, pid, rootValue) {
  const newList = []
  for (let i = 0; i < array.length; i++) {
    if (array[i][pid] === rootValue) {
      newList.push(array[i]) // 把根节点放入新的list中
    } else { // Parent
      const parent = array.find(item => item[id] === array[i][pid]) // 获取 当前节点的父节点
      if (parent) { // 如果当前节点的父节点不为空，就把当前节点放入父节点的 children 数组属性中
        if (parent.children) {
          // 更改原数组就相当于给新数组里面添加了children，因为新数组里面元素的地址和原数组是一个、
          parent.children.push(array[i])
        } else {
          parent.children = [array[i]]
        }
      }
    }
  }
  return newList
}

/**
 *  tree 转 list
 * @desc 利用队列的特性，不停的往队列里存放当前node的children，然后边遍历
 * @param tree 是数组 ，是tree数组
 * @returns {[]}
 */
export function tree2List(trees) {
  const newList = []
  const queue = []
  trees.forEach(tree => {
    // 1. 对根节点的处理
    const { children, ...meta } = tree // 去除子节点集合
    newList.push(meta) // 把当前节点介入到 新的list里
    if (children) { // 如果当前节点的 children 数组属性不为空，就把它加入到队列中
      queue.push(children)
    }
    // 2. 对根节点以外的节点进行处理
    // 遍历队列，可以看出 队列的操作 ： 边遍历,边放入新的元素
    while (queue.length) {
      const item = queue.pop() // 从队列里推出一个元素
      item && item.forEach(node => { // 如果子节点还有子节点，就继续往队列里存放
        // 以下是重复性操作
        const { children, ...meta } = node
        newList.push(meta)
        if (children) {
          queue.push(children)
        }
      })
    }
  })
  return newList
}

/**
 * 获取node 的上级node集合(包含当前节点)，就是获取所以的父节点
 * 获取当前节点的所以子节点，可以自己实现，和这个原理相同
 * @param tree
 * @param nodes 是数组，需要获取上级节点的节点集合
 * @param id 主键名称
 * @param pid 对应node 的 parentId
 * @param rootValue tree 根节点的 parentId value
 * @returns {[]}
 */
export function getParentIds(tree, nodes, id, pid, rootValue) {
  const list = tree2List(tree) // 先把tree 转成 list
  const newList = []
  const queue = []
  nodes.forEach(n => {
    // 1. 对根节点的处理
    // eslint-disable-next-line no-unused-vars
    const { children, ...meta } = n // 去除子节点集合
    const node = meta
    // 把当前节点放入 新的list中
    if (newList.findIndex(r => r[id] === node[id]) < 0) { newList.push(node) } // 目的是去重
    // 如果当前节点有父节点，就把父节点放入队列中
    if (node[pid] !== rootValue) {
      queue.push(list.find(ele => ele[id] === node[pid]))
    }
    // 2. 对根节点以外的节点进行处理
    // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
    while (queue.length) {
      const n = queue.pop() // 从队列里推出一个元素
      // 以下是重复性操作
      // eslint-disable-next-line no-unused-vars
      const { children, ...meta } = n
      const node = meta
      if (newList.findIndex(r => r[id] === node[id]) < 0) { newList.push(node) } // 目的是去重
      if (node[pid] !== rootValue) {
        queue.push(list.find(ele => ele[id] === node[pid]))
      }
    }
  })
  return newList
}

/**
 * 迭代tree
 * @param tree
 * @param handler 对每一个节点的处理函数
 */
export function treeIterator(tree, handler) {
  const walk = (tree) => {
    const queue = []
    // 1. 对根节点的处理
    const { children, ...meta } = tree // 去除子节点集合
    handler(meta) // 对节点进行操作
    // 把当前节点的子节点list放入队列中
    if (children) {
      queue.push(children)
    }
    // 2. 对根节点以外的节点进行处理
    // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
    while (queue.length) {
      const nodes = queue.pop() // 从队列里推出一个元素
      // 一下是重复性操作
      nodes && nodes.forEach(node => {
        const { children, ...meta } = node
        handler(meta)
        if (children) {
          queue.push(children)
        }
      })
    }
  }
  walk(tree)
}

/**
 * tree 过滤
 * @param tree
 * @param handler  处理函数
 * @param filter  过滤函数
 * @returns {{[p: string]: *, [p: number]: *}}
 */
export function treeFilter(tree, handler, filter) {
  const walkAndCopy = (tree) => {
    const queue = []
    // 1. 对根节点的处理
    if (filter(tree)) {
      let newTree = {}
      const { children, ...meta } = tree
      handler(meta) // 处理函数
      newTree = meta // 新节点的元信息，除子节点外的
      // 如果当前节点的存在子节点，就把 当前节点的子节点 和 新tree的子节点 放到队列里
      // 如果原节点有子节点，那么新节点也应该有子节点
      if (children) {
        newTree.children = [] // 每一个节点生成时，自添加一个子节点list 属性，并把这个list属性放入到队列中
        queue.push({
          oldNodes: children,
          newNodes: newTree.children // 新tree 的子节点集合的引用
        })
      }
      // 2. 对根节点以外的节点进行处理
      // 遍历 队列 ，可以看出 队列的操作 ： 边遍历,边放入新的元素
      while (queue.length) {
        const item = queue.pop() // 从队列里推出一个元素
        // 如果 节点中的子节点集合存在，就遍历子节点集合
        item.oldNodes && item.oldNodes.forEach(node => {
          if (filter(node)) {
            // 以下是重复性操作
            let newNode = {}
            const { children, ...meta } = node
            handler(meta)
            newNode = meta
            if (children) {
              newNode.children = []
              queue.push({
                oldNodes: children,
                newNodes: newNode.children
              })
            }
            item.newNodes.push(newNode) // 把当前节点放入到子节点集合中
          }
        })
      }
      return newTree
    }
  }
  return walkAndCopy(tree)
}