javascript將扁平的數(shù)據(jù)轉(zhuǎn)為樹形結(jié)構(gòu)的高效率算法
當(dāng)我們需要將一個一維數(shù)組轉(zhuǎn)換成一個多層結(jié)構(gòu)的時候,最簡單但是最慢的就是多個for循環(huán)嵌套,但是這樣做有一些缺點(diǎ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é)點(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: ’報單審核’, menu_url: ’order.orderreview’, parent_id: ’2’ }, { id: ’2-2’, menu_name: ’退款管理’, menu_url: ’order.refundmanagement’, parent_id: ’2’ }]
實現(xiàn)算法buildTree
算法思想:
先將數(shù)組中的每一個節(jié)點(diǎn)放到temp對象中(創(chuàng)建set)即數(shù)組中有{id: ’2-3’, parent_id: ’2’,...}這樣一個節(jié)點(diǎn),需要將他放到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é)點(diǎn)與父節(jié)點(diǎn)建立連接。是因為我們保證了父節(jié)點(diǎn)一定在子節(jié)點(diǎn)前,那么當(dāng)子節(jié)點(diǎn)出現(xiàn)的時候就直接可以用temp[temp[i].parent_id]來查找到父節(jié)點(diǎn)這個時候先父節(jié)點(diǎn)的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)容請搜索好吧啦網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持好吧啦網(wǎng)!
相關(guān)文章:
1. python excel和yaml文件的讀取封裝2. python實現(xiàn)讀取類別頻數(shù)數(shù)據(jù)畫水平條形圖案例3. moment轉(zhuǎn)化時間戳出現(xiàn)Invalid Date的問題及解決4. python操作數(shù)據(jù)庫獲取結(jié)果之fetchone和fetchall的區(qū)別說明5. python爬蟲實戰(zhàn)之制作屬于自己的一個IP代理模塊6. python中PyQuery庫用法分享7. python 讀取二進(jìn)制 顯示圖片案例8. .net6 在中標(biāo)麒麟下的安裝和部署過程9. Python中內(nèi)建模塊collections如何使用10. 開發(fā)效率翻倍的Web API使用技巧
