测试数据

const arr = [
  {id: 1, name: '部门1', pid: 0},
  {id: 2, name: '部门2', pid: 1},
  {id: 3, name: '部门3', pid: 1},
  {id: 4, name: '部门4', pid: 3},
  {id: 5, name: '部门5', pid: 4},
]

const obj = {
  id: 1,
  name: "部门1",
  pid: 0,
  children: [
    {
      id: 2,
      name: "部门2",
      pid: 1,
      children: []
    },
    {
      id: 3,
      name: "部门3",
      pid: 1,
      children: [
        {
          id: 4,
          name: "部门4",
          pid: 3,
          children: [
            {
              id: 5,
              name: "部门5",
              pid:4,
              children: []
            }
          ]
        }
      ]
    }
  ]
}

tips：以下算法均以上面的数据结构实现，主要体现思路，注意注释

array to tree 【生成树结构】

递归

定义方法获取指定 id 的所有 children，每个 children 递归调用该方法获取 children.

优势是代码少，结构清晰，缺点是递归相对循环耗能更高。

/**
 * @param {arr: array 原数组数组, id: number 父节点id} 
 * @return {children: array 子数组}
 */
function getChildren(arr, id) {
  const res = [];
  for (const item of arr) {
    if (item.pid === id) { // 找到当前id的子元素
      // 插入子元素，每个子元素的children通过回调生成
      res.push({...item, children: getChildren(arr, item.id)});
    }
  }
  return res;
}

getChildren(arr, 0);

定义方法获取指定 id 的 node，node.children 的每个元素 调用该方法获取新的子元素

/**
 * @param {arr: array 原数组数组, id: number 当前元素id} 
 * @return {children: array 子数组}
 */
function getNode(arr, id){
  const node = arr.find(i => i.id === id); // 找到当前元素
  node.children = [];
  for(const item of arr) {
    if (item.pid === id) {
      // 给当前元素添加子节点，每个子节点递归调用
      node.children.push(getNode(arr, item.id));
    }
  }
  return node;
}

getChildren(arr, 1);

循环

利用 map 存储数组数据，并且每次循环处理对应的元素，利用指针指向内存空间的原理

/**
 * @param {arr: array, pid: number}
 * @return {obj: object}
 */
function fn(arr, pid) {
  const map = new Map(); // 生成map存储元素
  for(const item of arr) {
    if (!map.has(item.id)) { // 若map中没有当前元素，添加并初始化children
      map.set(item.id, {...item, children: []});
    } else {
      // 若不存在父元素 pid，后续会构造一个空的父元素，就会出现当前元素 item 已经存在的情况；此时需要将当前元素与已存在的元素（创建的父元素）进行合并
      // 即之前初始化父元素时只存在children，匹配到时表示该父元素存在，合并数据
      map.set(item.id, {...map.get(item.id), ...item});
    }
    if (map.has(item.pid)){ // 查找父元素，存在则将该元素插入到children
      map.get(item.pid).children.push(map.get(item.id));
    } else { // 否则初始化父元素，并插入children
      map.set(item.pid, {children: [map.get(item.id)]});
    }
  }
  return map.get(pid);
}

fn(arr, 0);

封装

// 数组转树结构
// 利用 map 存储数组数据，并且每次循环处理对应的元素，利用指针指向内存空间的原理
// 步骤：(遍历)
// 1.先储存下元素，查找储存中是否存在父元素，若无则初始化一个，并将该元素插入
// 2.遍历下一个，继续没有该元素，重复上面；如果查找到了，即为曾初始化过的元素，合并该父元素
export function getTree(arr, baseParentId, attrsDiff = { parentId: 'pid', targetId: 'id', childrenPropretyName: 'children' }) {
  const map = new Map(); // 生成map存储元素
  for (const item of arr) {
    if (!map.has(item[attrsDiff.targetId])) { // 若map中没有当前元素，添加并初始化children
      map.set(item[attrsDiff.targetId], { ...item, [attrsDiff.childrenPropretyName]: [] });
    } else {
      // 若不存在父元素 pid，后续会构造一个空的父元素，就会出现当前元素 item 已经存在的情况；此时需要将当前元素与已存在的元素（创建的父元素）进行合并
      // 即之前初始化父元素时只存在children，匹配到时表示该父元素存在，合并数据；未匹配到即未最顶级父元素，其只有子元素而不存在本身
      map.set(item[attrsDiff.targetId], { ...map.get(item[attrsDiff.targetId]), ...item });
    }
    
    if (map.has(item[attrsDiff.parentId])) { // 查找父元素，存在则将该元素插入到children
      map.get(item[attrsDiff.parentId]).children.push(map.get(item[attrsDiff.targetId]));
    } else { // 否则初始化父元素，并插入children
      map.set(item[attrsDiff.parentId], { children: [map.get(item[attrsDiff.targetId])] });
    }
  }
  return map.get(baseParentId)[attrsDiff.childrenPropretyName];
}

