淺談JavaScript構造樹形結構的一種高效算法
引言
我們經常會碰到樹形數據結構,比如組織層級、省市縣或者動植物分類等等數據。下面是一個樹形結構的例子:
在實際應用中,比較常見的做法是將這些信息存儲為下面的結構,特別是當存在1對多的父/子節點關系時:
const data = [ { id: 56, parentId: 62 }, { id: 81, parentId: 80 }, { id: 74, parentId: null }, { id: 76, parentId: 80 }, { id: 63, parentId: 62 }, { id: 80, parentId: 86 }, { id: 87, parentId: 86 }, { id: 62, parentId: 74 }, { id: 86, parentId: 74 }, ];
那麼,如何將這種對象數組格式轉換為層級樹的格式呢?其實,利用 JavaScript 對象引用的特性,實現起來會非常簡單。它可以不用遞歸,在O(n)時間內完成。
術語
為瞭表述方便,我們先來定義幾個術語。我們把數組中的每個元素(也就樹形圖裡的每個圓圈)稱為“節點”。節點可以是多個節點的“父節點”,也可以是某個節點的“子節點”。上圖中,節點 86是節點 80和節點 87的“父節點”,節點 86是節點 74的子節點。樹的最頂部節點稱為“根節點”。
思路
為瞭構造樹形結構,我們需要:
- 遍歷data數組
- 找到當前元素的父元素
- 在父元素對象上添加一個對該子元素的引用
- 元素如果沒有父元素,那我們就認為它是樹的根節點
我們可以看到到,引用被保存在對象樹下,這就是為什麼我們可以在O(n)時間內完成這個任務!
建立 ID-數組索引映射關系
雖然不是必需的,但是這個映射關系可以幫我們快速找到元素的位置,方便找到到父元素的引用。
const idMapping = data.reduce((acc, el, i) => { acc[el.id] = i; return acc; }, {});
映射結果如下,後面你會看到它的用處有多大:
{
56: 0,
62: 7,
63: 4,
74: 2,
76: 3,
80: 5,
81: 1,
86: 8,
87: 6,
};
構造樹形結構
現在我們開始構造這個樹形結構。遍歷這個對象數組,找到每個元素的父元素對象,然後添加對這個元素的引用。現在你應該看到瞭,這個idMapping用來定位元素的位置多麼方便(常數時間)。
let root; data.forEach(el => { // 判斷根節點 if (el.parentId === null) { root = el; return; } // 用映射表找到父元素 const parentEl = data[idMapping[el.parentId]]; // 把當前元素添加到父元素的`children`數組中 parentEl.children = [...(parentEl.children || []), el]; });
完事!用console.log打印root看下:
console.log(root);
{
id: 74,
parentId: null,
children: [
{
id: 62,
parentId: 74,
children: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],
},
{
id: 86,
parentId: 74,
children: [
{
id: 80,
parentId: 86,
children: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],
},
{ id: 87, parentId: 86 },
],
},
],
};
原理
為什麼可以這麼做呢?這是因為,data數組裡的每個元素都是內存裡的一個對象引用,forEach循環裡的el變量其實是指向內存裡的一個對象,parentEl也引用瞭一個對象。
如果內存中的一個對象引用瞭一個 children 數組,這些子元素同樣可以引用自己的子元素數組,這些關聯關系都是通過引用完成的。
總結
對象引用是 JavaScript 中最基本的概念之一,需要更多的學習和理解。真正理解這個概念後,既可以避免棘手的 bug,又可以為看似復雜的問題提供相對簡單的解決方案。
以上就是淺談JavaScript構造樹形結構的一種高效算法的詳細內容,更多關於JavaScript構造樹形結構的算法的資料請關註WalkonNet其它相關文章!
推薦閱讀:
- JS使用reduce()方法處理樹形結構數據
- js將列表組裝成樹結構的兩種實現方式分享
- 詳解JS中你不知道的各種循環測速
- 分享幾個JavaScript運算符的使用技巧
- JavaScript數組對象高階函數reduce的妙用詳解