多數情況下，從服務端拿到用於樹形顯示的數據，本身是平面的，也就是列表。這是因為關係型數據庫是以“行”為單位保存數據，所以它保存了每一個節點的數據，而這個數據中包含了它與父節點之間的聯繫（比如 parentId）。

前端要以樹形顯示這樣的列表數據，需要把列表數據轉換成樹形結構數據。這個的樹形結構是指：每個節點數據中都含有其子節點集（通常是 children 屬性）。所以樹形結節的數據結構主要需要包含如下信息（TypeScript 數據結構聲明）：

interface TreeNodeBase<TKey extends string | number = number> {
    id: TKey;
    parentId: TKey
    children?: TreeNodeBase<TKey>[]
}

這裏使用了 TypeScript 的泛型語法來描述樹節點結構。從自然語義不難明白：

• 樹節點的 id（包括 parentId）是 string 或者 number 類型，較為少見的情況下也可能是混合類型。
• 樹節點包含一個 parentId，由於這個 parentId 不是可選的（沒用 ? 號聲明），所以根節點通常會用一個特殊值，或者不應該存在的 ID 值，比如 0（如果是數據庫自增字段，一般會從 1 開始）
• 樹節點包含一個可選的子節點集 children，其每個元素了當前元素是相同的類型
• 定義 TKey 這個類型參數的作用就是為了約束子節點類型必須和父節點一致，避免父節點的 id 是 string 類型，子節點的 id 卻搞成了 string 這種情況（混合類型 id 的情況不含在內）

科普完樹節點的數據結構，再來説轉換過程。一般來説可能會在三個階段進行轉換：

• 後端送出來之前先處理好
• 前端拿到之後自己轉換，再用轉換後數組去渲染頁面
• 前端使用的 UI 組件自帶轉換功能，不需要開發者去操心（比如 zTree）

這裏就以 JS/TS 為例來説説如何進行轉換。語言不重要，重要的是該如何來思考，以及使用什麼方法進行轉換。這裏同時使用 JS 和 TS 的原因在於：帶類型的 TS 可以清晰地描述數據結構，而 JS 代碼可能多數人看起來更沒有壓力。

一、準備示例數據（隨機產生）

以列表表示的樹形數據，其每一條（行）一定需要清楚的描述這個節點的三個要素：

1. 自身標識（ID），通常用 id、key、name 等屬性名，它能唯一標識一個節點
2. 與父節點的關係，通過使用 parentId、upstreamId 等名稱，清楚的指明其父節點
3. 節點自己攜帶的數據，比如顯示的文本，title、label 等，和一些其他數據。

為了快速準備示例數據，我們使用一個最簡單，屬性意義也非常明確的數據結構。注意，這個結構是與數據表相匹配的平面結構，不含 children 子集。

// TypeScript
interface TreeNode {
    id: number;
    parentId: number;
    label: string;
}

然後寫一段代碼來隨機生成數據。在這之前，我們約定，有效節點的 id 從 1 開始。如果某個節點的 parentId === 0，則表示該節點沒有父節點。思路：

• 循環產生一組節點，每個節點的 id 就是 序號 + 1（序號是從 0 開始的）

  // JavaScript
  const nodes = [];
  count nodesCount = 20;
  for (let i = 0; i < nodesCount; i++) {
      nodes.push({
          id: i + 1,
      })
  }

• 接下來，parentId 是之前已經產生的節點，其 ID 範圍在區間 [0, i]（封閉區間，如果不懂，請複習一下高中數學）。我們隨機從這個範圍內一個作為其父節點。這裏我們需要產生一個隨機整數，所以先寫一個 randomInt(max)

  // JavaScript
  function randomInt(max) {
      return Math.floor(Math.random());
  }

  注意 Math.random() 的取值範圍是 [0, 1)（左閉右開區間）內的浮點數，所以 randomInt() 的結果集在 [0, max) 範圍內。為了保證需要的 [0, i] 內的整數，即 [0, i + 1) 間的整數，需要調用時給參數為 i + 1：randomInt(i + 1) 。

  繼續完善上面 node.push( ... ) 中的 parentId 部分：

  {
      id: i + 1,
      parentId: randomInt(i + 1)
  }

