淺談JavaScript構造樹形結構的一種高效算法

更新時間：2021年05月08日 10:08:18 作者：李中凱

這篇文章主要介紹了JavaScript構造樹形結構的一種高效算法，對算法感興趣的同學，可以參考下

引言

我們經常會碰到樹形數(shù)據(jù)結構，比如組織層級、省市縣或者動植物分類等等數(shù)據(jù)。下面是一個樹形結構的例子：

在實際應用中，比較常見的做法是將這些信息存儲為下面的結構，特別是當存在1對多的父/子節(jié)點關系時：

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 },
];

那么，如何將這種對象數(shù)組格式轉換為層級樹的格式呢？其實，利用 JavaScript 對象引用的特性，實現(xiàn)起來會非常簡單。它可以不用遞歸，在O(n)時間內完成。

術語

為了表述方便，我們先來定義幾個術語。我們把數(shù)組中的每個元素（也就樹形圖里的每個圓圈）稱為“節(jié)點”。節(jié)點可以是多個節(jié)點的“父節(jié)點”，也可以是某個節(jié)點的“子節(jié)點”。上圖中，節(jié)點 86是節(jié)點 80和節(jié)點 87的“父節(jié)點”，節(jié)點 86是節(jié)點 74的子節(jié)點。樹的最頂部節(jié)點稱為“根節(jié)點”。

思路

為了構造樹形結構，我們需要：

遍歷data數(shù)組
找到當前元素的父元素
在父元素對象上添加一個對該子元素的引用
元素如果沒有父元素，那我們就認為它是樹的根節(jié)點

我們可以看到到，引用被保存在對象樹下，這就是為什么我們可以在O(n)時間內完成這個任務！

建立 ID-數(shù)組索引映射關系

雖然不是必需的，但是這個映射關系可以幫我們快速找到元素的位置，方便找到到父元素的引用。

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,

};

構造樹形結構

現(xiàn)在我們開始構造這個樹形結構。遍歷這個對象數(shù)組，找到每個元素的父元素對象，然后添加對這個元素的引用?，F(xiàn)在你應該看到了，這個idMapping用來定位元素的位置多么方便（常數(shù)時間）。

let root;
data.forEach(el => {
  // 判斷根節(jié)點
  if (el.parentId === null) {
    root = el;
    return;
  }
  // 用映射表找到父元素
  const parentEl = data[idMapping[el.parentId]];
  // 把當前元素添加到父元素的`children`數(shù)組中
  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 },

],

},

],

};