  樹是一種非線性表數據結構，樹的基本概念如下所列。
  （1）結點高度：結點到葉子結點的最長路徑（即邊數）。例題：[112\. 路徑總和](https://leetcode-cn.com/problems/path-sum/)。
  （2）結點深度：根結點到這個結點所經歷的邊的個數。例題：[104\. 二叉樹的最大深度](https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/)。
  （3）結點層數：結點深度加 1。
  （4）樹的高度：根結點的高度。例題：[面試題 04.02. 最小高度樹](https://leetcode-cn.com/problems/minimum-height-tree-lcci/)。
  后面幾張這種類型的圖都來源于《[數據結構與算法之美](https://time.geekbang.org/column/126)》。
:-: 
圖 2
  （5）二叉樹：只包含左右兩個子結點的樹（編號1）。
  （6）滿二叉樹：所有分支結點都存在左右子樹，并且所有葉子結點都在同一層上（編號2）。例題：[894\. 所有可能的滿二叉樹](https://leetcode-cn.com/problems/all-possible-full-binary-trees/)。
  （7）完全二叉樹：葉子結點都在最底下兩層，最后一層的葉子結點都靠左排列，并且除了最后一層，其余結點個數都要達到最大（編號3）。例題：[222\. 完全二叉樹的結點個數](https://leetcode-cn.com/problems/count-complete-tree-nodes/)。
:-: 
圖 3
## 一、二叉樹
**1）實現**
  有兩種方法存儲一棵二叉樹，第一種是基于指針的鏈式存儲法，[如下所示](https://codepen.io/strick/pen/LYGMrVO)。
~~~
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\. 二叉樹的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)，遞歸的在左右子樹中查找兩個指定的結點，最后判斷公共祖先所在的位置。在當前結點的左子樹，或在其右子樹，又或者它就是兩種的公共祖先。
**2）遍歷**
  二叉樹的遍歷有四種（[示例如下](https://codepen.io/strick/pen/mdVaKVz)）：
  （1）前序：先訪問當前結點，然后訪問左子樹，再訪問右子樹。
~~~
preOrder(root = this.root) {
//前序
if (!root) {
return;
}
console.log(root.data);
this.preOrder(root.left);
this.preOrder(root.right);
}
~~~
:-: 
圖 4
  面試題28[對稱二叉樹](https://leetcode-cn.com/problems/dui-cheng-de-er-cha-shu-lcof/)。前序遍歷的變種是先訪問右結點，再訪問左結點，如果其遍歷結果與前序遍歷結果相同，就說明是對稱的。
  面試題34[二叉樹中和為某一值的路徑](https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof/)。前序遍歷首先訪問根結點，在用前序遍歷訪問結點時，將其壓入棧中，遇到葉結點，就求和判斷結果是否符合要求。然后將葉結點出棧，回到父節點，繼續遍歷右子樹，遞歸執行該過程。
  （2）中序：先訪問左子樹，然后訪問當前結點，再訪問右子樹。
~~~
inOrder(root = this.root) {
//中序
if (!root) {
return;
}
this.midOrder(root.left);
console.log(root.data);
this.midOrder(root.right);
}
~~~
:-: 
圖 5
  面試題7[重建二叉樹](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)。前序遍歷第一個數是根結點，中序遍歷以根結點為界其兩邊分別是左右子樹，遞歸構建左右子樹。
  面試題54[BST中第 k 大的結點](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/)。中序遍歷BST，得到的序列是遞增的。
  （3）后序：先訪問左子樹，然后訪問右子樹，再訪問當前結點。
~~~
postOrder(root = this.root) {
//后序
if (!root) {
return;
}
this.backOrder(root.left);
this.backOrder(root.right);
console.log(root.data);
}
~~~
:-: 
圖 6
  面試題33[BST的后序遍歷序列](https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-hou-xu-bian-li-xu-lie-lcof/)。序列的最后一個數字是根結點，左子樹的結點都比根結點小，右子樹的結點都比根結點大，遞歸執行該過程。
  （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）會從根結點開始遍歷，沿著路徑直到這條路徑最后一個葉結點被訪問，接著原路回退并探索下一條路徑，也就是先深度后廣度地訪問結點，如下圖右半部分。
:-: 
  在《[算法小抄](https://labuladong.gitbook.io/algo/di-ling-zhang-bi-du-xi-lie/xue-xi-shu-ju-jie-gou-he-suan-fa-de-gao-xiao-fang-fa#san-suan-fa-shua-ti-zhi-nan)》一文中曾強調先刷二叉樹的LeetCode題目，因為很多難題本質上都是基于二叉樹的遍歷，例如LeetCode的[124 題](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)（二叉樹中的最大路徑和）、[105 題](https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)（從前序與中序遍歷序列構造二叉樹）和[99 題](https://leetcode-cn.com/problems/recover-binary-search-tree/)（恢復二叉搜索樹）。
**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);
}
~~~
  遞歸的數學模型就是[歸納法](https://baike.baidu.com/item/%E6%95%B0%E5%AD%A6%E5%BD%92%E7%BA%B3%E6%B3%95)，其過程如下。
  （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中查找一個結點的遞歸算法是（[代碼如下所示](https://codepen.io/strick/pen/JjGwZeZ)）：
  （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）刪除**
  針對刪除結點的子結點個數的不同，需要分類討論（[代碼如下所示](https://codepen.io/strick/pen/oNbJMoK)）：
  （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，讓整棵樹左右看起來比較對稱和平衡，不要出現左子樹很高、右子樹很矮的情況。
  在下面的[示例](https://codepen.io/strick/pen/eYJbLmo)中，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），下面的[示例](https://codepen.io/strick/pen/bGEOxLm)在構建一個大頂堆。
~~~
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) 的不穩定排序算法。排序主要分為兩個過程：一是構建堆；二是交換堆頂元素與最后一個元素的位置，[如下所示](https://codepen.io/strick/pen/pogqOMo)。
~~~
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大元素](https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/)，[劍指 Offer 41. 數據流中的中位數](https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/)。
  其中求中位數的方法很巧妙，會維護兩個堆：大頂堆和小頂堆。大頂堆中存儲前半部分數據，小頂堆中存儲后半部分數據，且小頂堆中的數據都大于大頂堆中的數據。如果有 n 個數據：
  （1）當 n 是偶數時，前 2/n? 個數據存儲在大頂堆中，后 2/n? 個數據存儲在小頂堆中。
  （2）當 n 是奇數時，大頂堆就存儲 2/n?+1 個數據，小頂堆中就存儲 2n? 個數據。
  這樣，大頂堆中的堆頂元素就是要找的中位數。
*****
> 原文出處：
[博客園-數據結構和算法躬行記](https://www.cnblogs.com/strick/category/1809992.html)
已建立一個微信前端交流群，如要進群，請先加微信號freedom20180706或掃描下面的二維碼，請求中需注明“看云加群”，在通過請求后就會把你拉進來。還搜集整理了一套[面試資料](https://github.com/pwstrick/daily)，歡迎閱讀。
推薦一款前端監控腳本：[shin-monitor](https://github.com/pwstrick/shin-monitor)，不僅能監控前端的錯誤、通信、打印等行為，還能計算各類性能參數，包括 FMP、LCP、FP 等。
- ES6
- 1、let和const
- 2、擴展運算符和剩余參數
- 3、解構
- 4、模板字面量
- 5、對象字面量的擴展
- 6、Symbol
- 7、代碼模塊化
- 8、數字
- 9、字符串
- 10、正則表達式
- 11、對象
- 12、數組
- 13、類型化數組
- 14、函數
- 15、箭頭函數和尾調用優化
- 16、Set
- 17、Map
- 18、迭代器
- 19、生成器
- 20、類
- 21、類的繼承
- 22、Promise
- 23、Promise的靜態方法和應用
- 24、代理和反射
- HTML
- 1、SVG
- 2、WebRTC基礎實踐
- 3、WebRTC視頻通話
- 4、Web音視頻基礎
- CSS進階
- 1、CSS基礎拾遺
- 2、偽類和偽元素
- 3、CSS屬性拾遺
- 4、浮動形狀
- 5、漸變
- 6、濾鏡
- 7、合成
- 8、裁剪和遮罩
- 9、網格布局
- 10、CSS方法論
- 11、管理后臺響應式改造
- React
- 1、函數式編程
- 2、JSX
- 3、組件
- 4、生命周期
- 5、React和DOM
- 6、事件
- 7、表單
- 8、樣式
- 9、組件通信
- 10、高階組件
- 11、Redux基礎
- 12、Redux中間件
- 13、React Router
- 14、測試框架
- 15、React Hooks
- 16、React源碼分析
- 利器
- 1、npm
- 2、Babel
- 3、webpack基礎
- 4、webpack進階
- 5、Git
- 6、Fiddler
- 7、自制腳手架
- 8、VSCode插件研發
- 9、WebView中的頁面調試方法
- Vue.js
- 1、數據綁定
- 2、指令
- 3、樣式和表單
- 4、組件
- 5、組件通信
- 6、內容分發
- 7、渲染函數和JSX
- 8、Vue Router
- 9、Vuex
- TypeScript
- 1、數據類型
- 2、接口
- 3、類
- 4、泛型
- 5、類型兼容性
- 6、高級類型
- 7、命名空間
- 8、裝飾器
- Node.js
- 1、Buffer、流和EventEmitter
- 2、文件系統和網絡
- 3、命令行工具
- 4、自建前端監控系統
- 5、定時任務的調試
- 6、自制短鏈系統
- 7、定時任務的進化史
- 8、通用接口
- 9、微前端實踐
- 10、接口日志查詢
- 11、E2E測試
- 12、BFF
- 13、MySQL歸檔
- 14、壓力測試
- 15、活動規則引擎
- 16、活動配置化
- 17、UmiJS版本升級
- 18、半吊子的可視化搭建系統
- 19、KOA源碼分析（上）
- 20、KOA源碼分析（下）
- 21、花10分鐘入門Node.js
- 22、Node環境升級日志
- 23、Worker threads
- 24、低代碼
- 25、Web自動化測試
- 26、接口攔截和頁面回放實驗
- 27、接口管理
- 28、Cypress自動化測試實踐
- 29、基于Electron的開播助手
- Node.js精進
- 1、模塊化
- 2、異步編程
- 3、流
- 4、事件觸發器
- 5、HTTP
- 6、文件
- 7、日志
- 8、錯誤處理
- 9、性能監控（上）
- 10、性能監控（下）
- 11、Socket.IO
- 12、ElasticSearch
- 監控系統
- 1、SDK
- 2、存儲和分析
- 3、性能監控
- 4、內存泄漏
- 5、小程序
- 6、較長的白屏時間
- 7、頁面奔潰
- 8、shin-monitor源碼分析
- 前端性能精進
- 1、優化方法論之測量
- 2、優化方法論之分析
- 3、瀏覽器之圖像
- 4、瀏覽器之呈現
- 5、瀏覽器之JavaScript
- 6、網絡
- 7、構建
- 前端體驗優化
- 1、概述
- 2、基建
- 3、后端
- 4、數據
- 5、后臺
- Web優化
- 1、CSS優化
- 2、JavaScript優化
- 3、圖像和網絡
- 4、用戶體驗和工具
- 5、網站優化
- 6、優化閉環實踐
- 數據結構與算法
- 1、鏈表
- 2、棧、隊列、散列表和位運算
- 3、二叉樹
- 4、二分查找
- 5、回溯算法
- 6、貪心算法
- 7、分治算法
- 8、動態規劃
- 程序員之路
- 大學
- 2011年
- 2012年
- 2013年
- 2014年
- 項目反思
- 前端基礎學習分享
- 2015年
- 再一次項目反思
- 然并卵
- PC網站CSS分享
- 2016年
- 制造自己的榫卯
- PrimusUI
- 2017年
- 工匠精神
- 2018年
- 2019年
- 前端學習之路分享
- 2020年
- 2021年
- 2022年
- 2023年
- 2024年
- 日志
- 2020