這段時(shí)間重新?lián)炱鹆藬?shù)據(jù)結(jié)構(gòu)和算法，發(fā)現(xiàn)里面的樹(shù)和圖是真的掉頭發(fā)。本文基于一個(gè)面試題，詳細(xì)分析如何實(shí)現(xiàn)數(shù)組和樹(shù)的相互轉(zhuǎn)換。

前言

樹(shù)或者圖是個(gè)比較抽象的概念，并不存在這樣的數(shù)據(jù)類(lèi)型。我們看一下樹(shù)的結(jié)構(gòu)，一層嵌套一層，同層次可能還會(huì)有多個(gè)節(jié)點(diǎn)，這種結(jié)構(gòu)的數(shù)據(jù)可以使用{}對(duì)象來(lái)表示。數(shù)組就比較簡(jiǎn)單了，因此數(shù)組和樹(shù)的轉(zhuǎn)換可以理解為數(shù)組和對(duì)象之間的轉(zhuǎn)換，只是需要轉(zhuǎn)換的數(shù)組和對(duì)象都是比較特殊的數(shù)據(jù)。為了更好的看清楚轉(zhuǎn)換過(guò)程，本文采用ts的語(yǔ)法，使用js的話沒(méi)有類(lèi)型約束，看起來(lái)就更容易暈了。

數(shù)組轉(zhuǎn)換為樹(shù)

我們先來(lái)一個(gè)簡(jiǎn)單點(diǎn)的，將數(shù)組轉(zhuǎn)換為樹(shù)。

結(jié)合樹(shù)，我們看一下數(shù)組的結(jié)構(gòu)：BC是A的子節(jié)點(diǎn)，DE是B的子節(jié)點(diǎn)，F(xiàn)是C的子節(jié)點(diǎn)。想要實(shí)現(xiàn)這個(gè)效果，我們先來(lái)捋一下實(shí)現(xiàn)思路：

• 遍歷數(shù)組
• 將數(shù)組項(xiàng)轉(zhuǎn)換為樹(shù)的葉子節(jié)點(diǎn)，并使用Map來(lái)維持id與節(jié)點(diǎn)直接的關(guān)系，便于快速查找
• 根據(jù)parentId查找到可能存在的父節(jié)點(diǎn)，并建立葉子節(jié)點(diǎn)和父節(jié)點(diǎn)之間的關(guān)系
• 找到根節(jié)點(diǎn)，最終返回的也就是根節(jié)點(diǎn)

文字描述可能不太具體，我們看一下實(shí)現(xiàn)代碼：

// 定義數(shù)組項(xiàng)的數(shù)據(jù)類(lèi)型，包含id、name、parentId基本屬性
interface ArrayItem {
  id: number,
  name: string,
  parentId: number
}
// 定義樹(shù)節(jié)點(diǎn)的數(shù)據(jù)類(lèi)型，包含id、name、可能存在的子節(jié)點(diǎn)
interface TreeNode {
  id: number,
  name: string,
  children?: TreeNode[], // 葉子節(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)
}
function array2Tree(arr: ArrayItem[]): TreeNode | null {
  // 用于id和TreeNode的映射，map<key, value>，可通過(guò)id快速查找到樹(shù)節(jié)點(diǎn)，時(shí)間復(fù)雜度為O(1)
  const treeNode: Map<number, TreeNode> = new Map();
  let root = null; // 樹(shù)根節(jié)點(diǎn)
  arr.forEach(item => {
    const {id, name, parentId} = item; // 解構(gòu)賦值
    // 定義樹(shù)節(jié)點(diǎn)tree node，并使用Map維持id與節(jié)點(diǎn)之間的關(guān)系
    const node: TreeNode = {id, name}
    treeNode.set(id, node);
?
    // 使用parentId找出parentNode
    const parentNode = treeNode.get(parentId);
    if (parentNode) {
      if (parentNode.children == null) {
        parentNode.children = [];
      }
      // 找到父節(jié)點(diǎn)后，將當(dāng)前數(shù)組項(xiàng)轉(zhuǎn)換的節(jié)點(diǎn)添加到子節(jié)點(diǎn)列表中
      parentNode.children.push(node)
    }
?
    // 在第一次循環(huán)中找到根節(jié)點(diǎn)，我們假定id=0的表示根節(jié)點(diǎn)
    if (parentId === 0) {
      root = node;
    }
  })
  return root;
}
const tree = array2Tree(arrs); // 需要定義arrs
console.log(tree);

代碼是使用ts完成的，清晰的展示了樹(shù)節(jié)點(diǎn)數(shù)據(jù)類(lèi)型的定義，在轉(zhuǎn)換過(guò)程中數(shù)據(jù)類(lèi)型的變化。直接運(yùn)行ts代碼是看不出來(lái)打印的結(jié)果的，我們可以新建一個(gè)vue-ts的項(xiàng)目，或者嫌麻煩的話可以直接使用官網(wǎng)提供的運(yùn)行環(huán)境：playground

實(shí)現(xiàn)效果：

其實(shí)就是一個(gè)對(duì)象，對(duì)象的層次就像是樹(shù)一樣展開(kāi)。

樹(shù)轉(zhuǎn)換為數(shù)組

同樣也是這個(gè)例子，只不過(guò)是需要將樹(shù)轉(zhuǎn)換為數(shù)組了。

