当前位置 博文首页 > Yngz_Miao的博客：【数据结构】二叉树（哈夫曼树）的JAVA代码实
二叉树的经典应用就是哈夫曼（Haffman）树，也称最优二叉树，是指对于一组带有确定权值的叶结点、构造的具有最小带权路径长度的二叉树。
二叉树的路径长度是指由根结点到所有的叶结点的路径长度之和。如果二叉树的叶结点都带有一定的权值，则可以将这个概念加以推广。设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应的叶结点权值的乘积之和叫做二叉树的带权路径长度。
我们可以知道：有相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度。根据哈夫曼树的定义，一棵二叉树要想它的带权路径长度最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。
哈夫曼根据这个特点提出了一种方法。这种方法的基本思想是：
?
在数据传输中，需要将传输的文字换成二进制的字符，用0和1的不同排列来表示字符。然而，在传送报文的时候总希望传输报文的总长度尽可能短。在实际的应用中，各个字符的出现频率或使用次数是不同的，在设计编码时，应使用频率高的用短码，使用频率低的用长码。
对于数据通信中的报文编码问题，我们一般采用以下三步来解决：
注意：在求文字符编码的时候，假设到每棵左子树的根结点的边为0，到右子树的结点的边为1。
?
由哈夫曼树的构造思想可知，可以用一个数组存放原来的n个叶子结点和构造过程中临时生成的结点，数组大小为2n-1。所以，哈夫曼树类中有两个成员字段：data数组用于存放结点集合；leafNum表示哈夫曼树叶子结点的数目。而哈夫曼树结点一共有5个域，各个域的名称及作用见下表：
| 哈夫曼树结点域名称 | 哈夫曼树结点域作用 |
| weight | 该结点的权值 |
| data | 该结点的信息 |
| lchild | 该结点的左孩子结点在数组中的序号 |
| rchild | 该结点的右孩子结点在数组中的序号 |
| parent | 该结点的父结点在数组中的序号，同时用于判断该结点是否已 经加入哈夫曼树中（默认为-1） |
根据各个域的名称，定义哈夫曼树的结点类：
public class HNode {
private int weight; //结点权值
private int lchild; //左孩子结点
private int rchild; //右孩子结点
private int parent; //父结点
private String name; //结点数据,存放字符名称
private String code;//存放叶子结点的字符编码
//构造器
public HNode(String name, int w){
this.weight = w;
this.name = name;
this.lchild = -1;
this.rchild = -1;
this.parent = -1;
this.code = "";
}
public HNode(){
this(null,0);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getLchild() {
return lchild;
}
public void setLchild(int lchild) {
this.lchild = lchild;
}
public int getRchild() {
return rchild;
}
public void setRchild(int rchild) {
this.rchild = rchild;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
}根据哈夫曼树的要求，我们需要实现以下功能：
使用Java构造的哈夫曼树，代码实现如下：
public class HuffmanTree {
private HNode[] data; // 结点数组
private int leafNum; // 叶子结点数目
// 构造哈夫曼树
public void create() {
Scanner sc = new Scanner(System.in);
System.out.println("请输入要传输的报文:");
String str = sc.nextLine().toLowerCase();
str = str.replace(" ", ""); //去掉空格
int[] c = new int[26];
for (int i = 0; i < str.length(); i++) { // 统计各字符出现的频率
c[str.charAt(i) - 'a']++;
}
int cnt = 0;
for (int i = 0; i < 26; i++) { // 统计报文中字符的数量
if (c[i] > 0)
cnt++;
}
this.leafNum = cnt;
data = new HNode[this.leafNum * 2 - 1];
for (int i = 0; i < 2 * leafNum - 1; i++)
data[i] = new HNode();
cnt = 0;
for (int i = 0; i < 26; i++) { // 用字符创建叶子结点
if (c[i] > 0) {
data[cnt].setName((char) (i + 'a') + "");
data[cnt++].setWeight(c[i]);
}
}
int m1, m2, x1, x2;
// 处理n个叶子结点，建立哈夫曼树
for (int i = 0; i < this.leafNum - 1; ++i) {
m1 = m2 = Integer.MAX_VALUE; // m1：最小权值,m2:次小权值
x1 = x2 = 0; // x1：权值最小位置,x2:权值次小位置
// 在全部结点中找权值最小的两个结点
for (int j = 0; j < this.leafNum + i; ++j) {
if ((data[j].getWeight() < m1) && (data[j].getParent() == -1)) {
m2 = m1;
x2 = x1;
m1 = data[j].getWeight();
x1 = j;
} else if ((data[j].getWeight() < m2)
&& (data[j].getParent() == -1)) {
m2 = data[j].getWeight();
x2 = j;
}
}
// 用两个权值最小点构造一个新的中间结点
data[this.leafNum + i].setWeight(data[x1].getWeight()
+ data[x2].getWeight());
data[this.leafNum + i].setLchild(x1);
data[this.leafNum + i].setRchild(x2);
// 修改权值最小的两个结点的父结点指向
data[x1].setParent(this.leafNum + i);
data[x2].setParent(this.leafNum + i);
}
}
//输出哈夫曼树结构
public void print() {
System.out.println("位置\t字符\t权值\t父结点\t左孩子结点\t右孩子结点");
for (int i = 0; i < 2 * leafNum - 1; i++) {
System.out.printf("%d\t%s\t%d\t%d\t%d\t%d\r\n", i,
data[i].getName(), data[i].getWeight(),
data[i].getParent(), data[i].getLchild(),
data[i].getRchild());
}
}
// 前序遍历,输出所有叶子结点的编码,并计算总的报文编码长度
private int preorder(HNode root,String code) {
int sum = 0;
if (root != null) {
root.setCode(code);
if(isLeaf(root)){ //叶子结点，输出编码，并计算长度
System.out.println(root.getName() + ":" + root.getCode());
return root.getWeight()*root.getCode().length();
}
if(root.getLchild()!=-1){
//左子树，编码为0，并统计左子树叶子结点的编码长度
sum +=preorder(data[root.getLchild()],code+"0");
}
if(root.getRchild()!=-1){
//右子树，编码为1，并统计右子树所有叶子结点的编码长度
sum +=preorder(data[root.getRchild()],code+"1");
}
}
return sum;
}
//层序遍历，求报文传输的总长度
private void levelOrder(){
//根结点的位置
int root = 2*leafNum-2;
// 根结点为空
if (root == -1) {
return;
}
// 设置一个队列保存层序遍历的结点
Queue<HNode> q = new LinkedList<HNode>();
// 根结点入队
q.add(data[root]);
int sum = 0;
String code = "";
// 队列非空，结点没有处理完
while (!q.isEmpty()) {
// 结点出队
HNode tmp = q.poll();
code = tmp.getCode();
// 如果是叶子结点，则计算编码长度
if(isLeaf(tmp)){
sum +=tmp.getWeight()*tmp.getCode().length();
}
// 将当前结点的左孩子结点入队
if (tmp.getLchild() != -1) {
q.add(data[tmp.getLchild()]);
data[tmp.getLchild()].setCode(code+"0");
}
if (tmp.getRchild() != -1) {
// 将当前结点的右孩子结点入队
q.add(data[tmp.getRchild()]);
data[tmp.getRchild()].setCode(code+"1");
}
}
System.out.println("总的报文长度为："+sum);
}
//采用层序遍历，进行报文解码
public String decodes(String codes){
//根结点的位置
int root = 2*leafNum-2;
// 根结点为空
if (root == -1) {
return "";
}
// 设置一个队列保存层序遍历的结点
Queue<HNode> q = new LinkedList<HNode>();
// 根结点入队
q.add(data[root]);
int i = 0;
String str = "";
// 队列非空，结点没有处理完
while (!q.isEmpty()) {
// 结点出队
HNode tmp = q.poll();
if(!codes.startsWith(tmp.getCode())) continue;
// 如果是叶子结点，则计算编码长度
if(isLeaf(tmp)){
str = str + tmp.getName();
codes = codes.substring(tmp.getCode().length());
if(codes.length()>0){ //如果存在多个报文字符，则继续重新解码
while(!q.isEmpty()) q.poll();
q.add(data[root]);
continue;
}
}
// 将当前结点的左孩子结点入队
if (tmp.getLchild() != -1) {
q.add(data[tmp.getLchild()]);
}
if (tmp.getRchild() != -1) {
// 将当前结点的右孩子结点入队
q.add(data[tmp.getRchild()]);
}
}
return str;
}
// 层次遍历
public void traverse() {
//根结点的位置
int root = 2*leafNum-2;
// 根结点为空
if (root == -1) {
return;
}
int sum = preorder(data[root],"");
System.out.println("所有报文长度为（位）："+sum);
}
// 判断是否是叶子结点
public boolean isLeaf(HNode p) {
return ((p != null) && (p.getLchild() == -1) && (p.getRchild() == -1));
}
}public class TestHuffmanTree {
// 测试哈夫曼树
public static void main(String[] args) {
HuffmanTree ht = new HuffmanTree();
ht.create(); //创建哈夫曼树
//ht.print(); //输出哈夫曼树结构
ht.traverse(); //输出所有字符编码
String op = "";
do{
System.out.println("请输入一个报文编码进行解码:");
Scanner sc = new Scanner(System.in);
String codes = sc.nextLine();
String decodes = ht.decodes(codes); //报文解码
if(decodes.length()==0){
System.out.println("解码出错！");
}else{
System.out.println("对应的报文为："+decodes);
}
System.out.println("按X键退出，其他键继续");
op = sc.nextLine();
}while(!op.toLowerCase().equals("x"));
System.out.println("程序退出");
}
}?
哈夫曼树的实现，用现在的这个方法看起来还是比较复杂的，但如果使用一些更加好的数据结构会简化很多。比如说一些有序数据结构（优先队列）等。这会在后面的文章中说到。
?
附：评论区的一个疑问，因为回复的代码块格式有问题，就在正文里写了：
疑问：实现一个哈夫曼树的应用程序，可以按照以下每个字符的出现频率（权值）｛空格和26个英文字母出现频率分别为：186，64，13，22，32，103，21，15，47，57，1，5，32，20，57，63，15，1，48，51，80，23，8，18，1，16，1｝创建一棵哈夫曼树（要求左孩子的权值小于等于右孩子的权值）；并输出所有报文字符的编码，并将“THIS PROGRAM IS MY FAVORITE”编码，统计总的报文传输长度。在此基础上，对用户输入的01串，回答其代表的字符串（即进行报文解码），若解码失败则回复“解码失败”。
解答：本质上没有什么区别。首先是哈夫曼树的结点类，没有任何变化：
package com.southeast.data.structure.huffmantree;
public class HNode {
private int weight;
private int lchild;
private int rchild;
private int parent;
private String name; //结点代表的字符
private String code; //结点字符的编码
public HNode(String name,int w){
this.weight=w;
this.name=name;
this.lchild=-1;
this.rchild=-1;
this.parent=-1;
this.code="";
}
public HNode(){
this(null,0);
}
public int getWeight() {
return weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
public int getLchild() {
return lchild;
}
public void setLchild(int lchild) {
this.lchild = lchild;
}
public int getRchild() {
return rchild;
}
public void setRchild(int rchild) {
this.rchild = rchild;
}
public int getParent() {
return parent;
}
public void setParent(int parent) {
this.parent = parent;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getCode() {
return code;
}
public void setCode(String code) {
this.code = code;
}
}下面是主要的哈夫曼树的代码：
package com.southeast.data.structure.huffmantree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
public class HuffmanTree {
private HNode[] data; //保存哈夫曼树结点
private int leafNum; //保存哈夫曼树的叶子结点数目
//整个哈夫曼树的结点数目=哈夫曼树叶子结点数目*2-1
public boolean isLeaf(HNode p){
return (p!=null)&&(p.getLchild()==-1)&&(p.getRchild()==-1);
}
public void create(){
Scanner sc=new Scanner(System.in);
System.out.println("请输入每个字符出现频率：");
int[] c=new int[27]; //保存27个字符的出现次数
for(int i=0;i<27;i++){
c[i]=sc.nextInt();
}
int cnt=0; //统计报文中字符的种类
for(int i=0;i<27;i++){
if(c[i]>0)
cnt++;
}
this.leafNum=cnt;
data=new HNode[this.leafNum*2-1]; //创建哈夫曼树结点
for(int i=0;i<2*this.leafNum-1;i++)
data[i]=new HNode();
//为哈夫曼树结点赋值
data[0].setName(" ");
data[0].setWeight(c[0]);
for(int i=1;i<this.leafNum;++i){
if(c[i]>0){
data[i].setName((char)(i-1+'A')+"");
data[i].setWeight(c[i]);
}
}
int m1,m2,x1,x2;
for(int i=0;i<this.leafNum-1;++i){
m1=m2=Integer.MAX_VALUE; //m1最小权重，m2次小权重
x1=x2=0; //x1权重最小位置，x2权重次小位置
for(int j=0;j<this.leafNum+i;++j){ //找出最小的两个权重和它的位置，判断权重和它的父母
if((data[j].getWeight()<m1)&&(data[j].getParent()==-1)){
m2=m1;
x2=x1;
m1=data[j].getWeight();
x1=j;
}else if((data[j].getWeight()<m2)&&(data[j].getParent()==-1)){
m2=data[j].getWeight();
x2=j;
}
}
//用权重最小的两个点构造一个新的中间节点
data[this.leafNum+i].setWeight(data[x1].getWeight()+data[x2].getWeight());
data[this.leafNum+i].setLchild(x1);
data[this.leafNum+i].setRchild(x2);
data[x1].setParent(this.leafNum+i);
data[x2].setParent(this.leafNum+i);
}
}
public void print(){
System.out.println("位置\t字符\t权值\t父节点位置\t左孩子点位置\t右孩子点位置");
for(int i=0;i<2*leafNum-1;i++){
System.out.printf("%d\t%s\t%d\t%d\t%d\t%d\r\n",i,data[i].getName(),
data[i].getWeight(),data[i].getParent(),data[i].getLchild(),data[i].getRchild());
}
}
//前序遍历，求所有报文字符编码
public void traverse(){
int root=2*leafNum-2;
if(root==-1){
return;
}
System.out.println("所有报文字符的编码为：");
preOrder(data[root],"");
}
public void preOrder(HNode p,String code){
if(p!=null){
p.setCode(code);
if(isLeaf(p)){
System.out.println(p.getName()+":"+p.getCode());
}
if(p.getLchild()!=-1){
preOrder(data[p.getLchild()],code+"0");
}
if(p.getRchild()!=-1){
preOrder(data[p.getRchild()],code+"1");
}
}
}
//层次遍历，进行报文解码
public String decodes(String codes){
int root=2*leafNum-2; //root的索引
if(root==-1){
return "";
}
Queue<HNode> q=new LinkedList<HNode>();
q.add(data[root]);
String str="";
boolean flag=false; //标志位，排除末尾无法编码的情况
while(!q.isEmpty()){
HNode tmp = q.poll();
if(!codes.startsWith(tmp.getCode())) //层次遍历判断出codes的开头密码
continue;
if(isLeaf(tmp)){ //判断是否为叶子结点，如果不是，则继续循环
flag=true;
str=str+tmp.getName();
codes=codes.substring(tmp.getCode().length()); //获得开头密码解析后剩下的密码
if(codes.length()>0){
flag=false;
while(!q.isEmpty()) //循环清空q队列的内容
q.poll();
q.add(data[root]); //在队列中在此添加头内容
continue;
}
}
if(tmp.getLchild()!=-1){
q.add(data[tmp.getLchild()]);
}
if(tmp.getRchild()!=-1){
q.add(data[tmp.getRchild()]);
}
}
if(!flag)
str="";
return str;
}
//前序遍历，计算报文传输总长度
public int encodes(String codes){
int[] num=new int[27]; //统计报文中字符出现的次数
for(int i=0;i<27;i++){
num[i]=0;
}
for(int i=0;i<codes.length();i++){
if(codes.charAt(i)==' '){
++num[0];
}else if(codes.charAt(i)>='A'&&codes.charAt(i)<='Z'){
++num[codes.charAt(i)-'A'+1];
}else //不是正确的报文字符
return 0;
}
int root=2*leafNum-2;
if(root==-1){
return 0;
}
int sum=preOrder(data[root],num);
return sum;
}
public int preOrder(HNode p,int[] num){
int sum=0;
if(p!=null){
if(isLeaf(p)){
int i;
if(p.getName()==" "){
i=0;
}else{
i=p.getName().charAt(0)-'A'+1;
}
return num[i]*p.getCode().length();
}
if(p.getLchild()!=-1){
sum+=preOrder(data[p.getLchild()],num);
}
if(p.getRchild()!=-1){
sum+=preOrder(data[p.getRchild()],num);
}
}
return sum;
}
public static void main(String[] args){
HuffmanTree ht=new HuffmanTree();
ht.create();
ht.print();
ht.traverse();
System.out.println("请输入一个字符报文进行编码：");
Scanner sc=new Scanner(System.in);
String codes=sc.nextLine();
int encodes=ht.encodes(codes);
if(encodes==0){
System.out.println("编码失败！");
}else{
System.out.println("总的报文传输长度为："+encodes);
}
System.out.println("请输入一个报文编码进行解码：");
sc=new Scanner(System.in);
codes=sc.nextLine();
String decodes=ht.decodes(codes);
if(decodes.length()==0){
System.out.println("解码失败！");
}else{
System.out.println("对应报文为："+decodes);
}
System.out.println("程序结束！");
}
}
最终运行的结果为：
请输入每个字符出现频率：
186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1
位置 字符 权值 父节点位置 左孩子点位置 右孩子点位置
0 186 49 -1 -1
1 A 64 44 -1 -1
2 B 13 32 -1 -1
3 C 22 36 -1 -1
4 D 32 38 -1 -1
5 E 103 47 -1 -1
6 F 21 35 -1 -1
7 G 15 32 -1 -1
8 H 47 40 -1 -1
9 I 57 42 -1 -1
10 J 1 27 -1 -1
11 K 5 30 -1 -1
12 L 32 38 -1 -1
13 M 20 35 -1 -1
14 N 57 42 -1 -1
15 O 63 43 -1 -1
16 P 15 33 -1 -1
17 Q 1 27 -1 -1
18 R 48 41 -1 -1
19 S 51 41 -1 -1
20 T 80 45 -1 -1
21 U 23 36 -1 -1
22 V 8 31 -1 -1
23 W 18 34 -1 -1
24 X 1 28 -1 -1
25 Y 16 33 -1 -1
26 Z 1 28 -1 -1
27 null 2 29 10 17
28 null 2 29 24 26
29 null 4 30 27 28
30 null 9 31 29 11
31 null 17 34 22 30
32 null 28 37 2 7
33 null 31 37 16 25
34 null 35 39 31 23
35 null 41 39 13 6
36 null 45 40 3 21
37 null 59 43 32 33
38 null 64 44 4 12
39 null 76 45 34 35
40 null 92 46 36 8
41 null 99 46 18 19
42 null 114 47 9 14
43 null 122 48 37 15
44 null 128 48 1 38
45 null 156 49 39 20
46 null 191 50 40 41
47 null 217 50 5 42
48 null 250 51 43 44
49 null 342 51 45 0
50 null 408 52 46 47
51 null 592 52 48 49
52 null 1000 -1 50 51
所有报文字符的编码为：
C:00000
U:00001
H:0001
R:0010
S:0011
E:010
I:0110
N:0111
B:100000
G:100001
P:100010
Y:100011
O:1001
A:1010
D:10110
L:10111
V:1100000
J:1100001000
Q:1100001001
X:1100001010
Z:1100001011
K:11000011
W:110001
M:110010
F:110011
T:1101
:111
请输入一个字符报文进行编码：
THIS PROGRAM IS MY FAVORITE
总的报文传输长度为：118
请输入一个报文编码进行解码：
01
解码失败！
程序结束！
?
cs