JS高效算法：扁平数据转树形结构O(n)实现详解

扁平数组转树形结构的痛点

在处理将一维数组转换为多层级结构的需求时，最直观但效率最低的方法是使用多层for循环嵌套。这种方式不仅代码冗余、可读性差，而且随着层级深度的增加，嵌套层数也随之增加，导致维护困难且执行效率低下。

为此，我们实现了一种时间复杂度为O(n)的算法，旨在将一个代表菜单结构的一维扁平数组，高效地转换为一个多层级的树形结构对象。

为了实现这一转换，输入的一维数组中的每个元素必须包含特定的属性字段：

一个唯一的标识符id。
一个指向父级节点id的parent_id属性。

其他业务相关字段，例如在本例的菜单场景中，包含菜单名称(menu_name)和访问路径(menu_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'
  }
]

O(n)算法实现与原理

核心算法实现名为buildTree。

该算法的核心思想如下：

首先，遍历输入数组，将每个节点存入一个临时对象temp中，以节点的id作为键。例如，对于节点{id: '2-3', parent_id: '2', ...}，在temp中将其存储为temp['2-3'] = {id: '2-3', parent_id: '2', ...}。这一步建立了id到节点对象的映射。

接着，再次遍历temp对象。利用之前保证的“父节点先于子节点”的顺序，通过代码 temp[temp[i].parent_id].children[temp[i].id] = temp[i] 建立父子连接。由于父节点已存在于temp中，可以直接通过temp[temp[i].parent_id]获取父节点对象，并在其children属性下添加当前子节点的引用。若某节点没有parent_id（即顶层节点），则直接将其放入最终的树根对象tree中。


/**
 * 将一维的扁平数组转换为多层级对象
 * @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'
  }];

此方案由一名大二学生提出，相较于老师使用的三层for循环嵌套方案，该算法在简洁性和性能上均有显著提升。

以上就是关于JavaScript将扁平数据转为树形结构的高效算法介绍。如需了解更多相关技术内容，请查阅本站历史文章或继续浏览后续内容，感谢支持。

JavaScript实现O(n)复杂度扁平数组转树形结构算法

扁平数组转树形结构的痛点

O(n)算法实现与原理

测试验证与性能分析

实用工具推荐