數(shù)組和樹(shù)在數(shù)據(jù)結(jié)構(gòu)上最大的差異就是樹(shù)沒(méi)有parentId的屬性，如果一個(gè)節(jié)點(diǎn)有子節(jié)點(diǎn)，那么該節(jié)點(diǎn)的id就應(yīng)該是其子節(jié)點(diǎn)的parentId。老規(guī)矩，先來(lái)捋一下思路：

• 遍歷樹(shù)節(jié)點(diǎn)，使用廣度優(yōu)先。樹(shù)的遍歷可分為廣度優(yōu)先和深度優(yōu)先，廣度優(yōu)先表示橫向遍歷，深度優(yōu)先表示縱向遍歷
• 將遍歷出的樹(shù)節(jié)點(diǎn)添加到隊(duì)列中，實(shí)現(xiàn)先進(jìn)先出。隊(duì)列并不是js中的數(shù)據(jù)類(lèi)型，但是我們可以使用數(shù)組來(lái)實(shí)現(xiàn)隊(duì)列
• 將樹(shù)節(jié)點(diǎn)轉(zhuǎn)換為數(shù)組項(xiàng)
• 根據(jù)節(jié)點(diǎn)的父子關(guān)系，設(shè)置數(shù)組項(xiàng)的parentId，并將數(shù)組項(xiàng)添加到數(shù)組中
• 為了查找遍歷，可使用Map來(lái)維持父節(jié)點(diǎn)和子節(jié)點(diǎn)的關(guān)系

實(shí)現(xiàn)代碼:

// 定義數(shù)據(jù)結(jié)構(gòu)
...
function tree2Array(root: TreeNode): ArrayItem[] {
  // 定義子節(jié)點(diǎn)和父節(jié)點(diǎn)的映射關(guān)系，map<子節(jié)點(diǎn)，父節(jié)點(diǎn)>
  const childToParent: Map<TreeNode, TreeNode> = new Map();

  const arr: ArrayItem[] = []; // 返回的數(shù)組

  // 廣度優(yōu)先遍歷樹(shù)，使用隊(duì)列保存節(jié)點(diǎn)
  const queue: TreeNode[] = [];
  queue.unshift(root); // 入隊(duì)，從頭部入隊(duì)
  while(queue.length) {
    const curNode = queue.pop(); // 出隊(duì)，從尾部出隊(duì)，保證先進(jìn)先出
    if (curNode == null) break; // 循環(huán)結(jié)束，使用==包括了null和undefined的情況

    const {id, name, children = []} = curNode; // 結(jié)構(gòu)賦值，葉子節(jié)點(diǎn)沒(méi)有children屬性，所以默認(rèn)為空數(shù)組

    const parentNode = childToParent.get(curNode); // 獲取當(dāng)前節(jié)點(diǎn)的父節(jié)點(diǎn)
    const parentId = parentNode?.id || 0; // 獲取父節(jié)點(diǎn)id，根節(jié)點(diǎn)設(shè)置為0
    const item = {id, name, parentId}; // 定義數(shù)組項(xiàng)
    arr.push(item); // 插入到數(shù)組中

    // 繼續(xù)遍歷子節(jié)點(diǎn)，并且子節(jié)點(diǎn)入隊(duì)
    children.forEach(child => {
      // 如果有子節(jié)點(diǎn)，則把子節(jié)點(diǎn)和當(dāng)前節(jié)點(diǎn)通過(guò)Map保持關(guān)系
      childToParent.set(child, curNode);

      // 入隊(duì)
      queue.unshift(child);
    })
  }

  return arr;
}
const array = tree2Array(obj); // 這個(gè)obj對(duì)象就是數(shù)組轉(zhuǎn)換為樹(shù)打印出的結(jié)果
console.log(array)

運(yùn)行結(jié)果:

可以發(fā)現(xiàn)，結(jié)果符合預(yù)期。

總結(jié)

總結(jié)一下，數(shù)組和樹(shù)之間相互轉(zhuǎn)換一開(kāi)始還挺蒙的，但是看完代碼發(fā)現(xiàn)，其實(shí)也并不復(fù)雜。

• 數(shù)組轉(zhuǎn)換為樹(shù)：從數(shù)組的第一項(xiàng)開(kāi)始，根據(jù)parentId，找到每一項(xiàng)的歸屬；若找不到，則表示當(dāng)前數(shù)組項(xiàng)為根節(jié)點(diǎn)
• 樹(shù)轉(zhuǎn)換為數(shù)組：樹(shù)的每一個(gè)節(jié)點(diǎn)都可能會(huì)有很多子節(jié)點(diǎn)，按照廣度優(yōu)先，從根節(jié)點(diǎn)開(kāi)始遍歷，將每一個(gè)節(jié)點(diǎn)以及其子節(jié)點(diǎn)都添加到隊(duì)列中，按照先進(jìn)先出的原則，逐一將節(jié)點(diǎn)都轉(zhuǎn)換為數(shù)組項(xiàng)并添加到數(shù)組中
• 在實(shí)現(xiàn)的過(guò)程中，可結(jié)合圖例，一步一步分析，最終實(shí)現(xiàn)結(jié)果

以上就是TypeScript實(shí)現(xiàn)數(shù)組和樹(shù)的相互轉(zhuǎn)換的詳細(xì)內(nèi)容，更多關(guān)于TypeScript數(shù)組轉(zhuǎn)樹(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論