测试数据

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 存储数组数据，并且每次循环处理对应的元素，利用指针指向内存空间的原理

// 数组转树结构
// 利用 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];
}

不依赖根id的转换方式

// 扁平化转为树状列表（不依赖根id）
export function arrayToTree(nodes, options = {}) {
  const { id = 'id', parentId = 'parentId', children = 'children' } = options
  const nodeMap = new Map()
  const roots = []

  // 创建节点映射（排除原始children属性）
  nodes.forEach((item) => {
    // 创建新节点时排除原始children属性
    const { [children]: _, ...cleanItem } = item
    nodeMap.set(item[id], { ...cleanItem })
  })

  // 2. 构建树结构并收集根节点
  nodes.forEach((item) => {
    const node = nodeMap.get(item[id])
    const parent = nodeMap.get(item[parentId])

    if (parent) {
      parent[children] = parent[children] || []
      parent[children].push(node)
    } else {
      roots.push(node)
    }
  })

  return roots
}

tree to array 【扁平化数据】

递归

function treeToArrayUniqueById(tree) {
  const queue = [...tree];         // 使用队列进行广度优先遍历（BFS）
  const result = [];               // 最终输出的扁平数组
  const seenIds = new Map();       // 用于记录已处理过的节点 id

  while (queue.length > 0) {
    const node = queue.shift();

    // 如果该 id 已存在，跳过这个节点
    if (seenIds.has(node.id)) {
      continue;
    }

    // 记录该 id 已处理
    seenIds.set(node.id, true);

    // 加入结果数组
    result.push(node);

    // 继续处理子节点
    if (node.children && node.children.length > 0) {
      queue.push(...node.children);
    }
  }

  return result;
}

循环

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

function treeToArrayRecursiveUniqueById(tree) {
  const result = [];
  const seenIds = new Set();

  function traverse(node) {
    if (seenIds.has(node.id)) return;
    seenIds.add(node.id);
    result.push(node);

    if (node.children && node.children.length > 0) {
      for (let child of node.children) {
        traverse(child);
      }
    }
  }

  for (let root of tree) {
    traverse(root);
  }

  return result;
}

拓展：根据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 editTreeitem = (arr: any[], fn: (node: any) => any): any[] =>
    arr.map((item) => {
      return {
        ...item,
        ...fn(item),
        children: item.children ? editTreeitem(item.children, fn) : [],
      };
    });

拓展：通过选中 id 返回子级全部选中的父级 id 和其他子级 id

function getFullySelectedParents(tree, selectedIds) {
  const result = [];

  function traverse(node) {
    // 如果当前节点是叶子节点
    if (!node.children || node.children.length === 0) {
      // 如果当前节点被选中，则返回 [id]
      return selectedIds.includes(node.id) ? [node.id] : [];
    }

    let allChildrenSelected = true;
    const childResults = [];

    for (const child of node.children) {
      const childResult = traverse(child);
      if (childResult.length === 0) {
        allChildrenSelected = false;
      } else {
        childResults.push(...childResult);
      }
    }

    // 如果所有子节点都被选中，则返回父节点的 id
    if (allChildrenSelected && childResults.length === node.children.length) {
      return [node.id];
    }

    // 否则返回具体的子节点 id
    return childResults;
  }

  for (const root of tree) {
    result.push(...traverse(root));
  }

  return result;
}

如果反向操作，获取选中节点的所有最下级子项

拓展：获取选中节点的所有最下级子项id

function getLeafNodes(tree, selectedIds) {
  const leafNodes = [];

  // 递归查找某个节点下的所有叶子节点
  function findLeafNodes(node) {
    if (!node.children || node.children.length === 0) {
      leafNodes.push(node.id);
      return;
    }

    for (const child of node.children) {
      findLeafNodes(child);
    }
  }

  // 遍历选中的节点，找到对应子树并提取叶子节点
  function traverseTree(tree) {
    let result = [];
    for (const node of tree) {
      if (selectedIds.includes(node.id)) {
        const leaves = [];
        leafNodes.length = 0; // 清空缓存
        findLeafNodes(node);
        result = result.concat(leafNodes);
      } else if (node.children && node.children.length > 0) {
        result = result.concat(traverseTree(node.children));
      }
    }
    return result;
  }

  return traverseTree(tree);
}