数据结构1.0哈弗曼篇_JAVA_编程开发_程序员俱乐部

编者语：一直在拖拉，从明儿起慢慢写吧，任重道远啊，啊~~

1.定义：

? ? ? ? ?哈夫曼树又称最优hashu.html" target="_blank">二叉树，是一种带权路径长度最短的二叉树。

2.建树：

? ? ? ? ?1）对给定的n个权值构成初始集合F={A1,A2,A3...};

? ? ? ? ?2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左 ?右子树的根结点的权值之和。?

? ? ? ? ?3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。?

? ? ? ? ?4）重复2）和3），直到集合F中只有一棵二叉树为止。

3.代码如下：

?

public class HFM {

public Node creatTree(int[] dd){

//创建节点数组

Node[] nodes=new Node[dd.length];

//把数组中数字存到节点上

for(int i=0;i<nodes.length;i++){

Node node=new Node();

node.data=dd[i];

//把节点保存到数组

nodes[i]=node;

}

?

while(nodes.length>1){

//排序

sort(nodes);

//找出前两个节点，最小

Node n1=nodes[0];

Node n2=nodes[1];

//把两个节点组合

Node n3=new Node();

n3.data=n1.data+n2.data;

//左小右大

if(n1.data<n2.data){

n3.left=n1;

n3.right=n2;

}else {

n3.left=n2;

n3.right=n1;

}

//创建一个新数组

Node[] n=new Node[nodes.length-1];

//保存

for(int i=0;i<nodes.length-2;i++){

n[i]=nodes[i+2];

}

n[n.length-1]=n3;

nodes=n;

}

return nodes[0];

}

//冒泡排序

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].data>nodes[j].data) {

Node node=nodes[i];

nodes[i]=nodes[j];

nodes[j]=node;

}

}

}

}

?//打印编码

public void printCode(Node node,String code){

if(node.left==null||node.right==null){

System.out.println(node.data+"的哈夫曼数是"+code);

}

if(node.left!=null){

printCode(node.left,code+"0");

}

if(node.right!=null){

printCode(node.right,code+"1");

}

}

//主方法

public static void main(String[] args){

int[] d={2,3,5,7,11,13,17,19,23,29,31,37,41};

HFM hfm=new HFM();

Node root=hfm.creatTree(d);

hfm.printCode(root, "");

}

}

?

?