第java中霍夫曼樹的示例分析一、基本介紹

二、霍夫曼樹幾個重要概念和舉例說明

構成霍夫曼樹的步驟

舉例：以arr={136781329}

publicclassHuffmanTree{

publicstaticvoidmAIn(String[]args){

int[]arr={13,7,8,3,29,6,1};

Noderoot=createHuffmanTree(arr);

preOrder(root);

//編寫一個前序遍歷的方法

publicstaticvoidpreOrder(Noderoot){

if(root!=null){

root.preOrder();

}else{

System.out.println(樹是空樹，無法遍歷~~

//創(chuàng)建赫夫曼樹的方法

*@paramarr需要創(chuàng)建成霍夫曼樹的數組

*@return創(chuàng)建好后的霍夫曼樹的root節(jié)點

publicstaticNodecreateHuffmanTree(int[]arr){

//第一步為了操作方便

//1.遍歷arr數組

//2.將arr的每個元素構成一個Node

//3.將Node放入到ArrayList中

ListNodenodes=newArrayListNode

for(intvalue:arr){

nodes.add(newNode(value));

while(nodes.size()1){

//排序從小到大

Collections.sort(nodes);

System.out.println(nodes=+nodes);

//取出根節(jié)點權值最小的兩顆二叉樹

//注意：如果是從大到小排列的：就應該取倒數第一個和倒數第二個

//(1)取出權值最小的節(jié)點(二叉樹)

NodeleftNode=nodes.get(0);

//(2)取出權值第二小的節(jié)點(二叉樹)

NoderightNode=nodes.get(1);

//(3)構建一顆新的二叉樹

Nodeparent=newNode(leftNode.value+rightNode.value);

parent.left=leftNode;

parent.right=rightNode;

//(4)從ArrayList刪除處理過的二叉樹

nodes.remove(leftNode);

nodes.remove(rightNode);

//(5)將parent加入到nodes

nodes.add(parent);

//返回赫夫曼樹的root節(jié)點

returnnodes.get(0);

//創(chuàng)建節(jié)點類

//為了讓Node對象支持排序Collections集合排序

//讓Node實現Comparable接口

classNodeimplementsComparableNode{

intvalue;//節(jié)點權值

Nodeleft;//指向左子節(jié)點

Noderight;//指向右子節(jié)點

publicNode(intvalue){

this.value=value;

//寫一個前序遍歷

publicvoidpreOrder(){

System.out.println(this);

if(this.left!=null){

this.left.preOrder();

if(this.right!=null){

this.right.preOrder();

@Override

publicStringtoString(){

returnNode[value=+value+]

@Override

publicintcompareTo(Nodeo){

//表示從小到大排列

returnthis.value-o.value;

}

霍夫曼編碼

一、基本介紹

二、原理剖析

6）說明：

原來長度是359，壓縮了(359-133)/359=62.9%

此編碼滿足前綴編碼，即字符的編碼都不能是其他字符編碼的前綴。不會造成匹配的多義性；

霍夫曼編碼是無損的壓縮處理方案

霍夫曼編碼壓縮文件注意事項

1）如果文件本身就是經過壓縮處理的，那么