tree to array 【扁平化数据】

递归

/**
 * @param {obj: object, res: array}
 * @return {arr: array}
 */
function fn(obj, res = []) { // 默认初始结果数组为[]
  res.push(obj); // 当前元素入栈
  // 若元素包含children，则遍历children并递归调用使每一个子元素入栈
  if (obj.children && obj.children.length) {
    for(const item of obj.children) {
      fn(item, res);
    }
  }
  return res;
}

fn(arr);

/**
 * @param { arr: array } 接收子数组，调用时可以构造 `{children: [...]}` 开始调用
 * @return { arr: array }
 */
function fn(arr) {
  const res = [];
  for(const item of arr) { // 遍历子元素，若包含children则递归调用
      res.push(item); // chilren插入结果数组
    if (item.children && item.children.length) {
      res.push(...fn(item.children))
    }
  }
  return res;
}

fn([children: [obj]]);

封装

// 树结构转数组
/**
 * @param {Array} arr
 * @param {String} childrenPropretyName:子元素 proprety 名称
 */
export function flatTree(arr, childrenPropretyName = 'children') {
  const res = [];
  for (const item of arr) { // 遍历子元素，若包含children则递归调用
    res.push(item)
    if (item[childrenPropretyName] && item[childrenPropretyName].length) {
      res.push(...flatTree(item[childrenPropretyName], childrenPropretyName))
    }
    delete item[childrenPropretyName]
  }
// 去重
  const newArr = [...new Set(res.map(v => JSON.stringify(v)))].map(s => JSON.parse(s));
  return newArr;
}

循环

基本大部分递归都可以用栈的思想改为循环，将每次需要处理的元素压入栈中，处理后弹出，至栈为空

/**
 * @param {obj: object} 
 * @return {arr: array}
 */
function fn(obj) {
  const stack = [];         // 声明栈，用来存储待处理元素
  const res = [];           // 接收结果
  stack.push(obj);          // 将初始元素压入栈
  while(stack.length) {     // 栈不为空则循环执行
    const item = stack[0];  // 取出栈顶元素
    res.push(item);         // 元素本身压入结果数组
    stack.shift();          // 将当前元素弹出栈
    // 逻辑处理，如果当前元素包含子元素，则将子元素压入栈
    if (item.children && item.children.length) {
      stack.push(...item.children);
    }
  }
  return res;
}

fn(obj);

拓展：根据id拿到所有父级id

其实就是递归的简单运用

function getPaths(data, id) {
    for (const item of data) {
      if (item.id && item.id === id) {
        return [item.id];
      }
      if (item.children) {
        const d = getPaths(item.children, id);
        if (d) return [item.id,...d];
      }
   }
}

拓展：根据条件进行筛选

/**
 * 递归过滤节点，生成新的树结构
 * @param {Node[]} nodes 要过滤的节点
 * @param {node => boolean} predicate 过滤条件，符合条件的节点保留
 * @return 过滤后的节点
 */
export function deal(nodes:any[], predicate:(node: any)=>boolean) {
  // 如果已经没有节点了，结束递归
  if (!(nodes && nodes.length)) {
      return [];
  }

  const newChildren = [];
  for (const node of nodes) {
      if (predicate(node)) {
          // 如果节点符合条件，直接加入新的节点集
          newChildren.push(node);
          node.children = deal(node.children, predicate);
      } else {
          // 如果当前节点不符合条件，递归过滤子节点，
          // 把符合条件的子节点提升上来，并入新节点集
          newChildren.push(...deal(node.children, predicate));
      }
  }
  return newChildren;
}

拓展：根据条件获取节点及其子节点

// 条件检索对应节点及其子节点
export const getItemInTree = (fn, tree) => {
  let res = null;
  for (let node of tree) {
    fn(node) ? (res = node) : '';
    if (res) break;
    if (node.children && node.children.length) {
      res = getItemInTree(fn, node.children);
    }
  }
  return res;
};
  const list = [
    {id: '1',name: '手机号分配',lv:1,children:[]},
    {id: '2',name: '账号密码分配',lv:1,children:[
      {id: '2_1', name: '自动分配',lv:2, children: []},
      {id: '2_2', name: '手动导入分配',lv:2, children: []},
    ]},
  ]

拓展：根据条件修改属性

const addKey = (arr: any[], fn: (node: any) => any): any[] =>
    arr.map((item) => {
      return {
        ...item,
        ...fn(item),
        children: item.children ? addKey(item.children, fn) : [], // 这里要判断原数据有没有子级如果没有判断会报错
      };
    });