当我们需要将一个一维数组转换成一个多层结构的时候,最简单但是最慢的就是多的个循环嵌套,但是这样做有一些缺点,那就是效率太低,而且有多少层就需要嵌套几的个循环,不好用。
我实现了用O (n)级算法将一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构。
一位数组中每一个元素必须要包含以下属性:
<李>拥有一个唯一的id
<李>拥有一个parent_id,这个id指向它父级的id
其他则为每一个元素中的一些信息,我这里是菜单,就有菜单的名称和url信息。
注:
<李>在层级结构中,第一层的parent_id需要为0。
<李>父节点在数组中的位置需要在子节点前,即节点3必须排在节点3 - 2之前李
扁平数组例:
var menu_list=[{
id: ' 1 ',
menu_name:“设置”,
menu_url:“设置”,
parent_id: 0
},{
id:“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’
},{
id:“1-1-2”,
menu_name:“用户管理新增”,
menu_url:“setting.permission.user_add”,
parent_id:‘1’
},{
id:“1-1-3”,
menu_name:“角色管理列表”,
menu_url:“setting.permission.role_list”,
parent_id:‘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:“订单”,
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”, parent_id:‘2’,……}这样一个节点,需要将他放到临时表中变成“2 - 3”:,{id:“2 - 3”, parent_id:‘2’,…}这种JSON结构
直接遍历整个临时对象,通过这句代码,,临时[临时[我].parent_id]定格[临时[我]。id]=temp[我];,,将当前子节点与父节点建立连接。是因为我们保证了父节点一定在子节点前,那么当子节点出现的时候就直接可以用临时(临时[我].parent_id]来查找到父节点这个时候先父节点的孩子对象中添加一个引用即可。
/* *
*将一维的扁平数组转换为多层级对象
* @param{[型]}列表一维数组,数组中每一个元素需包含id和parent_id两个属性
* @return{[型]}树多层级树状结构
*/函数buildTree(列表){
让temp={};
让树={};
(让我的列表){
临时[[我]列表。id]=[我]列表;
}
(让我临时){
如果(临时[我].parent_id) {
如果(!临时(临时[我].parent_id]定格){
临时(临时[我].parent_id]。孩子=新对象();
}
临时(临时[我].parent_id)定格(临时[我]。id]=temp[我];
其他}{
树(临时[我]。id]=temp[我];
}
}
返回树;
}
测试结果:
可以看到函数成功地构建了多级的树状结构
这个算法的效率是极高的,比多重的循环来的好得多。
以下是测试数据,用时只需5毫秒左右:
var menu_list=[{
id: ' 1 ',
menu_name:“设置”,
menu_url:“设置”,
parent_id: 0
},{
id:“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’
},{
id:“1-1-2”,
menu_name:“用户管理新增”,
menu_url:“setting.permission.user_add”,
parent_id:‘1’
},{
id:“1-1-3”,
menu_name:“角色管理列表”,
menu_url:“setting.permission.role_list”,
parent_id:‘1’
},{
id:“1-1-4”,
menu_name:“角色管理新增”,
menu_url:“setting.permission.role_add”,
parent_id:‘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:“订单”,
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:“商品”,
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”,
menu_name:“商品管理”,
menu_url:“commodity.commoditymanagement”,
parent_id:‘3’
},{
id:“3-3-1”,
menu_name:“管理”,
menu_url:“commodity.commoditymanagement.management”,
parent_id:‘3’
},{
id:“3-3-2”,
menu_name:“编辑或新增”,
menu_url:“commodity.commoditymanagement.edit”,
parent_id:‘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”
},{
null
null
null
null
null
null
null
null
