夜猫子的知识栈 夜猫子的知识栈
首页
  • 前端文章

    • JavaScript
  • 学习笔记

    • 《JavaScript教程》
    • 《Web Api》
    • 《ES6教程》
    • 《Vue》
    • 《React》
    • 《TypeScript》
    • 《Git》
    • 《Uniapp》
    • 小程序笔记
    • 《Electron》
    • JS设计模式总结
  • 《前端架构》

    • 《微前端》
    • 《权限控制》
    • monorepo
  • 全栈项目

    • 任务管理日历
    • 无代码平台
    • 图书管理系统
  • HTML
  • CSS
  • Nodejs
  • Midway
  • Nest
  • MySql
  • 其他
  • 技术文档
  • GitHub技巧
  • 博客搭建
  • Ajax
  • Vite
  • Vitest
  • Nuxt
  • UI库文章
  • Docker
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 友情链接
收藏
  • 分类
  • 标签
  • 归档
GitHub (opens new window)

夜猫子

前端练习生
首页
  • 前端文章

    • JavaScript
  • 学习笔记

    • 《JavaScript教程》
    • 《Web Api》
    • 《ES6教程》
    • 《Vue》
    • 《React》
    • 《TypeScript》
    • 《Git》
    • 《Uniapp》
    • 小程序笔记
    • 《Electron》
    • JS设计模式总结
  • 《前端架构》

    • 《微前端》
    • 《权限控制》
    • monorepo
  • 全栈项目

    • 任务管理日历
    • 无代码平台
    • 图书管理系统
  • HTML
  • CSS
  • Nodejs
  • Midway
  • Nest
  • MySql
  • 其他
  • 技术文档
  • GitHub技巧
  • 博客搭建
  • Ajax
  • Vite
  • Vitest
  • Nuxt
  • UI库文章
  • Docker
  • 学习
  • 面试
  • 心情杂货
  • 实用技巧
  • 友情链接
收藏
  • 分类
  • 标签
  • 归档
GitHub (opens new window)
  • JavaScript文章

    • 33个非常实用的JavaScript一行代码
    • new命令原理
    • ES5面向对象
    • ES6面向对象
    • 多种数组去重性能对比
    • 获取ip地址
    • ES6扩展符运用
    • file、base64和blob互相转化
    • 图片转base64格式
    • 实现异步队列
    • websocket实现二维码扫描
    • js动画之requestAnimationFrame
    • JS随机打乱数组
    • 判断是否为移动端浏览器
    • 将一维数组按指定长度转为二维数组
    • 防抖与节流函数
    • 时间戳与倒计时
    • JS获取和修改url参数
    • 比typeof运算符更准确的类型判断
    • 前端下载excel文件
    • 商品sku算法
    • 数组与对象的互相转化
    • Javascript原生事件监听及手动触发
    • JS编码与转码
    • 树结构与扁平化相互转换
      • 测试数据
      • array to tree 【生成树结构】
        • 递归
        • 循环
        • 不依赖根id的转换方式
      • tree to array 【扁平化数据】
        • 递归
        • 循环
      • 拓展:根据id拿到所有父级id
      • 拓展:根据条件进行筛选
      • 拓展:根据条件获取节点及其子节点
      • 拓展:根据条件修改属性
    • 实现微信登录
    • 判断两个对象值是否相等
    • 常用表单验证
    • 在H5中实现OCR拍照识别身份证功能
    • 滚动条元素定位
    • 获取目标容器内的元素列表
    • 微信H5支付
    • 对象除空
    • 获取指定链接的参数
    • js中的函数注释
    • 大模型流式数据前端实现
    • 定高虚拟列表
    • 不定高虚拟列表
    • 虚拟表格
    • 移动端文件预览
    • 浏览器缓存机制
    • 前端从剪切板获取word图片
  • 前端架构

  • 学习笔记

  • 全栈项目

  • 前端
  • JavaScript文章
夜猫子
2022-10-13
目录

树结构与扁平化相互转换

# 测试数据

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: []
            }
          ]
        }
      ]
    }
  ]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

定义方法获取指定 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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

# 循环

利用 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];
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

# 不依赖根id的转换方式

// 扁平化转为树状列表(不依赖根id)
export function arrayToTree(nodes, options = {}) {
  const { id = 'id', parentId = 'parentId', children = 'children' } = options
  // 创建一个Map来存储所有节点
  const map = new Map()
  // 用于存储根节点的数组
  const roots = []

  // 遍历数组,构建节点映射
  nodes.forEach((item) => {
    // 如果parentId在数组中不存在,则将其视为根节点并设置parentId为null
    const _parentId = nodes.some((i) => i[id] === item[parentId]) ? item[parentId] : null
    const node = { ...item, [children]: [] }
    map.set(item[id], node)
    // 如果节点是无根节点(parentId为null),则添加到根节点数组中
    if (!_parentId) {
      roots.push(node)
    }
  })
  // 为每个非根节点设置其父节点
  map.forEach((node) => {
    if (node[parentId] !== null) {
      const parentNode = map.get(node[parentId])
      if (parentNode) {
        parentNode[children].push(node)
      }
    }
  })

  // 返回根节点数组
  return roots
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

# tree to array 【扁平化数据】

# 递归

// 树结构转数组
/**
 * @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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

# 循环

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

/**
 * @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);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

# 拓展:根据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];
      }
   }
}
1
2
3
4
5
6
7
8
9
10
11

# 拓展:根据条件进行筛选

/**
 * 递归过滤节点,生成新的树结构
 * @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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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

// 条件检索对应节点及其子节点
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: []},
    ]},
  ]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

# 拓展:根据条件修改属性

const editTreeitem = (arr: any[], fn: (node: any) => any): any[] =>
    arr.map((item) => {
      return {
        ...item,
        ...fn(item),
        children: item.children ? editTreeitem(item.children, fn) : [],
      };
    });
1
2
3
4
5
6
7
8
编辑 (opens new window)
上次更新: 2025/5/29 13:49:25
JS编码与转码
实现微信登录

← JS编码与转码 实现微信登录→

最近更新
01
IoC 解决了什么痛点问题?
03-10
02
如何调试 Nest 项目
03-10
03
Provider注入对象
03-10
更多文章>
Copyright © 2019-2025 Study | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式