1. 概念
哈夫曼樹是一個特殊的二叉樹，它的特殊在于：
- 葉子節點帶有權值：對葉子結點賦予的一個有意義的數值量
- 二叉樹的帶權路徑長度：設二叉樹具有n個帶權值的葉子結點，從根結點到各個葉子結點的路徑長度與相應葉子結點權值的乘積之和，記為 WPL=Wklk，這里的WPL即帶權路徑長度（Weight Path Length），
- 權值越大的葉子結點越靠近根結點，而權值越小的葉子結點越遠離根結點
- 只有度為0的葉子結點和度為2的分支節點，不存在度為1的結點
綜上，總結哈夫曼樹的概念為：
哈夫曼樹：給定一組具有確定權值的葉子節點，帶權路徑長度最小的二叉樹
舉例：給定4個葉子結點，其權值分別為{2,3,4,7}，可以構造出形狀不同的多個二叉樹，
如上圖所示，可以根據給定的葉子結點構建出不同的二叉樹結構，按照計算以上三個二叉樹帶權路徑長度計算公式得出的WPL分別為32、41、30，根據哈夫曼樹定義可知，最右側WPL=30的這個二叉樹就是一個哈夫曼樹，
2. 基本思想
2.1 初始化
由給定的n個權值 {w1,w2,…,wn} 構造n顆只有一個根結點的二叉樹，從而得到一個二叉樹集合F= {T1,T2,…,Tn}
2.2 選取與合并
在集合F中選取根結點的權值最小的兩顆二叉樹分別作為左、右子樹構造一顆新的二叉樹，這顆二叉樹的根結點的權值為其左、右子樹根結點的權值之和
2.3 洗掉與加入
在集合F中洗掉作為作為左、右子樹的兩顆二叉樹，并將新建立的二叉樹加入到集合F中
2.4 遞回
重復以上選取與合并、洗掉與加入兩步，當集合F中只剩下一顆二叉樹時，這顆二叉樹便是哈夫曼樹
2.5 實體
我們按照上面的例子，初始化集合{2,3,4,7}來模擬下哈夫曼樹的推演程序，記錄如下：
3. 資料結構
設定一個陣列 huffTree 來存盤哈夫曼樹中各結點資訊，陣列元素的資料結構如下圖：
- weight 權值
- leftChild 左子節點，存盤陣列下標
- rightChild 右子節點，存盤陣列下標
- parent 父節點，存盤陣列下標
陣列大小可以通過2n-1來計算獲得，為何是2n-1大小，可以參考二叉樹性質來計算，
根據上面的初始化、選取與合并、洗掉與加入、遞回的步驟方法推演，進行陣列操作程序如下：
4. 代碼實作
參考的資料中是采用樸素的陣列進行存盤的，陣列存盤的困難在于不利于動態擴容和調整，這里采用List集合進行存盤，實際上底層也是陣列存盤，只是通過封裝好的容器進行呼叫即可，這里還是延用上面圖例中的權值陣列 {2,3,4,7}，除此之外，還可以使用 {2,3,5,7,5} 這種新構建結點等于已存在權值結點、多個權值結點權值相等各種特殊情況來進行驗證，
/**
* 哈夫曼樹
* created by guanjian on 2020/12/30 15:43
*/
public class HuffmanTree {
//權值結點
private Integer[] weightArray;
//哈夫曼樹結點總數 2*weights - 1
private int huffmanTreeNodeLength;
//哈夫曼樹結點陣列
private List<HuffmanTreeNode> huffmanTreeNodeList;
//每次獲取最小權值數量
private final static int minNodeLength = 2;
public HuffmanTree(Integer[] weightArray) {
Assert.notEmpty(weightArray, "weightArray can not be empty");
this.weightArray = weightArray;
}
/**
* 初始化哈夫曼樹結點陣列
*/
public void initHuffmanTreeNodeArray() {
//哈夫曼樹結點總數 2*weights - 1
this.huffmanTreeNodeLength = 2 * this.weightArray.length - 1;
this.huffmanTreeNodeList = Lists.newArrayListWithCapacity(huffmanTreeNodeLength);
//初始化填充哈夫曼樹結點
IntStream.range(0, weightArray.length).forEach(i -> {
//這里將權值灌入到node節點中
huffmanTreeNodeList.add(
HuffmanTreeNode.Builder.aHuffmanTreeNode()
.weight(weightArray[i])
.build()
);
});
System.out.format("初始化完成 huffmanTreeNodeList=%s \n", Arrays.toString(huffmanTreeNodeList.toArray()));
}
/**
* 查找最小權值方法
*/
public List<HuffmanTreeNode> findMinNodes() {
//按權值從小到大升序進行排序
List<HuffmanTreeNode> sortedList = huffmanTreeNodeList.stream()
.filter(x -> !x.isSorted())
.sorted(Comparator.comparing(HuffmanTreeNode::getWeight))
.collect(Collectors.toList());
sortedList.forEach(x -> System.out.format("排序 %s 處理 %s \n", x.getWeight(), x.isSorted()));
//取最小權值的兩個node
List<HuffmanTreeNode> list = sortedList.subList(0,
sortedList.size() >= minNodeLength ? minNodeLength : sortedList.size());
if (CollectionUtils.isEmpty(list)) return list;
list.forEach(x -> {
x.setSorted(true);
});
return list;
}
/**
* 構建哈夫曼樹
*/
public void buildHuffmanTree() {
for (; ; ) {
/**
* 選取權值最小的兩個結點，構造父節點
*/
List<HuffmanTreeNode> minNodes = findMinNodes();
if (minNodes.size() != minNodeLength) break;
//左子節點
HuffmanTreeNode leftChild = minNodes.get(0);
//右子節點
HuffmanTreeNode rightChild = minNodes.get(1);
//父結點
HuffmanTreeNode parent = HuffmanTreeNode.Builder.aHuffmanTreeNode()
.weight(leftChild.getWeight() + rightChild.getWeight())
.leftChild(leftChild)
.rightChild(rightChild)
.build();
leftChild.setParent(parent);
rightChild.setParent(parent);
System.out.println("====================================");
System.out.format("獲取左子結點權值=%s\n", leftChild.getWeight());
System.out.format("獲取右子結點權值=%s\n", rightChild.getWeight());
System.out.format("獲取父結點權值=%s\n", parent.getWeight());
huffmanTreeNodeList.add(parent);
}
}
/**
* 計算當前二叉樹的WPL
* weight（結點權值） * path（樹高度） = WPL（權值路徑）
*/
public void calculateWeightPathLength() {
System.out.println("====================================");
int wpl = 0;
for (HuffmanTreeNode node : huffmanTreeNodeList) {
//跳過構建結點,只計算權值結點
if (null != node.leftChild || null != node.rightChild) continue;
int path = 0;
HuffmanTreeNode currentNode = node;
while (null != currentNode.parent) {
path++;
currentNode = currentNode.parent;
}
System.out.format("權值：%s * 路徑長度：%s \n", node.getWeight(), path);
wpl += node.getWeight() * path;
}
System.out.format("WPL=%s \n", wpl);
}
public Integer[] getWeightArray() {
return weightArray;
}
public void setWeightArray(Integer[] weightArray) {
this.weightArray = weightArray;
}
public int getHuffmanTreeNodeLength() {
return huffmanTreeNodeLength;
}
public void setHuffmanTreeNodeLength(int huffmanTreeNodeLength) {
this.huffmanTreeNodeLength = huffmanTreeNodeLength;
}
public List<HuffmanTreeNode> getHuffmanTreeNodeList() {
return huffmanTreeNodeList;
}
public void setHuffmanTreeNodeList(List<HuffmanTreeNode> huffmanTreeNodeList) {
this.huffmanTreeNodeList = huffmanTreeNodeList;
}
public static int getMinNodeLength() {
return minNodeLength;
}
static class HuffmanTreeNode {
/**
* 父結點
*/
private HuffmanTreeNode parent;
/**
* 左子結點
*/
private HuffmanTreeNode leftChild;
/**
* 右子結點
*/
private HuffmanTreeNode rightChild;
/**
* 權重值
*/
private int weight;
/**
* 是否完成排序
*/
private boolean sorted;
public HuffmanTreeNode getParent() {
return parent;
}
public void setParent(HuffmanTreeNode parent) {
this.parent = parent;
}
public HuffmanTreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(HuffmanTreeNode leftChild) {
this.leftChild = leftChild;
}
public HuffmanTreeNode getRightChild() {
return rightChild;
}
public void setRightChild(HuffmanTreeNode rightChild) {
this.rightChild = rightChild;
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public boolean isSorted() {
return sorted;
}
public void setSorted(boolean sorted) {
this.sorted = sorted;
}
public static class Builder {
private HuffmanTreeNode parent;
private HuffmanTreeNode leftChild;
private HuffmanTreeNode rightChild;
private int weight;
private boolean sorted;
private Builder() {
}
public static Builder aHuffmanTreeNode() {
return new Builder();
}
public Builder weight(int weight) {
this.weight = weight;
return this;
}
public Builder parent(HuffmanTreeNode parent) {
this.parent = parent;
return this;
}
public Builder rightChild(HuffmanTreeNode rightChild) {
this.rightChild = rightChild;
return this;
}
public Builder leftChild(HuffmanTreeNode leftChild) {
this.leftChild = leftChild;
return this;
}
public Builder sorted(boolean sorted) {
this.sorted = sorted;
return this;
}
public HuffmanTreeNode build() {
HuffmanTreeNode huffmanTreeNode = new HuffmanTreeNode();
huffmanTreeNode.setLeftChild(this.leftChild);
huffmanTreeNode.setRightChild(this.rightChild);
huffmanTreeNode.setParent(this.parent);
huffmanTreeNode.setWeight(this.weight);
huffmanTreeNode.setSorted(this.sorted);
return huffmanTreeNode;
}
}
@Override
public String toString() {
return "HuffmanTreeNode{" +
"parent=" + parent +
", leftChild=" + leftChild +
", rightChild=" + rightChild +
", weight=" + weight +
", sorted=" + sorted +
'}';
}
}
public static void main(String[] args) {
//權值結點
Integer[] weightArray = new Integer[]{2,3,4,7};
//宣告哈夫曼樹
HuffmanTree huffmanTree = new HuffmanTree(weightArray);
//初始化哈夫曼樹
huffmanTree.initHuffmanTreeNodeArray();
//構建哈夫曼樹
huffmanTree.buildHuffmanTree();
//WPL
huffmanTree.calculateWeightPathLength();
}
}
【控制臺輸出】
初始化完成 huffmanTreeNodeList=[HuffmanTreeNode{parent=null, leftChild=null, rightChild=null, weight=2, sorted=false}, HuffmanTreeNode{parent=null, leftChild=null, rightChild=null, weight=3, sorted=false}, HuffmanTreeNode{parent=null, leftChild=null, rightChild=null, weight=4, sorted=false}, HuffmanTreeNode{parent=null, leftChild=null, rightChild=null, weight=7, sorted=false}]
排序 2 處理 false
排序 3 處理 false
排序 4 處理 false
排序 7 處理 false
====================================
獲取左子結點權值=2
獲取右子結點權值=3
獲取父結點權值=5
排序 4 處理 false
排序 5 處理 false
排序 7 處理 false
====================================
獲取左子結點權值=4
獲取右子結點權值=5
獲取父結點權值=9
排序 7 處理 false
排序 9 處理 false
====================================
獲取左子結點權值=7
獲取右子結點權值=9
獲取父結點權值=16
排序 16 處理 false
====================================
權值：2 * 路徑長度：3
權值：3 * 路徑長度：3
權值：4 * 路徑長度：2
權值：7 * 路徑長度：1
WPL=30
5. 參考
https://space.bilibili.com/26340287 懶貓老師資料結構講解
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/243303.html
標籤：java
上一篇：JAVA學習
下一篇：SpringIOC