哈夫曼樹又稱為最優二叉樹。

1、路徑和路徑長度

在一棵樹中，從一個節點往下可以達到的孩子或者子孫節點之間的通路稱為路徑。通路中分支的數目稱為路徑長度。若規定根節點的層數為1，則從根節點
到第L層節點的路徑長度為L-1.

2、節點的權和帶權路徑長度

若將樹中結點賦給一個有著某種含義的數值，則這個數值稱為該結點的權。結點的帶權路徑長度為：從根結點到該結點之間的路徑長度與該結點的權的乘積。

3、樹的帶權路徑長度

樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。

---

4、哈夫曼樹的構造：

假設有n個權值，則構造出的哈夫曼樹有N個葉子節點。n個權值分別設為w1、w2……wn，則哈夫曼樹的構造規則為：

1、將w1、w2……wn看成是有n棵樹的森林（每棵樹僅有一個節點）；
2、在森林中選出兩個根節點權值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根節點權值為其左、右子樹根節點權值之和；
3、從森林中刪除選取的兩棵樹，并將新樹加入森林；
4、重復2、3步，直到森林中只剩一棵樹為止，該樹即為所求的的哈夫曼樹。

---

5、基本性質：

具有n個葉子節點的哈夫曼樹，一共需要2n-1個葉子節點。

---

6、java實現構造哈夫曼樹以及對哈夫曼樹的廣度優先遍歷：

Node.java

/*** 哈夫曼樹的結點類* @author lmb**/ public class Node<T> implements Comparable<Node<T>> {private T data;private double weight;private Node<T> left;private Node<T> right;public Node(T data, double weight) {super();this.data = data;this.weight = weight;}public T getData() {return data;}public void setData(T data) {this.data = data;}public double getWeight() {return weight;}public void setWeight(double weight) {this.weight = weight;}public Node<T> getLeft() {return left;}public void setLeft(Node<T> left) {this.left = left;}public Node<T> getRight() {return right;}public void setRight(Node<T> right) {this.right = right;}public String toString(){return "data : " + this.data + "; weight : " + this.weight;}@Overridepublic int compareTo(Node<T> other) {if (other.getWeight() > this.getWeight()) {return 1;}if (other.getWeight() < this.getWeight()) {return -1;}return 0;}}

HuffmanTree.java

import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue;import edu.emory.mathcs.backport.java.util.Collections;public class HuffmanTree<T> {public static void main(String[] args){List<Node<String>> list = new ArrayList<Node<String>>();list.add(new Node<String>("a",9));list.add(new Node<String>("b",5));list.add(new Node<String>("c",3));list.add(new Node<String>("d",7));list.add(new Node<String>("e",8));list.add(new Node<String>("f",6));//構造一棵哈夫曼樹Node<String> root = createTree(list);//廣度優先遍歷剛剛構造的哈夫曼樹List<Node<String>> nodes = breadth(root);for (int i = 0; i < nodes.size(); i++) {System.out.println(nodes.get(i));}}//創建哈夫曼樹public static <T> Node<T> createTree(List<Node<T>> nodes){while(nodes.size() > 1){Collections.sort(nodes);Node<T> left = nodes.get(nodes.size() - 1);//左節點Node<T> right = nodes.get(nodes.size() - 2);//右節點//父節點Node<T> parent = new Node<T>(null,left.getWeight() + right.getWeight());//利用左右節點構造父節點parent.setLeft(left);parent.setRight(right);//從森林中刪除所選的兩棵樹，并將新樹加入森林nodes.remove(left);nodes.remove(right);nodes.add(parent); }return nodes.get(0);}public static <T> List<Node<T>> breadth(Node<T> root){List<Node<T>> list = new ArrayList<Node<T>>();Queue<Node<T>> queue = new ArrayDeque<Node<T>>();//如果根節點不為空，將根節點加入隊列if (root != null) {queue.offer(root);}while(!queue.isEmpty()){//將隊列前端元素節點加入list中(使用但不移出)list.add(queue.peek());//獲取并移出隊列中的元素節點Node<T> node = queue.poll();//如果節點的左子樹存在，將其加入隊列if (node.getLeft() != null) {queue.offer(node.getLeft());}//如果節點的右子樹存在，將其加入隊列if (node.getRight() != null) {queue.offer(node.getRight());}}return list;}}

運行結果：

data : null; weight : 38.0
data : null; weight : 16.0
data : null; weight : 22.0
data : null; weight : 8.0
data : e; weight : 8.0
data : a; weight : 9.0
data : null; weight : 13.0
data : c; weight : 3.0
data : b; weight : 5.0
data : f; weight : 6.0

---

附錄：java.util.Queue用法

隊列是一種特殊的線性表，它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。隊列中沒有元素時，稱為空隊列。

在隊列這種數據結構中，最先插入的元素將是最先被刪除的元素；反之最后插入的元素將是最后被刪除的元素，因此隊列又稱為“先進先出”（FIFO—first in first out）的線性表。

在java5中新增加了java.util.Queue接口，用以支持隊列的常見操作。該接口擴展了java.util.Collection接口。

Queue使用時要盡量避免Collection的add()和remove()方法，而是要使用offer()來加入元素，使用poll()來獲取并移出元素。它們的優點是通過返回a.u值可以判斷成功與否，add()和remove()方法在失敗的時候會拋出異常。 如果要使用前端而不移出該元素，使用element()或者peek()方法。

值得注意的是LinkedList類實現了Queue接口，因此我們可以把LinkedList當成Queue來用。

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的【大话数据结构算法】哈夫曼树的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。