JavaScript實現(xiàn)樹結構轉換的五種方法總結
在 JavaScript 編程中，將數(shù)組轉換為樹結構是一個常見的需求。本篇博客將介紹五種常用的方法來實現(xiàn)數(shù)組轉樹結構，并討論每種方法的時間復雜度、空間復雜度和最優(yōu)解。
假設有一個由對象組成的數(shù)組，每個對象包含 id 和 parentId 兩個屬性。其中 id 表示節(jié)點的唯一標識，parentId 表示該節(jié)點的父節(jié)點的 id。
const nodes = [
{ id: 1, parentId: null },
{ id: 2, parentId: 1 },
{ id: 3, parentId: 1 },
{ id: 4, parentId: 2 },
{ id: 5, parentId: 3 },
{ id: 6, parentId: 3 },
{ id: 7, parentId: 4 },
{ id: 8, parentId: 4 },
];以上面的數(shù)組為例，我們將介紹以下五種方法來將其轉換為樹結構。
方法一：使用遞歸
function arrayToTreeRec(nodes, parentId = null) {
return nodes
.filter((node) => node.parentId === parentId)
.map((node) => ({ ...node, children: arrayToTreeRec(nodes, node.id) }));
}
const tree = arrayToTreeRec(nodes, null);時間復雜度：O(n^2)，其中 n 是節(jié)點的數(shù)量。 空間復雜度：O(n^2)。 優(yōu)缺點：不適合大規(guī)模數(shù)據(jù)。
方法二：使用循環(huán)
function arrayToTreeLoop(nodes) {
const map = {};
const tree = [];
for (const node of nodes) {
map[node.id] = { ...node, children: [] };
}
for (const node of Object.values(map)) {
if (node.parentId === null) {
tree.push(node);
} else {
map[node.parentId].children.push(node);
}
}
return tree;
}
const tree = arrayToTreeLoop(nodes);
時間復雜度：O(n)，其中 n 是節(jié)點的數(shù)量。 空間復雜度：O(n)。 優(yōu)缺點：適合大規(guī)模數(shù)據(jù)。
方法三：使用 reduce
function arrayToTreeReduce(nodes) {
const map = {};
const tree = nodes.reduce((acc, node) => {
map[node.id] = { ...node, children: [] };
if (node.parentId === null) {
acc.push(map[node.id]);
} else {
map[node.parentId].children.push(map[node.id]);
}
return acc;
}, []);
return tree;
}
const tree = arrayToTreeReduce(nodes);
時間復雜度：O(n)，其中 n 是節(jié)點的數(shù)量。 空間復雜度：O(n)。 優(yōu)缺點：代碼簡潔，適合中小規(guī)模數(shù)據(jù)。
方法四：使用哈希表
function arrayToTreeMap(nodes) {
const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
const tree = [];
for (const node of map.values()) {
if (node.parentId === null) {
tree.push(node);
} else {
map.get(node.parentId).children.push(node);
}
}
return tree;
}
const tree = arrayToTreeMap(nodes);時間復雜度：O(n)，其中 n 是節(jié)點的數(shù)量。 空間復雜度：O(n)。 優(yōu)缺點：適合大規(guī)模數(shù)據(jù)，而且由于使用了 Map，相比于方法二和方法三，能夠更方便地進行節(jié)點的查找和刪除。
方法五：使用深度優(yōu)先搜索
function arrayToTreeDFS(nodes) {
const map = new Map(nodes.map((node) => [node.id, { ...node, children: [] }]));
const tree = [];
for (const node of map.values()) {
if (node.parentId === null) {
dfs(node, tree);
}
}
function dfs(node, parent) {
if (parent) {
parent.children.push(node);
}
for (const child of node.children) {
dfs(map.get(child.id), node);
}
}
return tree;
}
const tree = arrayToTreeDFS(nodes);
時間復雜度：O(n)，其中 n 是節(jié)點的數(shù)量。 空間復雜度：O(n)。 優(yōu)缺點：相比于方法二、方法三和方法四，可以更方便地進行深度優(yōu)先搜索。
總結
以上是五種常用的將數(shù)組轉換為樹結構的方法，每種方法都有其適用的場景和優(yōu)劣。如果是大規(guī)模數(shù)據(jù)，使用方法二或方法四比較合適；如果是中小規(guī)模數(shù)據(jù)，使用方法三比較簡潔；如果需要深度優(yōu)先搜索，可以使用方法五?？偟膩碚f，我們需要根據(jù)具體場景選擇最適合的方法來進行數(shù)組到樹結構的轉換。
到此這篇關于JavaScript實現(xiàn)樹結構轉換的五種方法總結的文章就介紹到這了,更多相關JavaScript樹結構轉換內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
在網站開發(fā)中,經常會遇到需要展示多張圖片并自動切換的需求,這就需要使用JavaScript來實現(xiàn)圖片的自動輪播功能,本文將通過一個簡單的例子,演示如何用JavaScript實現(xiàn)圖片的自動輪播,需要的朋友可以參考下2013-03-03
淺析AMD CMD CommonJS規(guī)范--javascript模塊化加載學習心得總結
下面小編就為大家分享一篇淺析AMD CMD CommonJS規(guī)范--javascript模塊化加載學習心得總結。小編覺得寫的非常不錯，需要的朋友可以過來參考一下2016-03-03
這篇文章主要為大家詳細介紹了基于JavaScript canvas繪制貝塞爾曲線的方法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-12-12
這篇文章主要為大家介紹了ChatGPT?之?Fetch請求的內容解析，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-03-03
這篇文章主要介紹了微信小程序中如何使用flyio封裝網絡請求，F(xiàn)ly.js 通過在不同 JavaScript 運行時通過在底層切換不同的 Http Engine來實現(xiàn)多環(huán)境支持，但同時對用戶層提供統(tǒng)一、標準的Promise API,需要的朋友可以參考下2019-07-07
js函數(shù)使用技巧之 setTimeout(function(){},0)
setTimeout的作用是將函數(shù)推遲第二參數(shù)設定的毫秒數(shù)后再執(zhí)行，如果是0，就意味著瀏覽器要馬上執(zhí)行該函數(shù)，但是瀏覽器解析到setTimeout，雖然會"立刻"執(zhí)行2009-02-02
解決IE6下JS動態(tài)設置圖片IMG的SRC時圖片無法加載錯誤的方法2010-01-01
一文詳解TypeScript中的內置數(shù)據(jù)類型
作為一門類型安全的編程語言，TypeScript?提供了多種內置數(shù)據(jù)類型，幫助我們更好地定義和操作數(shù)據(jù)，下面小編就來和大家詳細聊聊這些數(shù)據(jù)類型的相關知識吧2023-06-06
編寫JS的過程中,我們經常用到對象,也會用到對象中的屬性,下面這篇文章主要給大家介紹了關于JS判斷對象屬性是否存在的五種方案,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-01-01
這篇文章主要介紹了純js代碼實現(xiàn)簡單計算器，功能超簡單，實現(xiàn)加減乘除簡單運算，感興趣的小伙伴們可以參考一下2015-12-12