首页 > 代码库 > 闲来无事写写-Huffman树的生成过程
闲来无事写写-Huffman树的生成过程
前言:最近项目上一直没事干,感觉无聊到了极点,给自己找点事做,补一下大学没有完成的事情,写一个huffman算法Java版的,学校里面写过c语言的。
因为很久没搞数据结构和算法这方面了(现在搞Java web,真心感觉没什么挑战啊),代码写的一般,边听歌边写,3小时,不知道为什么现在效率这么低,写习惯了
xml配置,感觉纯写算法代码手生的紧,悲呼唉哉!
1、哈夫曼树:
给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree)
2、生成过程:
1. 在n个权值里面首先寻找最小的两个权值作为子节点,开始生成第一棵子树;
2.将新子树的父节点作为一个新的权值与剩余的权值继续做比较,选出最小的两个权值继续构造新子树;
3.依次进行,直到最后一棵子树生成;
4.这时候,最后一棵子树的根节点就是整个哈夫曼树的根节点,从此根节点开始遍历,就能遍历完整个哈夫曼树。
3、图形表示:
假设有6个权值:1、2、3、4、5、6,生成哈夫曼树的过程如下:
依次下去...
这样,最终得到的父节点21就是哈夫曼树的根节点,遍历树的话,
c/c++就是:root->left root->right就可以通过递归的方式从root节点访问到最后一个子节点。
Java就是: root.left root.right通过递归从root访问到最后一个子节点。
当然,二叉树的遍历不止递归一种方法,递归是最有效率的一种,还可以通过数据结构里面堆/栈的方式进行遍历。
下面是我写的实现哈夫曼树的Java代码(为了完成功能,绝壁不是优秀的,但可以方便看懂)
注:储存权值使用了List列表,随时增或者删方便一点。
1 import java.util.ArrayList; 2 import java.util.List; 3 4 class Node 5 { 6 int weight; 7 Node left,right,parent; 8 public Node(int weight) 9 { 10 this.weight=weight; 11 } 12 } 13 public class Huffman { 14 private static List<Node> list=new ArrayList<Node>(); 15 public static Node root; 16 public void insert(Node node) 17 { 18 //按照插入排序的方式将节点有序插入list 19 if(list.size()==0){ 20 list.add(node); 21 return; 22 } 23 int size=list.size(); 24 for(int i=0;i<size;) 25 { 26 if(list.get(i).weight<node.weight){ 27 i++; 28 if(i>=list.size()) 29 list.add(node); 30 } 31 else 32 { 33 //交换位置 34 list.add(list.get(list.size()-1)); 35 for(int j=list.size()-1;j>i;j--) 36 { 37 list.set(j, list.get(j-1)); 38 } 39 list.set(i, node);//插入新数据 40 return; 41 } 42 43 } 44 45 } 46 public Node createTree(Node n1,Node n2) 47 { 48 //返回新子树的父节点 49 Node parentNode=new Node(0); 50 parentNode.weight=n1.weight+n2.weight; 51 parentNode.left=n1; 52 parentNode.right=n2; 53 n1.parent=parentNode; 54 n2.parent=parentNode; 55 return parentNode; 56 } 57 public void run(List<Node> list) 58 { 59 int length=list.size(); 60 while(length!=0) 61 { 62 if(length==1){ 63 root=list.get(0); 64 return; 65 } 66 if(length==2){ 67 root=createTree(list.get(0),list.get(1)); 68 return; 69 } 70 Node n1=list.get(0); 71 Node n2=list.get(1); 72 Node newNode=createTree(n1,n2); 73 for(int i=0;i<length-2;i++) 74 { 75 //转移数据 76 list.set(i, list.get(i+2)); 77 } 78 list.remove(length-1); 79 list.remove(length-2); 80 insert(newNode); 81 length=list.size(); 82 } 83 84 } 85 public void display(Node node) 86 { 87 if(node!=null) 88 { 89 display(node.left); 90 System.out.print(node.weight+"\t"); 91 display(node.right); 92 } 93 } 94 public void drawTree(Node node) 95 { 96 if(node!=null) 97 { 98 //中序遍历,打算打印树形状,有些麻烦,后面改进 99 // if(node.parent!=null&&node.parent.left==node)100 // System.out.print("/");101 // if(node.parent!=null&&node.parent.right==node)102 // System.out.print("\\");103 System.out.print(node.weight+"\t");104 drawTree(node.left);105 drawTree(node.right);106 }107 }108 public static void main(String[] args)109 {110 Huffman hf=new Huffman();111 hf.insert(new Node(1));112 hf.insert(new Node(2));113 hf.insert(new Node(3));114 hf.insert(new Node(4));115 hf.insert(new Node(5));116 hf.insert(new Node(6));117 hf.run(list);118 System.out.println("前序遍历");119 hf.display(root);120 System.out.println("\n中序遍历");121 hf.drawTree(root);122 }123 }
执行结果:
后面,将写通过哈夫曼解析具体报文。
闲来无事写写-Huffman树的生成过程