• 下一步，是產生隨機的 label。也不定太複雜的規矩，就產生一個由大小寫字母及數字組成的，長度在 [5, 15) 範圍的隨機字符串。由於字符串本身是可以迭代（遍歷）的，所以可以用擴展 (Spread) 運算符來轉換成數組，從而得到字符集，代碼如下：

  // JavaScript
  const CHARS = ((chars, nums) => {
      return [...`${chars}${chars.toLowerCase()}${nums}`];
  })("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789");

  其實直接給一個包含所有字符的字符串就可以，但是不想把 a~z 再寫一遍，所以用了一個 IIFE 來複用 A~Z。

  另外有一點需要注意：字符串本身可以使用 [] 索引運算符來取字符，所以不預先轉換成字符數組也是可以的。

  接下來是隨機產生字符串。根據長度隨機選擇 n 個字符，再連接起來即可：

  // JavaScript
  function randomString(length) {
      return Array.from(
          Array(length),
          () => CHARS[randomInt(CHARS.length)]
      ).join("");
  }

  randomString() 可以產生一個指定長度的隨機字符串。這裏 Array(length) 會產生一個長度為 length 但不含任何元素的數組，可以用 Array.from() 把它變成含有元素（默認是 undefined）的數組。在轉換的過程中，Array.from() 的第二個參數是一個映射函數，跟 Array.prototype.map() 的參數一樣。

  現在，我們可以繼續完善 node.push(...) 中的 label 部分：

  {
      id: i + 1,
      parentId: randomInt(i + 1),
      label: randomString(5 + randomInt(10))    // 長度在 [5, 15) 區間的隨機字符串
  }

到目前為上，準備示例數據的關鍵代碼都有了，來個完整的

// TypeScript

interface TreeNode {
    id: number;
    parentId: number;
    label: string;
}

const CHARS = ((chars, nums) => {
    return [...`${chars}${chars.toLowerCase()}${nums}`];
})("ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789");

function randomInt(max: number): number {
    return Math.floor(Math.random() * max);
}

function randomString(length: number = 10): string {
    return Array.from(
        Array(length),
        () => CHARS[randomInt(CHARS.length)]
    ).join("");
}

function randomTreeNodes(count: number = 20): TreeNode[] {
    return [...Array(count).keys()]
        .map(i => ({
            id: i + 1,
            parentId: randomInt(i + 1),     // 從已經產生的節點中去隨機找一個
            label: randomString(5 + randomInt(10))  // 隨機產生長度為 [5, 15) 的字符串
        }));
}

完整代碼是 TypeScript 寫的。如果需要 JavaScript，可以根據上面每一步的關鍵代碼拼出來。或者拿 TypeScript 代碼到 TypeScript Playground 中去轉換一下。

最後可以直接調用 randomTreeNodes() 來生成我們需要的樹形結構：

// JavaScript | TypeScript
const treeNodes = randomTreeNodes();

得到的 treeNodes 會用於下面生成樹演示代碼的數據源。下面是其中一次運行的結果：

