javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹形結(jié)構(gòu)的高效率算法
更新時間：2020年02月27日 14:40:33 作者：huyao_road
這篇文章主要介紹了javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹形結(jié)構(gòu)的高效率算法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
當(dāng)我們需要將一個一維數(shù)組轉(zhuǎn)換成一個多層結(jié)構(gòu)的時候，最簡單但是最慢的就是多個for循環(huán)嵌套，但是這樣做有一些缺點，那就是效率太低、而且有多少層就需要嵌套幾個for循環(huán)，不好用。
我實現(xiàn)了用O(n)級算法將 一個扁平的數(shù)組即一維數(shù)組代表的菜單結(jié)構(gòu)轉(zhuǎn)換成一個多層級的菜單結(jié)構(gòu)。
一位數(shù)組中每一個元素必須要包含以下屬性：
- 擁有一個唯一的id
- 擁有一個parent_id, 這個id指向它父級的id
其他則為每一個元素中的一些信息，我這里是菜單，就有菜單的名稱和url信息。
注：
- 在層級結(jié)構(gòu)中，第一層的parent_id需要為0.
- 父節(jié)點在數(shù)組中的位置需要在子節(jié)點前，即 節(jié)點3必須排在節(jié)點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: '報單審核',
menu_url: 'order.orderreview',
parent_id: '2'
}, {
id: '2-2',
menu_name: '退款管理',
menu_url: 'order.refundmanagement',
parent_id: '2'
}
]
實現(xiàn)算法buildTree
算法思想：
先將數(shù)組中的每一個節(jié)點放到temp對象中（創(chuàng)建set）
即數(shù)組中有{id: '2-3', parent_id: '2',...}這樣一個節(jié)點，需要將他放到temp中變成 '2-3': {id: '2-3', parent_id: '2',...}這種JSON結(jié)構(gòu)
直接遍歷整個temp對象，通過這句代碼 temp[temp[i].parent_id].children[temp[i].id] = temp[i]; 將當(dāng)前子節(jié)點與父節(jié)點建立連接。是因為我們保證了父節(jié)點一定在子節(jié)點前，那么當(dāng)子節(jié)點出現(xiàn)的時候就直接可以用temp[temp[i].parent_id]來查找到父節(jié)點這個時候先父節(jié)點的children對象中添加一個引用即可。
/**
* 將一維的扁平數(shù)組轉(zhuǎn)換為多層級對象
* @param {[type]} list 一維數(shù)組，數(shù)組中每一個元素需包含id和parent_id兩個屬性
* @return {[type]} tree 多層級樹狀結(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;
}
測試結(jié)果：
可以看到函數(shù)成功地構(gòu)建了多級的樹狀結(jié)構(gòu)
這個算法的效率是極高的，比多重for循環(huán)來的好得多。
以下是測試數(shù)據(jù)，用時只需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: '報單審核',
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'
}];
這是我一個大二學(xué)生想出來的，挺開心的，因為當(dāng)時看到老師用的3個for循環(huán)嵌套。嘿嘿嘿
到此這篇關(guān)于javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹形結(jié)構(gòu)的高效率算法的文章就介紹到這了,更多相關(guān)javascript 扁平數(shù)據(jù)轉(zhuǎn)為樹形結(jié)構(gòu)內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
JS動畫實現(xiàn)回調(diào)地獄promise的實例代碼詳解
這篇文章主要介紹了JS動畫實現(xiàn)回調(diào)地獄promise的實例代碼詳解,需要的朋友可以參考下2018-11-11
我不知道是否有什么標(biāo)準(zhǔn)規(guī)定不允許修改id屬性，或者不建議修改id屬性，總之IE對此支持不佳。2008-09-09
今天小編大家分享一篇layer.open 獲取不到表單信息的解決方法，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09
js中substr,substring,indexOf,lastIndexOf的用法小結(jié)
本篇文章主要是對js中substr,substring,indexOf,lastIndexOf的用法進(jìn)行了總結(jié)介紹，需要的朋友可以過來參考下，希望對大家有所幫助2013-12-12
最近項目經(jīng)理交給我一下新項目，要實現(xiàn)關(guān)系圖，需要在線條上繪制文字。下面小編把使用textPath實現(xiàn)線條上的文字功能分享到腳本之家平臺供大家參考2017-12-12
Bootstrap入門書籍之（五）導(dǎo)航條、分頁導(dǎo)航
這篇文章主要介紹了Bootstrap入門書籍之（五）導(dǎo)航條、分頁導(dǎo)航的相關(guān)資料,需要的朋友可以參考下2016-02-02
處理文本部分內(nèi)容的TextRange對象應(yīng)用實例
TextRange是用來表現(xiàn)HTML元素中文字的對象，是一個用于處理JavaScript對象文本部分內(nèi)容的一個對象2014-07-07
JavaScript中Function函數(shù)與Object對象的關(guān)系
這篇文章主要介紹了JavaScript中Function函數(shù)與Object對象的關(guān)系的相關(guān)資料,需要的朋友可以參考下2015-12-12
如何使用uniapp開發(fā)微信小程序獲取當(dāng)前位置詳解
uni-app小程序項目無法直接獲取到地理位置,只能通過獲取到的經(jīng)緯度,調(diào)用第三方地圖Api獲取,下面這篇文章主要給大家介紹了關(guān)于如何使用uniapp開發(fā)微信小程序獲取當(dāng)前位置的相關(guān)資料,需要的朋友可以參考下2022-10-10
JavaScript通過RegExp使用正則表達(dá)式過程詳解
正則表達(dá)式用于定義一些字符串的規(guī)則。計算機可以根據(jù)正則表達(dá)式，來檢查一個字符串是否符合指定的規(guī)則，或者將字符串中符合規(guī)則的內(nèi)容提取出來。RegExp的意思是 Regular expression。使用typeof檢查正則對象，會返回object2023-03-03