javascript将扁平的数据转为树形结构 O(n)级算法

左手的ㄟ右手 2022-06-04 00:10 159阅读 0赞

当我们需要将一个一维数组转换成一个多层结构的时候，最简单但是最慢的就是多个for循环嵌套，但是这样做有一些缺点，那就是效率太低、而且有多少层就需要嵌套几个for循环，不好用。

我实现了用O(n)级算法将 一个扁平的数组即一维数组代表的菜单结构转换成一个多层级的菜单结构。

一位数组中每一个元素必须要包含以下属性：

1.  拥有一个唯一的id
2.  拥有一个parent\_id, 这个id指向它父级的id

其他则为每一个元素中的一些信息，我这里是菜单，就有菜单的名称和url信息。

**注：**

1.  在层级结构中，第一层的parent\_id需要为0.

扁平数组例：

实现算法buildTree

算法思想：

1.  先将数组中的每一个节点放到temp对象中（创建map）  
    即数组中有\{id: '2-3', parent\_id: '2',...\}这样一个节点，需要将他放到temp中变成 '2-3': \{id: '2-3', parent\_id: '2',...\}这种JSON结构
2.  直接遍历整个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;
    }

测试结果：

可以看到函数成功地构建了多级的树状结构

![70][]

这个算法的效率是极高的，比多重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循环嵌套。嘿嘿嘿

[70]: /images/20220604/420697478d4c4337a4632a43021cd059.png