Java基礎(chǔ)復(fù)習(xí)筆記09數(shù)據(jù)結(jié)構(gòu)哈夫曼樹

1、Java基礎(chǔ)復(fù)習(xí)筆記09數(shù)據(jù)結(jié)構(gòu)-哈夫曼樹劉巖哈夫曼樹哈夫曼樹也稱作最優(yōu)二叉樹，當(dāng)樹中的節(jié)點帶了權(quán)重信息了，帶權(quán)路徑長度最小的二叉樹叫做最優(yōu)二叉樹。帶權(quán)路徑長度=sum（權(quán)重*度）。sum代表每個節(jié)點的之和。加入有如下帶權(quán)重的節(jié)點。權(quán)重分別是1、5、8、4。那么關(guān)于這些零散的節(jié)點，最優(yōu)二叉樹該如何構(gòu)建呢？首先先將離散節(jié)點從小到大升序排序第二從離散節(jié)點中在挑選排序前兩個節(jié)點當(dāng)做一個新的父節(jié)點的兩個子節(jié)點第三從離散的節(jié)點中去除剛剛使用的兩個節(jié)點第四重復(fù)第二和第三步驟，直到所有離散節(jié)點剔除完畢。哈夫曼樹就構(gòu)建完成用圖形演示過程如下可以看出所有的葉子節(jié)點就是之前的離散節(jié)點，如果在采用廣度遍歷法遍歷此樹

2、。那么遍歷的過程實際上就是最短遍歷路徑的遍歷過程哈夫曼樹的使用場景其實哈夫曼樹使用場景還真不少，例如apache負(fù)載均衡的按權(quán)重請求策略的底層算法、咱們生活中的路由器的路由算法、利用哈夫曼樹實現(xiàn)漢字點陣字形的壓縮存儲()、快速檢索信息等等底層優(yōu)化算法，其實核心就是因為目標(biāo)帶有權(quán)重、長度遠(yuǎn)近這類信息才能構(gòu)建哈夫曼樹模型。實現(xiàn)哈夫曼樹要想實現(xiàn)哈夫曼樹其實就是將一堆零散的節(jié)點信息構(gòu)建成一顆最優(yōu)二叉樹，之后再按廣度優(yōu)先遍歷它。實現(xiàn)哈夫曼樹其實就是構(gòu)建哈夫曼樹的過程，原理其實上面已經(jīng)說了，這里再重復(fù)一下。首先先將離散節(jié)點從小到大升序排序第二從離散節(jié)點中在挑選排序前兩個節(jié)點當(dāng)做一個新的父節(jié)點的兩個子節(jié)點第

3、三從離散的節(jié)點中去除剛剛使用的兩個節(jié)點第四重復(fù)第二和第三步驟，直到所有離散節(jié)點剔除完畢。哈夫曼樹就構(gòu)建完成代碼以及測試程序如下package dateStructer.tree.huffmanTree;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;/* * 哈夫曼樹 * * author liuyan */public class HuffmanTree /* * 節(jié)點實體 */public static class Node / 數(shù)據(jù)T d

4、ata;/ 權(quán)重int power;Node leftNode;Node rightNode;public Node(T data, int power) this.data = data;this.power = power;Overridepublic String toString() / TODO Auto-generated method stubreturn data: + data + power: + power + ;SuppressWarnings(unchecked)public boolean compareTo(Node node) if (this.power no

5、de.power) return true;return false;/* * 將集合將序排序 * * param * param * * param list */SuppressWarnings(unchecked)public static void sort(List list) for (int i = 0; i list.size() - 1; i+) for (int j = i + 1; j list.size(); j+) if (list.get(i).compareTo(list.get(j) / 交換數(shù)組中的元素位置Node node = list.get(i);lis

6、t.set(i, list.get(j);list.set(j, node);/* * 創(chuàng)建哈夫曼樹 * * param list * return */SuppressWarnings(unchecked)public static Node createHuffmanTree(List list) while (list.size() 1) sort(list);Node left = list.get(list.size() - 1);Node right = list.get(list.size() - 2);Node parent = new Node(父節(jié)點, left.power

7、 + right.power);parent.leftNode = left;parent.rightNode = right;list.remove(list.size() - 1);list.remove(list.size() - 1);list.add(parent);return list.get(0);SuppressWarnings(unchecked)public static List deepFirst(Node root) List list = new ArrayList();Queue queue = new ArrayDeque();queue.add(root);

8、while (!queue.isEmpty() list.add(queue.peek();Node twoLinkNode = queue.poll();if (twoLinkNode.leftNode != null) queue.add(twoLinkNode.leftNode);if (twoLinkNode.rightNode != null) queue.add(twoLinkNode.rightNode);return list;/* * param args */public static void main(String args) List list = new ArrayList();Node node1 = new Node(東方不敗, 8);Node node2 = new Node(風(fēng)清揚, 5);Node node3 = new Node(岳不群, 4);Node node4 = new Node(左冷禪, 1);list.add(node1);list.add(node2);list.add(node3);list.add(node4);Node root = createHuffmanTree(list);System.out.println(deepFirst