|
1. 基本介紹：  二叉樹(shù)路徑：從一個(gè)節(jié)點(diǎn)到達(dá)其后輩節(jié)點(diǎn)的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長(zhǎng)度。上面這棵二叉樹(shù)，黃色的線就是50這個(gè)節(jié)點(diǎn)到15這個(gè)節(jié)點(diǎn)的路徑，路徑長(zhǎng)度為3。樹(shù)有n層，那么根節(jié)點(diǎn)到第n層節(jié)點(diǎn)的路徑長(zhǎng)度為(n-1)。 帶權(quán)路徑長(zhǎng)度：就是路徑長(zhǎng)度乘以該節(jié)點(diǎn)的值。比如50到15的帶權(quán)路徑長(zhǎng)度就是 3 * 15 = 45。 樹(shù)的帶權(quán)路徑長(zhǎng)度：所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，記作wpl。 赫夫曼樹(shù)：樹(shù)的帶權(quán)路徑長(zhǎng)度最小的的樹(shù)稱為最優(yōu)二叉樹(shù)，也稱為赫夫曼樹(shù)。也就說(shuō)，**wpl最小的樹(shù)就叫做赫夫曼樹(shù)。**從樹(shù)的帶權(quán)路徑長(zhǎng)度的定義可以知道，要想該值最小，離根節(jié)點(diǎn)越近的值應(yīng)該越大，才能使帶權(quán)路徑長(zhǎng)度最小。
給定13, 7, 8, 3這四個(gè)數(shù)作為葉子結(jié)點(diǎn)，構(gòu)建成二叉樹(shù)，部分情況如下：  二叉樹(shù)這種情況，權(quán)值為 2 * 13 + 2 * 7 + 2 * 8 + 2 * 3 = 62。  二叉樹(shù)這種情況，權(quán)值為1 * 13 + 2 * 8 + 3 * 7 + 3 * 3 = 59。 顯然第二種情況權(quán)值更小，確保沒(méi)有更小的情況下，這棵二叉樹(shù)就叫做赫夫曼樹(shù)。 2. 構(gòu)建赫夫曼樹(shù)： 假如現(xiàn)在要將13, 7, 8, 3, 29, 6, 1構(gòu)建成赫夫曼樹(shù)，步驟如下： 首先將數(shù)組升序排序；結(jié)果就是1, 3, 6, 7, 8,13, 29。 取出排序后的前兩個(gè)數(shù)，構(gòu)建成一棵二叉樹(shù)，根節(jié)點(diǎn)為兩個(gè)子節(jié)點(diǎn)之和；即取出1和3，構(gòu)建出如下二叉樹(shù)：
 第一步此時(shí)數(shù)組中的1和3就已經(jīng)用掉了，將上一步構(gòu)建的二叉樹(shù)的根節(jié)點(diǎn)4放入數(shù)組中排序，結(jié)果就是：4, 6, 7, 8, 13, 29。 再?gòu)男蛄兄腥〕鰞蓚€(gè)數(shù)，即4和6，構(gòu)建成一棵二叉樹(shù)，如下圖：
 第二步再將10放到序列中，此時(shí)的序列就是這樣的：7, 8, 10, 13, 29。 再?gòu)男蛄兄腥〕?code style="font-size: 14px;padding: 2px 4px;border-radius: 4px;margin-right: 2px;margin-left: 2px;background-color: rgba(27, 31, 35, 0.05);font-family: "Operator Mono", Consolas, Monaco, Menlo, monospace;word-break: break-all;color: rgb(239, 112, 96);">7和8，構(gòu)建二叉樹(shù)，如下：
 第三步將15放到序列中，此時(shí)序列就變成了：10, 13, 15, 29，并且此時(shí)構(gòu)建出了兩棵二叉樹(shù)，還沒(méi)關(guān)聯(lián)起來(lái)，先不用急。 取出10和13，構(gòu)建成二叉樹(shù)，此時(shí)二叉樹(shù)就變成了：
 第四步將23放到序列中，序列就變成了：15, 23, 29。 取出15和23，構(gòu)建成二叉樹(shù)，15和23是兩棵樹(shù)的根節(jié)點(diǎn)，經(jīng)過(guò)這一步，兩棵樹(shù)就合并了：
 第五步- 現(xiàn)在序列中就剩下
29和38了，所以將29加到這棵樹(shù)上就好了，如下圖：
 第六步- 經(jīng)過(guò)上面的步驟，就將給定的這個(gè)序列構(gòu)建成了赫夫曼樹(shù)。
3. 代碼實(shí)現(xiàn)： /**
* 赫夫曼樹(shù)
* @author zhu
*
*/
public class HuffmanTree {
/**
* 構(gòu)建赫夫曼樹(shù)
* @param arr
* @return
*/
public static Node buildHufmanTree(int[] arr) {
// 將數(shù)組轉(zhuǎn)成集合，方便增刪元素
List<Node> nodes = new ArrayList<>();
for (int i=0; i<arr.length; i++) {
nodes.add(new Node(arr[i]));
}
// 對(duì)集合進(jìn)行排序
Collections.sort(nodes);
// 循環(huán)構(gòu)建
while (nodes.size() > 1) {
// 取出前兩個(gè)節(jié)點(diǎn)，構(gòu)建二叉樹(shù)
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
parentNode.setLeft(leftNode);
parentNode.setRight(rightNode);
// 移除用掉了的元素，將parent的值添加進(jìn)集合
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
// 重新排序
Collections.sort(nodes);
}
// 返回赫夫曼樹(shù)的根節(jié)點(diǎn)
return nodes.get(0);
}
/**
* 前序遍歷
*
* @param root
*/
public static void preOrder(Node root) {
// 先輸出當(dāng)前節(jié)點(diǎn)
System.out.println(root.getValue());
// 判斷左子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getLeft() != null) {
preOrder(root.getLeft());
}
// 判斷右子節(jié)點(diǎn)是否為空，不為空就遞歸
if (root.getRight() != null) {
preOrder(root.getRight());
}
}
/**
* 節(jié)點(diǎn)內(nèi)部類，實(shí)現(xiàn)compareble接口，方便對(duì)node排序
* @author zhu
*
*/
static class Node implements Comparable<Node>{
private int value;
private Node left;
private Node right;
public Node(int val) {
this.value = val;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
@Override
public int compareTo(Node o) {
// 升序
return this.value - o.value;
}
}
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node node = buildHufmanTree(arr);
preOrder(node);
}
}
上面是創(chuàng)建赫夫曼樹(shù)的完整代碼，構(gòu)件好之后，用前序遍歷方法遍歷一下，然后看看與上面圖中的赫夫曼樹(shù)前序遍歷結(jié)果是否一致，如果一致，表示構(gòu)建成功。
|
