av一区二区在线观看_亚洲男人的天堂网站_日韩亚洲视频_在线成人免费_欧美日韩精品免费观看视频_久草视

您的位置:首頁技術文章
文章詳情頁

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

瀏覽:25日期:2023-06-04 13:38:48
引言

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

淺談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構造樹形結構的算法的資料請關注好吧啦網其它相關文章!

標簽: JavaScript
相關文章:
主站蜘蛛池模板: 成人性生交大片免费看中文带字幕 | 亚洲精品电影在线观看 | 中文字幕亚洲欧美 | 欧美精品久久久久久 | 精品视频一区二区三区在线观看 | 在线观看国产三级 | 久久综合激情 | 国产一区二区在线免费播放 | 亚洲第一天堂 | 中文在线a在线 | 免费v片| 国产一区二区三区在线看 | 精品日韩一区二区 | 久久专区 | 亚洲男人的天堂网站 | 韩国精品在线 | 免费在线播放黄色 | 免费特黄视频 | 午夜精品在线观看 | 欧洲妇女成人淫片aaa视频 | 亚洲高清视频在线观看 | 国产美女特级嫩嫩嫩bbb片 | 欧美激情综合色综合啪啪五月 | 国产激情综合五月久久 | 一级黄色片免费在线观看 | 欧美一区二区三区 | 亚洲精品www | 午夜精品久久久久久久 | 免费高潮视频95在线观看网站 | 亚洲品质自拍视频网站 | 国产欧美精品在线观看 | 亚洲欧美一区二区三区1000 | 国产美女特级嫩嫩嫩bbb片 | 日韩精品一区二区三区中文在线 | 欧美aaaa视频 | 久久久久久成人 | 国产精彩视频一区 | 欧美在线一区二区三区 | 黄色永久免费 | 欧美一区二区三区视频在线播放 | 色播久久久 |