首页 > 代码库 > 闲来无事写写-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树的生成过程