數據結構和演算法躬行記（3）——二叉樹
- 2020 年 9 月 7 日
- 筆記
- 數據結構和演算法躬行記
樹是一種非線性表數據結構，樹的基本概念如下所列。
（1）結點高度：結點到葉子結點的最長路徑（即邊數）。例題：112. 路徑總和。
（2）結點深度：根結點到這個結點所經歷的邊的個數。例題：104. 二叉樹的最大深度。
（3）結點層數：結點深度加 1。
（4）樹的高度：根結點的高度。例題：面試題 04.02. 最小高度樹。
後面幾張這種類型的圖都來源於《數據結構與演算法之美》。
圖 2
（5）二叉樹：只包含左右兩個子結點的樹（編號1）。
（6）滿二叉樹：所有分支結點都存在左右子樹，並且所有葉子結點都在同一層上（編號2）。例題：894. 所有可能的滿二叉樹。
（7）完全二叉樹：葉子結點都在最底下兩層，最後一層的葉子結點都靠左排列，並且除了最後一層，其餘結點個數都要達到最大（編號3）。例題：222. 完全二叉樹的結點個數。
圖 3
一、二叉樹
1）實現
有兩種方法存儲一棵二叉樹，第一種是基於指針的鏈式存儲法，如下所示。
class Node { constructor(data) { this.data = data; this.left = null; this.right = null; } } class TreeList { constructor(datas) { this.root = null; datas.forEach((value) => { const node = new Node(value); if (this.root == null) { this.root = node; return; } this.insert(this.root, node); }); } insert(parent, child) { if (parent.data > child.data) { parent.left === null ? (parent.left = child) : this.insert(parent.left, child); return; } parent.right === null ? (parent.right = child) : this.insert(parent.right, child); } }
第二種是基於數組的順序存儲法。
left = 2 * index + 1; //左結點下標 right = 2 * index + 2; //右結點下標
例題：LeetCode的236. 二叉樹的最近公共祖先，遞歸的在左右子樹中查找兩個指定的結點，最後判斷公共祖先所在的位置。在當前結點的左子樹，或在其右子樹，又或者它就是兩種的公共祖先。
2）遍歷
二叉樹的遍歷有四種（示例如下）：
（1）前序：先訪問當前結點，然後訪問左子樹，再訪問右子樹。
preOrder(root = this.root) { //前序 if (!root) { return; } console.log(root.data); this.preOrder(root.left); this.preOrder(root.right); }
圖 4
面試題28 對稱二叉樹。前序遍歷的變種是先訪問右結點，再訪問左結點，如果其遍歷結果與前序遍歷結果相同，就說明是對稱的。
面試題34 二叉樹中和為某一值的路徑。前序遍歷首先訪問根結點，在用前序遍歷訪問結點時，將其壓入棧中，遇到葉結點，就求和判斷結果是否符合要求。然後將葉結點出棧，回到父節點，繼續遍歷右子樹，遞歸執行該過程。
（2）中序：先訪問左子樹，然後訪問當前結點，再訪問右子樹。
inOrder(root = this.root) { //中序 if (!root) { return; } this.midOrder(root.left); console.log(root.data); this.midOrder(root.right); }
圖 5
面試題7 重建二叉樹。前序遍歷第一個數是根結點，中序遍歷以根結點為界其兩邊分別是左右子樹，遞歸構建左右子樹。
面試題54 BST中第 k 大的結點。中序遍歷BST，得到的序列是遞增的。
（3）後序：先訪問左子樹，然後訪問右子樹，再訪問當前結點。
postOrder(root = this.root) { //後序 if (!root) { return; } this.backOrder(root.left); this.backOrder(root.right); console.log(root.data); }
圖 6
面試題33 BST的後序遍歷序列。序列的最後一個數字是根結點，左子樹的結點都比根結點小，右子樹的結點都比根結點大，遞歸執行該過程。
（4）層序：自上而下，自左至右逐層訪問樹的結點。利用一個輔助隊列來完成層序遍歷。
levelOrder(node = this.root) { //層序 let queue = []; queue.push(node); // 根結點入隊 while (queue.length) { node = queue.shift(); // 出隊 console.log(node.data); // 訪問該結點 if (node.left) { // 如果它的右子樹不為空 queue.push(node.left); // 將左子樹的根結點入隊 } if (node.right) { // 如果它的右子樹不為空 queue.push(node.right); // 將右子樹的根結點入隊 } } }
除了層序遍歷之外，其餘三種都採用遞歸的方式來遍歷二叉樹。
有兩種圖的搜索演算法，也適用於樹。
（1）廣度優先搜索演算法（Breadth-First Search，BFS）會從根結點開始遍歷，先訪問其所有的相鄰點，就像一次訪問樹的一層，也就是先寬後深地訪問結點，之前的層序遍歷就是BFS，如下圖左半部分。
（2）深度優先搜索演算法（Depth-First-Search，DFS）會從根結點開始遍歷，沿著路徑直到這條路徑最後一個葉結點被訪問，接著原路回退並探索下一條路徑，也就是先深度後廣度地訪問結點，如下圖右半部分。
在《演算法小抄》一文中曾強調先刷二叉樹的LeetCode題目，因為很多難題本質上都是基於二叉樹的遍歷，例如LeetCode的124 題（二叉樹中的最大路徑和）、105 題（從前序與中序遍歷序列構造二叉樹）和99 題（恢復二叉搜索樹）。
3）遞歸
遞歸是一種應用廣泛的編程技巧，如果要使用遞歸，需要滿足三個條件。
（1）一個問題的解可以分解為幾個子問題的解。
（2）這個問題與分解之後的子問題，除了數據規模不同，求解思路完全一樣。
（3）存在遞歸終止條件，即基準線條件（Base Case）。
注意，遞歸的關鍵就是找到將大問題分解為小問題的規律（推薦畫出遞歸樹），基於此寫出遞推公式，然後再推敲終止條件，並且需要警惕重複計算。下面是一個遞歸的大致模板。
function recursion(level, param1, param2, ...) { //遞歸的終止條件 if(level > MAX_LEVEL) { console.log("result"); return; } //數據處理 processData(level, data1,...); //繼續遞歸 recursion(level + 1, p1, ...); //收尾工作 reverseState(level); }
遞歸的數學模型就是歸納法，其過程如下。
（1）基礎情況：證明 P(b)語句成立，該步驟只需帶入數字即可。
（2）聲明假設：假設 P(n)語句成立。
（3）歸納步驟：證明如果 P(n)語句成立，那麼 P(n+1) 語句也一定成立。
例如設計一程式，求自然數 N 的階乘 N!。
（1）當 N=1 時，N!=1。
（2）假設 P(N)=N!，P(N+1)=(N+1)!。
（3）證明 P(N) 和 P(N+1) 的關係：
P(N+1) = (N+1)! = (N+1)×(N)×…×2×1 = (N+1)×N! = (N+1)×P(N)
根據這個公式可構造一個遞歸函數：
function factorial(N) { return N * factorial(N - 1); //遞歸部分 }
在採用數學歸納法設計遞歸程式後，就能擺脫每一步的遞推，直接根據分析就能轉化為程式碼。
試圖想清楚整個遞和歸過程的做法，實際上是一種思維誤區，不符合人腦平鋪直敘的思維方式。
二、二叉查找樹
在二叉查找樹（Binary Search Tree，BST）中，每個結點的值都大於左子結點，小於右子結點。當中序遍歷BST時，就可在 O(n) 的時間複雜度內輸出有序的結點。
BST的時間複雜度和樹的高度成正比，即 O(height)，經過推導後，完全二叉樹的高度（height）小於等於 log2^n。
平衡二叉查找樹的高度接近 logn，所以插入、刪除、查找等操作的時間複雜度也比較穩定，都是 O(logn)。
1）操作
在BST中查找一個結點的遞歸演算法是（程式碼如下所示）：
（1）如果被查找的結點和根結點的值相等，則查找命中，否則就遞歸地的在適當的子樹中繼續查找。
（2）如果被查找的結點值較小就選擇左子樹，否則就選擇右子樹。
find(data) { //查找 let node = this.root; while (node != null) { if (data == node.data) { return node; } data < node.data ? (node = node.left) : (node = node.right); } return null; }
BST插入結點的過程和查找差不多，依次比較結點值和左右子樹的大小。
insert(parent, child) { //插入 if (parent.data > child.data) { parent.left === null ? (parent.left = child) : this.insert(parent.left, child); return; } parent.right === null ? (parent.right = child) : this.insert(parent.right, child); }
在BST中查找最大和最小的結點，以最小值為例，如果根結點的左鏈接為空，那麼一棵BST中的最小值就是根結點；如果左鏈接非空，那麼最小值就是左子樹中的最小值。
min(node = this.root) { //最小值 if (node.left == null) return node; return this.min(node.left); }
2）刪除
針對刪除結點的子結點個數的不同，需要分類討論（程式碼如下所示）：
（1）如果沒有子結點，那麼只需將父結點中，鏈接刪除結點的指針置為 null。
（2）如果只有一個子結點，那麼只需更新父結點中，鏈接刪除結點的指針指向其子結點即可。
（3）如果包含兩個子結點，那麼需要先找到該結點右子樹中的最小結點，替換要刪除的結點；然後再刪除該最小結點，由於最小結點肯定沒有左子結點，因此可以使用上面兩條規則刪除它。
圖 7
del(data) { //刪除 let p = this.root, //p指向要刪除的結點，初始化指向根結點 parent = null; //父結點 while (p != null && p.data != data) { parent = p; data > p.data ? (p = p.right) : (p = p.left); } if (p == null) return; //沒有找到 // 要刪除的結點有兩個子結點 if (p.left != null && p.right != null) { //查找右子樹中最小結點 let minP = p.right, minParent = p; //minParent表示minP的父結點 while (minP.left != null) { minParent = minP; minP = minP.left; } p.data = minP.data; //將minP的數據替換到p中 p = minP; //下面就變成了刪除minP了 parent = minParent; } // 刪除結點是葉子結點或者僅有一個子結點 let child; //p的子結點 if (p.left != null) child = p.left; else if (p.right != null) child = p.right; else child = null; if (parent == null) this.root = child; // 刪除的是根結點 else if (parent.left == p) parent.left = child; else parent.right = child; }
3）數據重複
要讓BST支援重複數據，可以有兩種處理方式。
（1）在每個結點中增加一個鏈表，把相同的值存儲到鏈表中。
（2）將相同的值插入到結點的右子樹中，作為大於這個結點來處理。
4）平衡二叉查找樹
平衡二叉樹是指任意一個結點的左右子樹的高度相差不能大於 1，讓整棵樹左右看起來比較對稱和平衡，不要出現左子樹很高、右子樹很矮的情況。
在下面的示例中，height()函數會自頂向下遞歸的計算結點的高度，isBalanced()函數會判斷左右子樹的高度差。
function isBalanced(root) { if (root == null) return true; if (Math.abs(height(root.left) - height(root.right)) > 1) { return false; } return isBalanced(root.left) && isBalanced(root.right); } function height(root) { if (root == null) return 0; return Math.max(height(root.left) + 1, height(root.right) + 1); }
三、堆
堆（heap）是一種特殊的樹形數據結構，它有兩個特性：
（1）必須是一棵完全二叉樹。
（2）結點的值要大於等於或小於等於兩個子結點的值。
當結點的值小於等於兩個子結點的值，稱之為小頂堆；當結點的值大於等於兩個子結點的值，稱之為大頂堆。
1）實現
往堆中插入一個元素後，需要繼續滿足堆的兩個特性，這個過程叫做堆化（heapify），下面的示例在構建一個大頂堆。
function heapify(arr, x, len) { let l = 2 * x + 1, //左結點 r = 2 * x + 2, //右結點 largest = x, temp; if (l < len && arr[l] > arr[largest]) { largest = l; } if (r < len && arr[r] > arr[largest]) { largest = r; } if (largest != x) { //交換位置 temp = arr[x]; arr[x] = arr[largest]; arr[largest] = temp; heapify(arr, largest, len); } } const tree = [4, 5, 1, 2, 3, 6], heapSize = tree.length; for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(tree, i, heapSize); }
2）堆排序
堆排序是一種原地的、時間複雜度為 O(nlogn) 的不穩定排序演算法。排序主要分為兩個過程：一是構建堆；二是交換堆頂元素與最後一個元素的位置，如下所示。
function heapSort(arr) { let heapSize = arr.length, temp; //建堆 for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) { heapify(arr, i, heapSize); } //堆排序 for (let j = heapSize - 1; j >= 1; j--) { temp = arr[0]; arr[0] = arr[j]; arr[j] = temp; heapify(arr, 0, --heapSize); } return arr; }
3）應用
堆有幾個非常重要的應用，例如優先順序隊列、求Top K和求中位數。例題：703. 數據流中的第K大元素，劍指 Offer 41. 數據流中的中位數。
其中求中位數的方法很巧妙，會維護兩個堆：大頂堆和小頂堆。大頂堆中存儲前半部分數據，小頂堆中存儲後半部分數據，且小頂堆中的數據都大於大頂堆中的數據。如果有 n 個數據：
（1）當 n 是偶數時，前 2/n 個數據存儲在大頂堆中，後 2/n 個數據存儲在小頂堆中。
（2）當 n 是奇數時，大頂堆就存儲 2/n+1 個數據，小頂堆中就存儲 2n 個數據。
這樣，大頂堆中的堆頂元素就是要找的中位數。
