中級演算法題：實現陣列和樹的相互轉換（ts版）
theme: fancy
持續創作，加速成長！這是我參與「掘金日新計劃 · 6 月更文挑戰」的第24天，點選檢視活動詳情
這段時間重新撿起了資料結構和演算法，發現裡面的樹和圖是真的掉頭髮。本文基於一個面試題，詳細分析如何實現陣列和樹的相互轉換。
前言
樹或者圖是個比較抽象的概念，並不存在這樣的資料型別。我們看一下樹的結構，一層巢狀一層，同層次可能還會有多個節點，這種結構的資料可以使用{}物件來表示。陣列就比較簡單了，因此陣列和樹的轉換可以理解為陣列和物件之間的轉換，只是需要轉換的陣列和物件都是比較特殊的資料。為了更好的看清楚轉換過程，本文采用ts的語法，使用js的話沒有型別約束，看起來就更容易暈了。
陣列轉換為樹
我們先來一個簡單點的，將陣列轉換為樹。
結合樹，我們看一下陣列的結構：BC是A的子節點，DE是B的子節點，F是C的子節點。想要實現這個效果，我們先來捋一下實現思路：
- 遍歷陣列
- 將陣列項轉換為樹的葉子節點，並使用Map來維持id與節點直接的關係，便於快速查詢
- 根據parentId查詢到可能存在的父節點，並建立葉子節點和父節點之間的關係
- 找到根節點，最終返回的也就是根節點
文字描述可能不太具體，我們看一下實現程式碼：
ts
// 定義陣列項的資料型別，包含id、name、parentId基本屬性
interface ArrayItem {
id: number,
name: string,
parentId: number
}
// 定義樹節點的資料型別，包含id、name、可能存在的子節點
interface TreeNode {
id: number,
name: string,
children?: TreeNode[], // 葉子節點沒有子節點
}
function array2Tree(arr: ArrayItem[]): TreeNode | null {
// 用於id和TreeNode的對映，map<key, value>，可通過id快速查詢到樹節點，時間複雜度為O(1)
const treeNode: Map<number, TreeNode> = new Map();
let root = null; // 樹根節點
arr.forEach(item => {
const {id, name, parentId} = item; // 解構賦值
// 定義樹節點tree node，並使用Map維持id與節點之間的關係
const node: TreeNode = {id, name}
treeNode.set(id, node);
// 使用parentId找出parentNode
const parentNode = treeNode.get(parentId);
if (parentNode) {
if (parentNode.children == null) {
parentNode.children = [];
}
// 找到父節點後，將當前陣列項轉換的節點新增到子節點列表中
parentNode.children.push(node)
}
// 在第一次迴圈中找到根節點，我們假定id=0的表示根節點
if (parentId === 0) {
root = node;
}
})
return root;
}
const tree = array2Tree(arrs); // 需要定義arrs
console.log(tree);
程式碼是使用ts完成的，清晰的展示了樹節點資料型別的定義，在轉換過程中資料型別的變化。直接執行ts程式碼是看不出來列印的結果的，我們可以新建一個vue-ts的專案，或者嫌麻煩的話可以直接使用官網提供的執行環境：playground
實現效果：
其實就是一個物件，物件的層次就像是樹一樣展開。
樹轉換為陣列
同樣也是這個例子，只不過是需要將樹轉換為陣列了。
陣列和樹在資料結構上最大的差異就是樹沒有parentId的屬性，如果一個節點有子節點，那麼該節點的id就應該是其子節點的parentId。老規矩，先來捋一下思路：
- 遍歷樹節點，使用廣度優先。樹的遍歷可分為廣度優先和深度優先，廣度優先表示橫向遍歷，深度優先表示縱向遍歷
- 將遍歷出的樹節點新增到佇列中，實現先進先出。佇列並不是js中的資料型別，但是我們可以使用陣列來實現佇列
- 將樹節點轉換為陣列項
- 根據節點的父子關係，設定陣列項的parentId，並將陣列項新增到陣列中
- 為了查詢遍歷，可使用Map來維持父節點和子節點的關係
實現程式碼:
```ts
// 定義資料結構
...
function tree2Array(root: TreeNode): ArrayItem[] {
// 定義子節點和父節點的對映關係，map<子節點，父節點>
const childToParent: Map
const arr: ArrayItem[] = []; // 返回的陣列
// 廣度優先遍歷樹，使用佇列儲存節點 const queue: TreeNode[] = []; queue.unshift(root); // 入隊，從頭部入隊 while(queue.length) { const curNode = queue.pop(); // 出隊，從尾部出隊，保證先進先出 if (curNode == null) break; // 迴圈結束，使用==包括了null和undefined的情況
const {id, name, children = []} = curNode; // 結構賦值，葉子節點沒有children屬性，所以預設為空陣列
const parentNode = childToParent.get(curNode); // 獲取當前節點的父節點 const parentId = parentNode?.id || 0; // 獲取父節點id，根節點設定為0 const item = {id, name, parentId}; // 定義陣列項 arr.push(item); // 插入到陣列中
// 繼續遍歷子節點，並且子節點入隊 children.forEach(child => { // 如果有子節點，則把子節點和當前節點通過Map保持關係 childToParent.set(child, curNode);
// 入隊 queue.unshift(child); }) }
return arr; } const array = tree2Array(obj); // 這個obj物件就是陣列轉換為樹打印出的結果 console.log(array) ```
執行結果:
可以發現，結果符合預期。
總結
總結一下，陣列和樹之間相互轉換一開始還挺蒙的，但是看完程式碼發現，其實也並不複雜。
- 陣列轉換為樹：從陣列的第一項開始，根據parentId，找到每一項的歸屬；若找不到，則表示當前陣列項為根節點
- 樹轉換為陣列：樹的每一個節點都可能會有很多子節點，按照廣度優先，從根節點開始遍歷，將每一個節點以及其子節點都新增到佇列中，按照先進先出的原則，逐一將節點都轉換為陣列項並新增到陣列中
- 在實現的過程中，可結合圖例，一步一步分析，最終實現結果