一、哈夫曼树的定义：
哈夫曼树：又称最优二叉树，是一种带权路径最短的树。
树的路径长度：从树根到树中每一个节点的路径长度之和。
结点之间的路径长度：从一个结点到另一个结点之间的分支数目。
结点的带权路径长度：从该结点到树根之间的路径长度与节点上权的乘积。
树的带权路径长度：Weighted Path Length of Tree，简称为WPL,树中所有叶子结点的带权路径长度之和，记作：
WPL最小的二叉树就称作最有二叉树或哈夫曼树。
二、构造哈夫曼树：
1、给出n个带有权值的结点，组成一个结点集合M；
2、从集合M中选出权值最小的两个结点A,B,权值分别为，构造一棵二叉树T，T的根结点C权值为 
；
3、删除结点A、B，将结点C加入到集合M中；
4、重复步骤2和3，直至M中只剩下一个结点为止。
三、哈弗曼编码
从哈夫曼树根结点开始，对左子树分配“0”，右子树分配“1”，直至叶子结点，然后，将树根沿每条路径到达叶子结点的代码排列起来，便可以得到哈夫曼编码。
四、练习：
将一个字符串转换成一棵HFM树，并打印出每个字符的HFM编码，将HFM树图形化。
1、先写一个节点类Node,里面存放字符串（一个字符组成的字符串）、字符串出现的次数、节点所在位置的横坐标、节点所在位置的纵坐标、左子结点、右子结点、父节点。
/**
* HFM树的节点类
* @author zr
*
*/
public class Node {
private String s;//字符串
private int count;//字符串s出现的次数
private int x;//节点所在位置的横坐标
private int y;//节点所在位置的纵坐标
private Node left;//左子节点
private Node right;//右子结点
private Node parent;//父节点
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public int getCount() {
return count;
}
public void setCount(int count) {
this.count = count;
}
public String getS() {
return s;
}
public void setS(String s) {
this.s = s;
}
public int getX() {
return x;
}
public void setX(int x) {
this.x = x;
}
public int getY() {
return y;
}
public void setY(int y) {
this.y = y;
}
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;
}
}
2、写一个HFM类：
（1）先把字符串转换成节点数组，其中需要求出某个字符在字符串中出现的次数，然后，我们需要获得一个无重复字符的字符串noRepeat,最后，将每个字符和它出现的次数放到一个Node对象中，最后，转换成一个节点数组。
/**
* 字符串c在字符串s中出现的次数
* @param c 需要统计的对象字符串c
* @param s 字符串c所在的字符串
* @return 返回字符串c在字符串s中出现的次数
*/
public int getCount(String c,String s){
int count=0;
for(int i=0;i<s.length();i++){
String ch=""+s.charAt(i);
if(c.equals(ch)){
count++;
}
}
return count;
}
/**
* 把字符串转换成节点数组
* @return 返回节点数组
*/
public Node [] toNodeArray(){
String noRepeat="";
for(int i=0;i<s.length();i++){
String c=""+s.charAt(i);
if(noRepeat.indexOf(c)==-1){
noRepeat+=c;
}
}
Node [] nodes=new Node[noRepeat.length()];
for(int i=0;i<noRepeat.length();i++){
Node node=new Node();
String ch=""+noRepeat.charAt(i);
node.setS(ch);
int count=this.getCount(ch, s);
node.setCount(count);
nodes[i]=node;
}
return nodes;
}
（2）将节点按字符出现次数的大小排序，这里采用冒泡排序；
注意，当nodes[i].getCount()>nodes[j].getCount())时，要交换的是节点对象，而不是count.
/**
* 把节点数组排序
* @param nodes 节点数组
*/
public void sort(Node [] nodes){
for(int i=0;i<nodes.length;i++){
for(int j=i+1;j<nodes.length;j++){
if(nodes[i].getCount()>nodes[j].getCount()){
Node temp=nodes[i];
nodes[i]=nodes[j];
nodes[j]=temp;
}
}
}
}
（3）创建HFM树,完成（1）（2）步之后，这里我们采用循环，循环条件：节点数组长度>1；
a、从排好序的Node节点中选出两个count值最小的节点n1,n2，
b、再实例化一个Node对象，其count值为n1,n2的count值之和，
c、新建一个节点数组nodes2，长度为原节点数组nodes长度-1，把n3放在nodes[0]位置，原节点数组nodes中除n1,n2外的剩余节点的放到nodes2中
d、把nodes指向nodes2
/**
* 创建HFM树
* @return 返回根节点
*/
public Node createHFM(){
Node [] nodes=this.toNodeArray();
while(nodes.length>1){
this.sort(nodes);
Node n1=nodes[0];
Node n2=nodes[1];
Node n3=new Node();
n3.setCount(n1.getCount()+n2.getCount());
n3.setLeft(n1);
n3.setRight(n2);
n1.setParent(n3);
n2.setParent(n3);
Node [] nodes2=new Node[nodes.length-1];
nodes2[0]=n3;
for(int i=0;i<nodes.length-2;i++){
nodes2[i+1]=nodes[i+2];
}
nodes=nodes2;
}
return nodes[0];
}
(4)打印HFM编码：当遇到叶子节点是开始打印；当遇到的不是叶子节点，则采用递归，则可得到HFM编码。
/**
*
* 打印HFM编码
* @param node 根节点
* @param code 上一个节点的编码
* @return 返回根节点
*/
private Node print(Node node,String code){
if(node.getLeft()==null&&node.getRight()==null){
System.out.println("字符"+node.getS()+"出现的次数为："+node.getCount()+"，哈夫曼编码为："+code);
if(node.getX()!=0&&node.getY()!=0){
g.setColor(Color.white);
g.fillRect(node.getX(), node.getY()+65, 50, 30);
g.setColor(Color.black);
g.drawString(code, node.getX()+25, node.getY()+80);
}
}else{
if(node.getLeft()!=null){
print(node.getLeft(),code+"0");
}
if(node.getRight()!=null){
print(node.getRight(),code+"1");
}
}
return node;
}
/**
* 打印HFM编码
*/
public void print(){
Node node=this.createHFM();
this.print(node, "");
}
（5）画出HFM树：当遇到的节点没有父节点，即该节点节为根节点时，画出根节点，给出权值，接着，可以画出该父节点的左右子节点及其权值；否则，遇到左子点不为空时，可以通过递归，画出所有左子结点，遇到右子结点不为空时，也通过递归，画出所有右子结点。最后，遇到叶子结点时，打印出字符及其HFM编码。
/**
* 画出HFM树
*/
public void draw(){
Node node=this.createHFM();
this.drawHFM(node);
}
/**
* 画出HFM树并打印出每个叶子结点的HFM编码
* @param node 根节点
*/
private void drawHFM(Node node){
if(node.getParent()==null){
node.setX(300);
node.setY(100);
x1=node.getX();
y1=node.getY();
String sc1=Integer.toString(node.getCount());
g.setColor(Color.yellow);
g.fillOval(x1, y1, 50, 50);
g.setColor(Color.black);
g.drawString(sc1, x1+25, y1+25);
if(node.getLeft()!=null){
Node left=node.getLeft();
left.setX(x1-100);
left.setY(y1+100);
int x2=left.getX();
int y2=left.getY();
String sc2=Integer.toString(left.getCount());
g.setColor(Color.yellow);
g.fillOval(x2, y2, 50, 50);
g.setColor(Color.black);
g.drawString(sc2, x2+25, y2+25);
g.drawLine(x2+25, y2, x1+25, y1+50);
g.drawString("0", (x1+x2+50)/2-10, (y1+y2+50)/2);
x4=x1;
y4=y1;
drawHFM(left);
}
if(node.getRight()!=null){
Node right=node.getRight();
right.setX(x4+100);
right.setY(y4+100);
int x3=right.getX();
int y3=right.getY();
String sc3=Integer.toString(right.getCount());
g.setColor(Color.yellow);
g.fillOval(x3, y3, 50, 50);
g.setColor(Color.black);
g.drawString(sc3, x3+25, y3+25);
g.drawLine(x3+25, y3, x4+25, y4+50);
g.drawString("1", (x4+x3+50)/2+10, (y4+y3+50)/2);
drawHFM(right);
}
}else{
if(node.getLeft()!=null){
x1=node.getX();
y1=node.getY();
Node left=node.getLeft();
left.setX(x1-30);
left.setY(y1+100);
int x2=left.getX();
int y2=left.getY();
String sc2=Integer.toString(left.getCount());
g.setColor(Color.yellow);
g.fillOval(x2, y2, 50, 50);
g.setColor(Color.black);
g.drawString(sc2, x2+25, y2+25);
g.drawLine(x2+25, y2, x1+25, y1+50);
g.drawString("0", (x1+x2+50)/2-10, (y1+y2+50)/2);
drawHFM(left);
}
if(node.getRight()!=null){
x1=node.getX();
y1=node.getY();
Node right=node.getRight();
right.setX(x1+30);
right.setY(y1+100);
int x3=right.getX();
int y3=right.getY();
String sc3=Integer.toString(right.getCount());
g.setColor(Color.yellow);
g.fillOval(x3, y3, 50, 50);
g.setColor(Color.black);
g.drawString(sc3, x3+25, y3+25);
g.drawLine(x3+25, y3, x1+25, y1+50);
g.drawString("1", (x1+x3+50)/2+10, (y1+y3+50)/2);
drawHFM(right);
}
if(node.getLeft()==null&&node.getRight()==null){
String str=node.getS();
g.drawString(str, node.getX()+25, node.getY()+60);
}
}
//打印HFM编码
this.print(node, "");
}
任意给出一个字符串，画出的HFM编码如下：
相关推荐
从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入...
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int num)//w存放n个字符的权值（均>0），构造哈夫曼树HT，并求出n个字符的哈弗曼编码HC { int i,m,c,s1,s2,start,f; HuffmanTree p; char* cd; if...
1）哈夫曼树类型、select()函数（求两最小权值结点）、哈夫曼树构建、求编码函数、字符串输入处理函数等的声明放在huffman.h文件； 2）select()函数、哈夫曼树构建、求编码函数的实现可放在huffman.c文件； 3）输入...
哈夫曼树与哈夫曼编码 建立哈夫曼树并计算哈夫曼编码
c++ 源代码 哈夫曼树 哈夫曼编码 部分代码如下： #include"Huffman.h" #include"hfmTree.h" #include using namespace std; int main() { cout~~~~~~~~~~~~~welcome to Huffman encodrding&decoding system ~~~~~~...
哈夫曼树构造 输出
如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树如何根据概率求哈夫曼树
用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树 用C语言实现三叉哈夫曼树
利用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并将它存于文件hfmTree中； 2） 编码（EnCoding）。利用已建好的哈夫曼树（若不在内存中，则从文件hfmTree中读入），对以下报文进行编码，结果存入文件...
这是我做的一个基于哈夫曼树思想的压缩算法程序源码，希望大家指正
C语言实现的哈夫曼树
（1） 读入一个 ASCII 文件，统计文档中字符出现的频度，构造哈夫曼树； （2） 在构造好的哈夫曼树中对每个字符进行 Huffman 编码； （3） 要求打印出原始数据、每个字符对应的Huffman 编码和总编码长度。
首先根据给定的n个字符的权值构造哈夫曼树。通过遍历此二叉树完成各字符的哈夫曼编码，另输入一组‘0’、‘1’代码构成的报文将其翻译成对应的字符信息。
一、课程设计题目：哈夫曼树应用 二、课程设计要求： 1) 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上； 2) 利用...
实现哈夫曼算法的前提是要考虑用什么样的存储结构来存储一棵哈夫曼树。在哈夫曼树中，没有度为1的结点，结点总数是n0+n2（其中n0表示二叉树中度为0的结点数，n2表示度为2的结点数），而由二叉树的性质知道n0=n2+1，...
构建哈夫曼树，对其进行编码，实现译码功能，数据结构的实验报告。。
利用已建好的哈夫曼树(如不在内存，则从文件 hfmtree 中读入)，对文件 tobetrans 中的正文进行编码，然后将结果存入文件 codefile 中。 (3)D:解码(Decoding)。利用已建好的哈夫曼树将文件 codefile 中的代码进行...
编码：利用建立好的哈夫曼树对源文件进行编码，实现文件压缩，然后将结果以文件形式保存，如编码文件codefile。 d．译码：利用建立好的哈夫曼树对codefile中的代码进行译码。结果存入译码文件decofile中。 e．输出：...
数据结构课程设计：哈夫曼树及其应用 文档 ++代码 构建哈夫曼树，编码，译码
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成 本。...将已在内存中的哈夫曼树以直观的方式(树或凹入表形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。