javascript将扁平的数据转为树形结构 O(n)级算法
当咱们须要将一个一维数组转换成一个多层结构的时候，最简单可是最慢的就是多个for循环嵌套，可是这样作有一些缺点，那就是效率过低、并且有多少层就须要嵌套几个for循环，很差用。javascript
我实现了用O(n)级算法将 一个扁平的数组即一维数组表明的菜单结构转换成一个多层级的菜单结构。java
一位数组中每个元素必需要包含如下属性：算法
- 拥有一个惟一的id
- 拥有一个parent_id, 这个id指向它父级的id
其余则为每个元素中的一些信息，我这里是菜单，就有菜单的名称和url信息。数组
注：函数
- 在层级结构中，第一层的parent_id须要为0.
扁平数组例：测试
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'
}
]
实现算法buildTreeui
算法思想：url
- 先将数组中的每个节点放到temp对象中（建立map）
即数组中有{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;
}
测试结果：code
能够看到函数成功地构建了多级的树状结构对象
这个算法的效率是极高的，比多重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循环嵌套。嘿嘿嘿