快捷導(dǎo)航

javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹(shù)形結(jié)構(gòu)的高效率算法

更新時(shí)間：2020年02月27日 14:40:33 作者：huyao_road

這篇文章主要介紹了javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹(shù)形結(jié)構(gòu)的高效率算法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

當(dāng)我們需要將一個(gè)一維數(shù)組轉(zhuǎn)換成一個(gè)多層結(jié)構(gòu)的時(shí)候，最簡(jiǎn)單但是最慢的就是多個(gè)for循環(huán)嵌套，但是這樣做有一些缺點(diǎn)，那就是效率太低、而且有多少層就需要嵌套幾個(gè)for循環(huán)，不好用。

我實(shí)現(xiàn)了用O(n)級(jí)算法將一個(gè)扁平的數(shù)組即一維數(shù)組代表的菜單結(jié)構(gòu)轉(zhuǎn)換成一個(gè)多層級(jí)的菜單結(jié)構(gòu)。

一位數(shù)組中每一個(gè)元素必須要包含以下屬性：

擁有一個(gè)唯一的id
擁有一個(gè)parent_id, 這個(gè)id指向它父級(jí)的id

其他則為每一個(gè)元素中的一些信息，我這里是菜單，就有菜單的名稱和url信息。

注：

在層級(jí)結(jié)構(gòu)中，第一層的parent_id需要為0.
父節(jié)點(diǎn)在數(shù)組中的位置需要在子節(jié)點(diǎn)前，即節(jié)點(diǎn)3必須排在節(jié)點(diǎn)3-2之前

扁平數(shù)組例：

var menu_list = [{
   id: '1',
   menu_name: '設(shè)置',
   menu_url: 'setting',
   parent_id: 0
  }, {
   id: '1-1',
   menu_name: '權(quán)限設(shè)置',
   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: '菜單設(shè)置',
   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: '報(bào)單審核',
   menu_url: 'order.orderreview',
   parent_id: '2'
  }, {
   id: '2-2',
   menu_name: '退款管理',
   menu_url: 'order.refundmanagement',
   parent_id: '2'
  }
]

實(shí)現(xiàn)算法buildTree

算法思想：

先將數(shù)組中的每一個(gè)節(jié)點(diǎn)放到temp對(duì)象中（創(chuàng)建set）
即數(shù)組中有{id: '2-3', parent_id: '2',...}這樣一個(gè)節(jié)點(diǎn)，需要將他放到temp中變成 '2-3': {id: '2-3', parent_id: '2',...}這種JSON結(jié)構(gòu)

直接遍歷整個(gè)temp對(duì)象，通過(guò)這句代碼 temp[temp[i].parent_id].children[temp[i].id] = temp[i]; 將當(dāng)前子節(jié)點(diǎn)與父節(jié)點(diǎn)建立連接。是因?yàn)槲覀儽ＷC了父節(jié)點(diǎn)一定在子節(jié)點(diǎn)前，那么當(dāng)子節(jié)點(diǎn)出現(xiàn)的時(shí)候就直接可以用temp[temp[i].parent_id]來(lái)查找到父節(jié)點(diǎn)這個(gè)時(shí)候先父節(jié)點(diǎn)的children對(duì)象中添加一個(gè)引用即可。

/**
 * 將一維的扁平數(shù)組轉(zhuǎn)換為多層級(jí)對(duì)象
 * @param {[type]} list 一維數(shù)組，數(shù)組中每一個(gè)元素需包含id和parent_id兩個(gè)屬性 
 * @return {[type]} tree 多層級(jí)樹(shù)狀結(jié)構(gòu)
 */
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;
}

測(cè)試結(jié)果：

可以看到函數(shù)成功地構(gòu)建了多級(jí)的樹(shù)狀結(jié)構(gòu)

這個(gè)算法的效率是極高的，比多重for循環(huán)來(lái)的好得多。

以下是測(cè)試數(shù)據(jù)，用時(shí)只需5毫秒左右：

var menu_list = [{
   id: '1',
   menu_name: '設(shè)置',
   menu_url: 'setting',
   parent_id: 0
  }, {
   id: '1-1',
   menu_name: '權(quán)限設(shè)置',
   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: '菜單設(shè)置',
   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: '報(bào)單審核',
   menu_url: 'order.orderreview',
   parent_id: '2'
  }, {
   id: '2-2',
   menu_name: '退款管理',
   menu_url: 'order.refundmanagement',
   parent_id: '2'
  }, {
   id: '2-3',
   menu_name: '實(shí)物訂單',
   menu_url: 'order.realorder',
   parent_id: '2'
  }, {
   id: '2-1-1',
   menu_name: '全部報(bào)單',
   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: '實(shí)物訂單管理',
   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'
  }];

這是我一個(gè)大二學(xué)生想出來(lái)的，挺開(kāi)心的，因?yàn)楫?dāng)時(shí)看到老師用的3個(gè)for循環(huán)嵌套。嘿嘿嘿

到此這篇關(guān)于javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹(shù)形結(jié)構(gòu)的高效率算法的文章就介紹到這了,更多相關(guān)javascript 扁平數(shù)據(jù)轉(zhuǎn)為樹(shù)形結(jié)構(gòu)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: