1. 引子
当前素质教育的背景下,小学的学科成绩都改为了优秀、良好、及格、不及格这样的模糊词语,而不再通报具体的分数。
用代码可以表示如下:
if( a < 60 )
System.out.print("不及格");
else if( a < 70 )
System.out.print("及格");
else if( a < 90 )
System.out.print("良好");
else
System.out.print("优秀");
粗略看这样做是没问题的,但是一张好的试卷大部分学生成绩集中在"良好",而上面的程序需要判断两次才能到"良好",输入量很大的时候,在算法效率上其实是有问题的。所以应该做如下改进(① -> ②):
2. 哈夫曼树定义和原理
我们先把上图简化成叶子结点带权的二叉树(注:树结点间的连线相关的数叫做权,Weight)。
① 结点的路径长度:从根结点到该结点的路径上的连接数。
②
树的路径长度:树中每个叶子结点的路径长度之和。
③
结点带权路径长度:结点的路径长度与结点权值的乘积。
④
树的带权路径长度:WPL(Weighted Path Length)是树中所有叶子结点的带权路径长度之和。
※WPL的值越小,说明构造出来的二叉树性能越优,这种最优二叉树又称为哈夫曼树。
3. 哈夫曼树的存储结构:
weight
|
data
|
leftChild
|
rightChild
|
哈夫曼树的结点存储结构为双亲孩子存储结构:
① weight: 结点的权值。
② data:结点的值。
③ leftChild:结点的左孩子。
④ rightChild:结点的右孩子。
4. 构造哈夫曼树:
对于已知的一组叶子的权值W 1 ,W 2...... ,W n
① 首先把 n 个叶子结点看做 n 棵树(仅有一个结点的二叉树),n棵树组成一个森林。
② 把森林中权值最小和次小的两棵树合并成一棵树(小的放左边,大的放右边),该树根结点的权值是两棵子树权值之和,这时森林中还有 n-1 棵树。
③ 重复第②步直到森林中只有一棵为止。此树就是哈夫曼树。
现给一组 (n=4) 具体的权值 2 、4 、5 、 8 ,下边是构造具体过程:
5. Java实现哈夫曼树
import java.util.*;
public class HuffmanTree {
/*
* 结点内部类
*/
public static class Node {
private String data; // 结点值
private int weight; // 权值
private Node leftChild; // 左孩子
private Node rightChild; // 右孩子
public Node(String data, int weight) {
this.data = data;
this.weight = weight;
}
public String toString() {
return "Node[data=" + data + ", weight=" + weight + "]";
}
}
/**
* 构造哈夫曼树
*
* @param nodes节点集合
* @return 构造出来的哈夫曼树的根节点
*/
private static Node buildHaffmanTree(List<Node> nodesList) {
while (nodesList.size() > 1) { // 只要nodes数组中还有2个以上的节点
quickSort(nodesList, 0, nodesList.size() - 1);
Node left = nodesList.get(nodesList.size() - 1); // 获取权值最小的两个节点
Node right = nodesList.get(nodesList.size() - 2);
Node parent = new Node(null, left.weight + right.weight); // 生成新节点,新节点的权值为两个子节点的权值之和
parent.leftChild = left; // 让新节点作为权值最小的两个节点的父节点
parent.rightChild = right;
nodesList.remove(nodesList.size() - 1); // 删除权值最小的两个节点
nodesList.remove(nodesList.size() - 1);
nodesList.add(parent); // 将新生成的父节点添加到集合中
}
return nodesList.get(0); // 返回nodes集合中唯一的节点,也就是根节点
}
/**
* 实现快速排序算法,用于对节点进行排序
*
* @param nodesList
* @param start
* @param end
*/
private static void quickSort(List<Node> nodesList, int start, int end) {
if (start < end) { // 需要排序
Node base = nodesList.get(start); // 以第一个元素作为分界值
int i = start; // i从左边搜索,搜索大于分界值的元素的索引
int j = end + 1; // j从右边开始搜索,搜索小于分界值的元素的索引
while (true) {
while (i < end && nodesList.get(++i).weight >= base.weight){ // 找到大于分界值的元素的索引,或i已经到了end处
;
}
while (j > start && nodesList.get(--j).weight <= base.weight){ // 找到小于分界值的元素的索引,或j已经到了start处
;
}
if (i < j) {
swap(nodesList, i, j);
} else {
break;
}
}
swap(nodesList, start, j);
quickSort(nodesList, start, j - 1); // 递归左子序列
quickSort(nodesList, j + 1, end); // 递归右边子序列
}
}
/**
* 将指定数组的i和j索引处的元素交换
*
* @param nodesList
* @param i
* @param j
*/
private static void swap(List<Node> nodesList, int i, int j) {
Node temp;
temp = nodesList.get(i);
nodesList.set(i, nodesList.get(j));
nodesList.set(j, temp);
}
/**
* 广度优先遍历
*
* @param root
* @return
*/
public static List<Node> breadthFirst(Node root) {
Queue<Node> queue = new ArrayDeque<Node>();
List<Node> list = new ArrayList<Node>();
if (root != null) {
queue.offer(root); // 将根元素入"队列"
}
while (!queue.isEmpty()) {
list.add(queue.peek()); // 将该队列的"队尾"的元素添加到List中
Node p = queue.poll();
if (p.leftChild != null) { // 如果左子节点不为null,将它加入"队列"
queue.offer(p.leftChild);
}
if (p.rightChild != null) { // 如果右子节点不为null,将它加入"队列"
queue.offer(p.rightChild);
}
}
return list;
}
/**
* 测试方法
*
* @param args
*/
public static void main(String[] args) {
List<Node> nodesList = new ArrayList<Node>();
nodesList.add(new Node("A", 2));
nodesList.add(new Node("B", 4));
nodesList.add(new Node("C", 5));
nodesList.add(new Node("D", 8));
Node root = HuffmanTree.buildHaffmanTree(nodesList);
System.out.println(breadthFirst(root));
}
}
分享到:
相关推荐
任务 :建立建立最优二叉树函数 要求:可以建立函数输入...在上交资料中请写明:存储结构、 基本算法(可以使用程序流程图) 、输入输出、源程序、测试数据和结果、算法的时间复杂度、另外可以提出算法的改进方法;
哈夫曼编码,最优二叉树的生成及各种算法遍历,非常有用哦,C语言版的哦
2. 实现哈夫曼树数据结构,使用哈夫曼树完成如下文档的编码与译码,假设该文档由5种符号字符(A、B、C、D、E)构成 ABACDEABBCEABAACCCDEACCBAABCCCA 3. 选做:实现二叉树的中序遍历线索化数据结构 4. 选做:使用...
定义:给定n个权值作为n个叶子结点,构造一棵二叉树,若树的带权路径长度达到最小,则这棵树被称为哈夫曼树。
1、训练学生灵活应用所学数据结构知识,独立完成问题分析,结合数据结构理论知识,编写程序求解指定问题。 2.初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能; 3.提高综合运用所学的...
适合非专业的学生使用。 本人是非计算机的学生,所以写的时候,可能不是很规矩 请您原谅! 平台:vc++6.0 操作系统 32位
数据结构完整实验报告 实验3:树和二叉树的应用-哈夫曼编码设计
哈夫曼二叉树编码译码器 里面有课程设计报告 课程是数据结构
用C语言写的数据结构课程设计 设计题目 哈夫曼编\译码器 设计要求: 1.初始化,键盘输入字符集大小n,n个字符和n个权植,建立哈夫曼树。 2.编码,利用建好的huffman树生成huffman编码; 3.输出编码; 4.译码功能; 5...
哈夫曼树的应用——数据结构课程设计
构建哈夫曼树,对其进行编码,实现译码功能,数据结构的实验报告。。
哈夫曼算法建立最优二叉树.doc
哈夫曼树 哈夫曼编码 最优二叉树 判定问题
数据结构-实验三-题目二:哈夫曼树.docx
数据结构实验报告 《五、最优二叉树应用之哈夫曼编译码》
头歌数据结构构建哈夫曼树及编码 第1关构建哈夫曼树 第2关根据哈夫曼树构建哈夫曼编码 通过哈夫曼树的构造,深刻理解二叉树的构造。 通过哈夫曼编/译码过程,深刻领会二叉树的基本操作和二叉树的应用,熟练掌握...
利用二叉树结构实现哈夫曼编/解码器。 基本要求: 1、初始化(Init):能够对输入的任意长度的字符串s进行统计,统计每个字符的频度,并建立哈夫曼树 2、建立编码表(CreateTable):利用已经建好的哈夫曼树进行编码...
数据结构课程设计,用C语言做的,有设计文档有程序关于哈哈夫曼树的应用
C语言实现的哈夫曼树