[toc]
# 幾個概念
## 路徑
在一棵樹中，從一個結點到另一個結點所經過的所有結點，被我們稱為兩個結點之間的路徑。
比如：A -> H 的路徑：
## 路徑長度
在一棵樹中，從一個結點到另一個結點所經過的“邊”的數量，被我們稱為兩個結點之間的路徑長度。
比如：A -> H的路徑長度為 3：
## 節點的帶權路徑長度
每一個節點都可以有一個權重（數字）。
帶權路徑長度：節點權重 * 節點到根節點的路徑長度
比如：H 的帶權路徑長度 = 3 * 3 = 9
## 樹的帶權路徑長度
樹的帶權路徑長度（也做WPL）：所有 `葉子` 節點的帶權路徑長度之和。
比如：下面這棵樹的 WPL = 3*3 + 6*3 + 1*2 + 4*2 + 8*2 = 53
## 哈夫曼樹
哈夫曼樹（Huffman Tree）：是在葉子結點和權重確定的情況下，帶權路徑長度最小的二叉樹，也被稱為最優二叉樹。
比如下圖左側就比右側 WPL 小。
總結：核心特點：權重越大的節點，越靠近根節點。
面試官問：什么是最優二叉樹？什么是哈夫曼樹？
## 哈夫曼編碼
哈夫曼編碼可以用來進行 `數據壓縮` 。
### 編碼
比如要壓縮：“acbcbacddaddaddccd”
1. 先統計文本中每個字符出現的頻率
2. 頻率當作權重構建哈夫曼樹
3. 根據哈夫曼樹對字符串進行編碼
編碼規則：
1. 左子節點是0，右子節點是1
2. 從根節點到葉子結果
根據哈夫曼樹可以將字符串編碼為：
* a:111
* ac:1111 0
* acb:1111 0110
* acbc:1111 011010
* acbcb:1111 0110 1011 0…
說明：編碼之后好像是變長了，但注意這里的存儲 單位是不同的：
- 1 字節(Byte) = 6 位(bit)
- 一個字母 = 1 字節 = 8 位
- 一個漢字 = 2~4字節 = 16~32位
- 而1010這個哈夫曼編碼，單位是位，一個1或0只帶1 位。
所以綜合：哈夫曼編碼的壓縮率在 20% ~ 90% 之間。
### 解碼
編碼過程就是：
1. 將哈夫曼編碼到哈夫曼樹上 “從根向下跑一遍”
2. 0 向左、 1 向右
3. 當遇到一個 “葉子” 節點時結束
4. 重復從根開始跑，重復 1~3
比如：1111 0110 1011 0... 到樹上跑得到：acbcb
## 用途
1. 數據壓縮
2. 加密、解密
# 構建哈夫曼樹的流程
1. 將帶權節點 `按升序` 放到數組中
2. 取出數組中最小的兩個節點做為子節點構造一棵樹，和為父節點
3. 將父節點的值放回數組中并 `排序`
4. 重復2~3步驟
拿出最小兩個節點：
將的父節點放回并排序
5. 重復2~3
6. 重復2~3
7. 重復2~3
最后數組中只剩下一個節點，說明構造結束！
# 代碼實現 - 構造哈夫曼樹
~~~
class Node {
constructor(data) {
this.data = data
this.left = null
this.right = null
}
}
class HuffmanTree {
constructor(arr) {
this.queue = arr
this.root = null
let first, second, parent
while(this.queue.length>1) {
// 排序
this.queue.sort((a,b)=>a-b)
first = this.queue.shift()
second = this.queue.shift()
parent = first + second
this.queue.unshift(parent)
parent = new Node(parent)
first = new Node(first)
second = new Node(second)
if(this.root === null) {
parent.left = first
parent.right = second
this.root = parent
} else {
if(this.root.data == first.data) {
parent.left = this.root
parent.right = second
this.root = parent
} else {
parent.left = first
parent.right = this.root
this.root = parent
}
}
}
}
}
~~~
