百度百科定義
給定n個權(quán)值作為n個葉子結(jié)點递宅，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達(dá)到最小苍狰，稱這樣的二叉樹為最優(yōu)二叉樹办龄，也稱為哈夫曼樹(Huffman Tree)。哈夫曼樹是帶權(quán)路徑長度最短的樹淋昭，權(quán)值較大的結(jié)點離根較近俐填。
image.png
哈夫曼樹數(shù)據(jù)結(jié)構(gòu)
- 左子樹
- 右子樹
- 父節(jié)點
- 權(quán)重
- 數(shù)據(jù)
public static class TreeNode<T> implements Comparable<TreeNode<T>>{
T data;
int weight;
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(T data, int wei) {
this.data = data;
this.weight = wei;
leftChild = null;
rightChild = null;
parent = null;
}
@Override
public int compareTo(TreeNode<T> o) {
if (this.weight > o.weight) {
return -1;
} else if (this.weight < o.weight) {
return 1;
}
return 0;
}
}
哈夫曼樹構(gòu)建
假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點翔忽。 n個權(quán)值分別設(shè)為 w1英融、w2、…歇式、wn驶悟，則哈夫曼樹的構(gòu)造規(guī)則為：
- (1) 將w1、w2材失、…痕鳍，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；
- (2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左笼呆、右子樹熊响，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和诗赌；
- (3 )從森林中刪除選取的兩棵樹汗茄，并將新樹加入森林；
- (4) 重復(fù)(2)铭若、(3)步洪碳，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹叼屠。
舉個例子
有這樣權(quán)值數(shù)組 {13,6,8,19,2,36,5,25 }
- 1 排序
{2,5,6,8,13,19,25,36} -
2 在這些數(shù)中 選擇兩個最小的權(quán)值偶宫，作為一棵新樹node的左右節(jié)點（小的在做，大的在右）环鲤，node的權(quán)值為其左纯趋、右子樹根結(jié)點權(quán)值之和
步驟1.png - 3 把新節(jié)點node的權(quán)值加入數(shù)組，重新排序
{7,6,8,13,19,25,36}
重復(fù)步驟2
步驟2.png
-
4 重復(fù)步驟3
排序后的權(quán)值數(shù)組 {8,13,13,19,25,36}
image.png
排序后的權(quán)值數(shù)組{13,19,21,25,36}
image.png
排序后的權(quán)值數(shù)組{21,25,32,36}
image.png
排序后的權(quán)值數(shù)組 {32,36,46}
image.png
排序后的權(quán)值數(shù)組{46,68}
image.png
排序后的權(quán)值數(shù)組{114}
public TreeNode createHaffManTree(ArrayList<TreeNode> list) {
while (list.size() > 1) {
Collections.sort(list);
TreeNode left = list.get(list.size()-1);
TreeNode right = list.get(list.size()-2);
TreeNode parent = new TreeNode("p", left.weight + right.weight);
parent.leftChild = left;
left.parent = parent;
parent.rightChild = right;
right.parent = parent;
list.remove(left);
list.remove(right);
list.add(parent);
}
root = list.get(0);
return list.get(0);
}
哈夫曼樹遍歷
層次遍歷 ：使用隊列實現(xiàn)層次遍歷
我們遍歷這棵樹
image.png
步驟
- 1 把根節(jié)點加入到隊列]
list.offer(root);
隊列{114}
- 2 隊列l(wèi)ist不為空冷离，彈出隊頭吵冒，輸出
TreeNode node = list.pop();
System.out.println(node.data);
- 3 讀取隊頭node 的左孩子，和右孩子西剥，如果孩子不為空痹栖，孩子加入隊列
if (node.leftChild != null) {
list.offer(node.leftChild);
}
if (node.rightChild != null) {
list.offer(node.rightChild);
}
- 現(xiàn)在隊列的數(shù)據(jù){46,68}
- 彈出46 ，隊尾加入46的左孩子瞭空，右孩子揪阿，隊列現(xiàn)在的數(shù)據(jù){68,21,25}
- 彈出68 ，隊尾加入68的左孩子咆畏，右孩子南捂，隊列現(xiàn)在的數(shù)據(jù){21,25,32,36}
- 彈出21 ，隊尾加入21的左孩子旧找，右孩子溺健，隊列現(xiàn)在的數(shù)據(jù){25,32,36,8,13}
- 彈出25 ，隊尾加入25的左孩子钮蛛，右孩子鞭缭，25沒有左右孩子，隊列現(xiàn)在的數(shù)據(jù){32,36,8,13}
- 彈出32 魏颓，隊尾加入32的左孩子岭辣，右孩子，隊列現(xiàn)在的數(shù)據(jù){36,8,13,13,19}
- 彈出36 甸饱，隊尾加入32的左孩子沦童，右孩子，36沒有左右孩子,隊列現(xiàn)在的數(shù)據(jù){8,13,13,19}
- 彈出8 ，隊尾加入8的左孩子搞动，右孩子, 沒有左右孩子，隊列現(xiàn)在的數(shù)據(jù){13,13,19}
- 彈出13 渣刷，隊尾加入13的左孩子鹦肿，右孩子，隊列現(xiàn)在的數(shù)據(jù){13,19,6,7}
- 彈出13 辅柴，隊尾加入13的左孩子箩溃，右孩子，隊列現(xiàn)在的數(shù)據(jù){19,6,7}
- 彈出19 碌嘀，隊尾加入19的左孩子涣旨，右孩子，隊列現(xiàn)在的數(shù)據(jù){6,7}
- 彈出6股冗，隊尾加入6的左孩子霹陡，右孩子，隊列現(xiàn)在的數(shù)據(jù){7}
- 彈出7止状，隊尾加入7的左孩子烹棉，右孩子，隊列現(xiàn)在的數(shù)據(jù){2,5}
- 彈出2怯疤，隊尾加入2的左孩子浆洗，右孩子，隊列現(xiàn)在的數(shù)據(jù){5}
- 彈出5集峦，隊尾加入5的左孩子伏社，右孩子，隊列現(xiàn)在的數(shù)據(jù){}
- 隊列為空塔淤，遍歷結(jié)束
image.png
public void showHaffman(TreeNode root) {
LinkedList<TreeNode> list = new LinkedList<>();
ArrayList<TreeNode> arrayList = new ArrayList<>();
list.offer(root);
while (!list.isEmpty()) {
TreeNode node = list.pop();
System.out.println(node.data);
if (node.leftChild != null) {
list.offer(node.leftChild);
}
if (node.rightChild != null) {
list.offer(node.rightChild);
}
}
}
獲取哈夫曼編碼
image.png
- 8 的哈夫曼編碼：000
- 6 的哈夫曼編碼：0010
- 2 的哈夫曼編碼：00110
- 5 的哈夫曼編碼：00111
- 25 的哈夫曼編碼：01
- 13 的哈夫曼編碼：100
- 19 的哈夫曼編碼：101
- 19 的哈夫曼編碼：11
image.png
public void getCode(TreeNode node) {
Stack<String> stack = new Stack<>();
TreeNode tNode = node;
while (tNode != null && tNode.parent != null) {
// left 0, right 1
if (tNode.parent.leftChild == tNode) {
stack.push("0");
} else if (tNode.parent.rightChild == tNode) {
stack.push("1");
}
tNode = tNode.parent;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
}
測試
public static void main(String[] args) {
ArrayList<TreeNode> list = new ArrayList<>();
TreeNode<String> node = new TreeNode("good", 54);
list.add(node);
list.add(new TreeNode("morning", 10));
list.add(new TreeNode("afternoon", 20));
list.add(new TreeNode("hello", 100));
list.add(new TreeNode("hi", 200));
HaffmanTree tree = new HaffmanTree();
tree.createHaffManTree(list);
tree.showHaffman(tree.root);
tree.getCode(node);
}