[
  { id: 1, parentId: 0, label: '8WUg35y' },
  { id: 2, parentId: 1, label: 'Pms1S5Mx' },
  { id: 3, parentId: 1, label: 'RUTKSF' },
  { id: 4, parentId: 1, label: 'IYkxXlhmU12x' },
  { id: 5, parentId: 4, label: 'p2Luabg9mK2' },
  { id: 6, parentId: 0, label: 'P6mtcgfCD' },
  { id: 7, parentId: 1, label: 'yluJgpnqKthR' },
  { id: 8, parentId: 6, label: 'm6o5UsytQ0' },
  { id: 9, parentId: 2, label: 'glcR5yGx' },
  { id: 10, parentId: 0, label: 'lhDGTNeeSxLNJ' },
  { id: 11, parentId: 1, label: 'r7ClxBCQS6' },
  { id: 12, parentId: 7, label: '5W6vy0EuvOjN' },
  { id: 13, parentId: 5, label: 'LbpWq' },
  { id: 14, parentId: 6, label: 'ysYwG8EFLAu1a' },
  { id: 15, parentId: 8, label: 'R2PmAh1' },
  { id: 16, parentId: 10, label: 'RKuQs4ki65wo' },
  { id: 17, parentId: 10, label: 'YN88ixWO1PY7f4' },
  { id: 18, parentId: 13, label: '03X6e4UT' },
  { id: 19, parentId: 7, label: 'LTJTeF' },
  { id: 20, parentId: 19, label: '3rqUqE3MLShh' }
]

如果用圖形來表示就是：

flowchart LR
%%{ init: { "theme": "forest" } }%%

S(("Virtual\nRoot")) --> N1
S --> N6
S --> N10

N1("1 | 8WUg35y") --> N2("2 | Pms1S5Mx")
N1 --> N3("3 | RUTKSF")
N1 --> N4("4 | IYkxXlhmU12x")
N4 --> N5("5 | p2Luabg9mK2")
N6("6 | P6mtcgfCD")
N1 --> N7("7 | yluJgpnqKthR")
N6 --> N8("8 | m6o5UsytQ0")
N2 --> N9("9 | glcR5yGx")
N10("10 | lhDGTNeeSxLNJ")
N1 --> N11("11 | r7ClxBCQS6")
N7 --> N12("12 | 5W6vy0EuvOjN")
N5 --> N13("13 | LbpWq")
N6 --> N14("14 | ysYwG8EFLAu1a")
N8 --> N15("15 | R2PmAh1")
N10 --> N16("16 | RKuQs4ki65wo")
N10 --> N17("17 | YN88ixWO1PY7f4")
N13 --> N18("18 | 03X6e4UT")
N7 --> N19("19 | LTJTeF")
N19 --> N20("20 | 3rqUqE3MLShh")

Mermaid 是個好東西，思否支持哦！

二、從演示數據生成樹

在思路沒有完全形成之前，拿起鍵盤就開始敲代碼 —— 這種行為一般算作“實驗”。不過即使是實驗，也應該先捋捋思路。

目前已知，每個節點上已經包括了關鍵數據：用於識別節點的 id，用於識別其父級關係的 parentId。那麼，只需要在處理某個節點時，根據其 parentId 找到父節點，並在父節點的 children[] 數組中加入當前節點即可生成樹形結構的數據。這裏還要考慮幾個相關問題：

1. 由於一個節點只有一個 parentId，所以它最終只會添加到某一個節點的 children[] 中，不可能出現在多個節點的 children[] 中；
2. 對於沒有 parentId 或者 parentId 為 0 的節點，我們認為是根節點。但它有可能不是唯一根節點，所以我們需要一個額外的 roots[] 數組來保存所有根節點。
3. 思考：該怎樣根據 parentId 來找到對應的節點數據？

前兩個問題好理解，第 3 個問題需要思考算法。由於節點列表中存在父節點，所以可以直接拿 parentId 在節點列表中去查找

// JavaScript
const parentNode = treeNodes.find(node => node.id === parentId);

在遍歷處理節點的過程中，根據上面生成數據的邏輯，可以斷定當前節點的父節點一定在它之前。如果知道父節點和子節點之間關係較近，可以優化為逆序查找。這個過程可以定義成一個函數 findParent()：

// JavaScript
/**
 * @param id 要查找的父節點 id
 * @param index 當前節點在 treeNodes 中的序號
 */
const findParent = (id, index) => {
    for (let i = index - 1; i >= 0; i--) {
        if (treeNodes[i].id === id) {
            return treeNodes[i];
        }
    }    
};

