引言

我們經(jīng)常會(huì)碰到樹形數(shù)據(jù)結(jié)構(gòu)，比如組織層級(jí)、省市縣或者動(dòng)植物分類等等數(shù)據(jù)。下面是一個(gè)樹形結(jié)構(gòu)的例子：

在實(shí)際應(yīng)用中，比較常見(jiàn)的做法是將這些信息存儲(chǔ)為下面的結(jié)構(gòu)，特別是當(dāng)存在1對(duì)多的父/子節(jié)點(diǎn)關(guān)系時(shí)：

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

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

術(shù)語(yǔ)

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

思路

為了構(gòu)造樹形結(jié)構(gòu)，我們需要：

• 遍歷data數(shù)組
• 找到當(dāng)前元素的父元素
• 在父元素對(duì)象上添加一個(gè)對(duì)該子元素的引用
• 元素如果沒(méi)有父元素，那我們就認(rèn)為它是樹的根節(jié)點(diǎn)

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

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

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

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  return acc;
}, {});

映射結(jié)果如下，后面你會(huì)看到它的用處有多大：

{

  56: 0,

  62: 7,

  63: 4,

  74: 2,

  76: 3,

  80: 5,

  81: 1,

  86: 8,

  87: 6,

};

構(gòu)造樹形結(jié)構(gòu)

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

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

      ],

    },

  ],

};

原理

為什么可以這么做呢？這是因?yàn)?，data數(shù)組里的每個(gè)元素都是內(nèi)存里的一個(gè)對(duì)象引用，forEach循環(huán)里的el變量其實(shí)是指向內(nèi)存里的一個(gè)對(duì)象，parentEl也引用了一個(gè)對(duì)象。

如果內(nèi)存中的一個(gè)對(duì)象引用了一個(gè) children 數(shù)組，這些子元素同樣可以引用自己的子元素?cái)?shù)組，這些關(guān)聯(lián)關(guān)系都是通過(guò)引用完成的。

總結(jié)

對(duì)象引用是 JavaScript 中最基本的概念之一，需要更多的學(xué)習(xí)和理解。真正理解這個(gè)概念后，既可以避免棘手的 bug，又可以為看似復(fù)雜的問(wèn)題提供相對(duì)簡(jiǎn)單的解決方案。

以上就是淺談JavaScript構(gòu)造樹形結(jié)構(gòu)的一種高效算法的詳細(xì)內(nèi)容，更多關(guān)于JavaScript構(gòu)造樹形結(jié)構(gòu)的算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論