javascript将扁平的数据转为树形结构的高效率算法
作者:huyao_road 发布时间:2024-02-24 05:26:01
当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多个for循环嵌套,但是这样做有一些缺点,那就是效率太低、而且有多少层就需要嵌套几个for循环,不好用。
我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构。
一位数组中每一个元素必须要包含以下属性:
拥有一个唯一的id
拥有一个parent_id, 这个id指向它父级的id
其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息。
注:
在层级结构中,第一层的parent_id需要为0.
父节点在数组中的位置需要在子节点前,即 节点3必须排在节点3-2之前
扁平数组例:
var menu_list = [{
id: '1',
menu_name: '设置',
menu_url: 'setting',
parent_id: 0
}, {
id: '1-1',
menu_name: '权限设置',
menu_url: 'setting.permission',
parent_id: '1'
}, {
id: '1-1-1',
menu_name: '用户管理列表',
menu_url: 'setting.permission.user_list',
parent_id: '1-1'
}, {
id: '1-1-2',
menu_name: '用户管理新增',
menu_url: 'setting.permission.user_add',
parent_id: '1-1'
}, {
id: '1-1-3',
menu_name: '角色管理列表',
menu_url: 'setting.permission.role_list',
parent_id: '1-1'
}, {
id: '1-2',
menu_name: '菜单设置',
menu_url: 'setting.menu',
parent_id: '1'
}, {
id: '1-2-1',
menu_name: '菜单列表',
menu_url: 'setting.menu.menu_list',
parent_id: '1-2'
}, {
id: '1-2-2',
menu_name: '菜单添加',
menu_url: 'setting.menu.menu_add',
parent_id: '1-2'
}, {
id: '2',
menu_name: '订单',
menu_url: 'order',
parent_id: 0
}, {
id: '2-1',
menu_name: '报单审核',
menu_url: 'order.orderreview',
parent_id: '2'
}, {
id: '2-2',
menu_name: '退款管理',
menu_url: 'order.refundmanagement',
parent_id: '2'
}
]
实现算法buildTree
算法思想:
先将数组中的每一个节点放到temp对象中(创建set)
即数组中有{id: '2-3', parent_id: '2',...}这样一个节点,需要将他放到temp中变成 '2-3': {id: '2-3', parent_id: '2',...}这种JSON结构
直接遍历整个temp对象,通过这句代码 temp[temp[i].parent_id].children[temp[i].id] = temp[i]; 将当前子节点与父节点建立连接。是因为我们保证了父节点一定在子节点前,那么当子节点出现的时候就直接可以用temp[temp[i].parent_id]来查找到父节点这个时候先父节点的children对象中添加一个引用即可。
/**
* 将一维的扁平数组转换为多层级对象
* @param {[type]} list 一维数组,数组中每一个元素需包含id和parent_id两个属性
* @return {[type]} tree 多层级树状结构
*/
function buildTree(list){
let temp = {};
let tree = {};
for(let i in list){
temp[list[i].id] = list[i];
}
for(let i in temp){
if(temp[i].parent_id) {
if(!temp[temp[i].parent_id].children) {
temp[temp[i].parent_id].children = new Object();
}
temp[temp[i].parent_id].children[temp[i].id] = temp[i];
} else {
tree[temp[i].id] = temp[i];
}
}
return tree;
}
测试结果:
可以看到函数成功地构建了多级的树状结构
这个算法的效率是极高的,比多重for循环来的好得多。
以下是测试数据,用时只需5毫秒左右:
var menu_list = [{
id: '1',
menu_name: '设置',
menu_url: 'setting',
parent_id: 0
}, {
id: '1-1',
menu_name: '权限设置',
menu_url: 'setting.permission',
parent_id: '1'
}, {
id: '1-1-1',
menu_name: '用户管理列表',
menu_url: 'setting.permission.user_list',
parent_id: '1-1'
}, {
id: '1-1-2',
menu_name: '用户管理新增',
menu_url: 'setting.permission.user_add',
parent_id: '1-1'
}, {
id: '1-1-3',
menu_name: '角色管理列表',
menu_url: 'setting.permission.role_list',
parent_id: '1-1'
}, {
id: '1-1-4',
menu_name: '角色管理新增',
menu_url: 'setting.permission.role_add',
parent_id: '1-1'
}, {
id: '1-2',
menu_name: '菜单设置',
menu_url: 'setting.menu',
parent_id: '1'
}, {
id: '1-2-1',
menu_name: '菜单列表',
menu_url: 'setting.menu.menu_list',
parent_id: '1-2'
}, {
id: '1-2-2',
menu_name: '菜单添加',
menu_url: 'setting.menu.menu_add',
parent_id: '1-2'
}, {
id: '2',
menu_name: '订单',
menu_url: 'order',
parent_id: 0
}, {
id: '2-1',
menu_name: '报单审核',
menu_url: 'order.orderreview',
parent_id: '2'
}, {
id: '2-2',
menu_name: '退款管理',
menu_url: 'order.refundmanagement',
parent_id: '2'
}, {
id: '2-3',
menu_name: '实物订单',
menu_url: 'order.realorder',
parent_id: '2'
}, {
id: '2-1-1',
menu_name: '全部报单',
menu_url: 'order.orderreview.all',
parent_id: '2-1'
}, {
id: '2-2-1',
menu_name: '所有记录',
menu_url: 'order.refundmanagement.all',
parent_id: '2-2'
}, {
id: '2-2-2',
menu_name: '待处理',
menu_url: 'order.refundmanagement.wait',
parent_id: '2-2'
}, {
id: '2-2-3',
menu_name: '退款原因',
menu_url: 'order.refundmanagement.result',
parent_id: '2-2'
}, {
id: '2-3-1',
menu_name: '实物订单管理',
menu_url: 'order.realorder.list',
parent_id: '2-3'
}, {
id: '3',
menu_name: '商品',
menu_url: 'commodity',
parent_id: 0
}, {
id: '3-1',
menu_name: '分类管理',
menu_url: 'commodity.classifieldmanagement',
parent_id: '3'
}, {
id: '3-1-1',
menu_name: '管理',
menu_url: 'commodity.classifieldmanagement.management',
parent_id: '3-1'
}, {
id: '3-1-2',
menu_name: '编辑或新增',
menu_url: 'commodity.classifieldmanagement.edit',
parent_id: '3-1'
}, {
id: '3-2',
menu_name: '品牌管理',
menu_url: 'commodity.brandmanagement',
parent_id: '3'
}, {
id: '3-2-1',
menu_name: '管理',
menu_url: 'commodity.brandmanagement.management',
parent_id: '3-2'
}, {
id: '3-2-2',
menu_name: '编辑或新增',
menu_url: 'commodity.brandmanagement.edit',
parent_id: '3-2'
}, {
id: '3-3',
menu_name: '商品管理',
menu_url: 'commodity.commoditymanagement',
parent_id: '3'
}, {
id: '3-3-1',
menu_name: '管理',
menu_url: 'commodity.commoditymanagement.management',
parent_id: '3-3'
}, {
id: '3-3-2',
menu_name: '编辑或新增',
menu_url: 'commodity.commoditymanagement.edit',
parent_id: '3-3'
}, {
id: '3-4',
menu_name: '类型管理',
menu_url: 'commodity.typeManagement',
parent_id: '3'
}, {
id: '3-4-1',
menu_name: '管理',
menu_url: 'commodity.typeManagement.management',
parent_id: '3-4'
}, {
id: '3-4-2',
menu_name: '编辑或新增',
menu_url: 'commodity.typeManagement.edit',
parent_id: '3-4'
}];
这是我一个大二学生想出来的,挺开心的,因为当时看到老师用的3个for循环嵌套。嘿嘿嘿
来源:https://blog.csdn.net/qq_37746973/article/details/78662177
猜你喜欢
- 一直记不住在jupyter notebook配置多环境编译器技巧,今总结于此,也希望对其他小伙伴有所帮助,如果有用请点赞!1.对window
- 我们在Python中经常使用会用到matplotlib画图,有些曲线和点的形状、颜色信息长时间不用就忘了,整理一下便于查找。安装matplo
- 加了三个验证漏洞以及四个getshell方法# /usr/bin/env python3# -*- coding: utf-8 -*-# @
- 一、Python 的 IDE —— PyCharm1.1 集成开发环境(IDE)集成开发环境(IDE,Integrated Developm
- mysql数据库没有增量备份的机制,当数据量太大的时候备份是一个很大的问题。还好mysql数据库提供了一种主从备份的机制,其实就是把主数据库
- MySQL 提供了一个很有意思的Engine:Federated!如果你了解Linux下面的Link的话,就应该很好理解这个Federate
- 在docker中安装mysqlubuntu官方镜像是精简的ubuntu系统,很多软件和库没有安装,所以直接安装mysql的话依赖较多,建议直
- MySQL是一个真正的多用户、多线程SQL数据库服务器。MySQL是以一个客户机/服务器结构的实现,它由一个服务器守护程序mys
- 堆是一种特殊的树形结构, 堆中的数据存储满足一定的堆序。堆排序是一种选择排序, 其算法复杂度, 时间复杂度相对于其他的排序算法都有很大的优势
- python将JPG、BMP图片转化为bgrimport cv2imgpath = "./0.png"#图片路径save
- 前言:今天我来分享几个好用到爆的Pycharm插件,在安装上之后,你的编程效率、工作效率都能够得到极大地提升。一、安装方法插件的安装方法一点
- 一、开发工具**Python****版本:**3.6.4相关模块:DecryptLogin模块;argparse模块;以及一些Python自
- 1. 整数、浮点数和复数Python2中区分整型int、长整型longPython3中只有统称为 整型int浮点数即带有小数点的数字,因为浮
- 本文实例讲述了Python嵌套函数,作用域与偏函数用法。分享给大家供大家参考,具体如下:内嵌函数(嵌套函数):意思:在函数里面再定义一个新的
- 本文实例讲述了MySQL Union合并查询数据及表别名、字段别名用法。分享给大家供大家参考,具体如下:union关键字SELECT s_i
- 例如:我们在百度中搜索 词典网,则网址后面的参数就是http://www.baidu.com/s?cl=3&wd=%B4%CA%B5
- 1.Airbus Ship Detection Challengeurl: https://www.kaggle.com/comp
- 我们大致会在下列几种情况下用到: 一、文件操作(FileSystemObject)<%@ IMPORT
- 前言在学习SQL 2012基础教程过程中会时不时穿插其他内容来进行讲解,相信看过SQL Server 2012 T-SQL基础教程的童鞋知道
- 一个朋友给她的朋友买礼物。撕心裂肺、绞尽脑汁。最后蹦出来一个主意:“送打火机”我不知道小妞们通过哪的投票,就这么断定男人都喜欢打火机。导致一