實際上，多數情況下並不清楚要查找到父節點到底是離起始位置近還是離子節點近，所以完全沒必要去寫個逆序查找，用 Array.prototype.find() 就好了。

找到父節點之後，在把當前節點 node 加入到 parentNode 子節點集之前，特別要注意其子節點集是否存在。可以使用 Logical nullish assignment (??=) 運算符來簡化代碼，一句搞定：

(parentNode.children ??= []).push(node);

這裏還有一個性能相關的問題。在數據量較大的情況下，不管順序還是逆序查找都可能掃過非常多的節點，使用 Map 可以大大提高查找效率。在節點有序（即父節點一定在前面）的情況下，Map 可以在遍歷的同時生成。相對完整的代碼示例：

// JavaScript

function makeTree(treeNodes) {
    const nodesMap = new Map();
    const roots = [];
    treeNodes.forEach((node, i) => {
        nodesMap.set(node.id, node);

        if (!node.parentId) {
            roots.push(node);
            return;
        }

        const parent = nodesMap.get(node.parentId);
        (parent.children ??= []).push(node);
    });

    return roots;
}

上面這段 JavaScript 代碼，如果改成 TypeScript 代碼，在補充了類型聲明的情況下，仍然會有一個問題：接近結尾處的 parent.children 會標紅 parent 並報告“Object is possibly 'undefined'.”。

這個問題説明根據 parentId 在 Map 中查找父節點時，存在找不到的可能性。

在這個示例中，由於我們生成 treeNodes 的代碼可以保證一定找得到，可以忽略編譯器的擔憂，直接改為 parent!.children 隱藏掉這個風險提示即可。但是，真實從後台過來的數據並不能保證 nodesMap.get(node.parentId) 不會返回 undefined。至少存在兩種造成這個問題的情況：

1. 節點順序並不是按先父後子的順序（多數是發生在移動過節點之後）。這種情況下，由於父節點在子節點之後，還沒加入 Map 就要從裏面查找，當然是找不到的。要解決這個問題，只需要提交遍歷所有節點生成完整的 Map 就好。

2. 由於後端失誤或業務需要，未能把所有節點都送回來。那前端除了報錯之外，還有兩種容錯處理方式：

   1. 丟棄沒有找到父節點的節點。這種容錯方式處理起來不難，就不多説了。
   2. 把沒有父節點的節點當作根節點 —— 既然數據都來了，多數情況下會採用這種容錯方式

接下來就是加入容錯處理的 makeTree。

三、從列表生成樹的完整 TypeScript 代碼

interface TreeNode {
    id: number;
    parentId: number;
    label: string;
    children?: TreeNode[]
}

function makeTree(treeNodes: TreeNode[]): TreeNode[] {
    // 提前生成節點查找表。
    // 如果明確節點是順序可以保證先父後子，可以省去這次遍歷，在後面邊遍歷過程中填充查找表
    const nodesMap = new Map<number, TreeNode>(
        treeNodes.map(node => [node.id, node])
    );

    // 引入虛擬根節點來統一實現 parent 始終有效，避免空判斷
    const virtualRoot = { } as Partial<TreeNode>;
    treeNodes.forEach((node, i) => {
        const parent = nodesMap.get(node.parentId) ?? virtualRoot;
        (parent.children ??= []).push(node);
    });

    return virtualRoot.children ?? [];
}

是的，這段代碼並不長。但是，

• 層層遞進的分析和處理過程有沒有 Get 到？
• TypeScript 的類型檢查有沒有打動到你？

來我的課堂：TypeScript從入門到實踐 【2021 版】 - 思否編程，你可以

• 深入理解 TypeScript 語言特性，編寫高質量代碼
• 掌握基於 TypeScript 的 Vue 前端、 Koa 後端技術運用
• 掌握前後端分離的開發模式、設計模式和發佈方法
• 將類型系統融入編程思維，提升理解能力和設計能力