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

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

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

3、三從離散的節(jié)點(diǎn)中去除剛剛使用的兩個(gè)節(jié)點(diǎn)第四重復(fù)第二和第三步驟，直到所有離散節(jié)點(diǎn)剔除完畢。哈夫曼樹(shù)就構(gòu)建完成代碼以及測(cè)試程序如下package dateStructer.tree.huffmanTree;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.Queue;/* * 哈夫曼樹(shù) * * author liuyan */public class HuffmanTree /* * 節(jié)點(diǎn)實(shí)體 */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)建哈夫曼樹(shù) * * 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é)點(diǎn), 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)清揚(yá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