Linux安全网 - Linux操作系统_Linux 命令_Linux教程_Linux黑客

会员投稿 投稿指南 本期推荐:
搜索:
您的位置: Linux安全网 > Linux编程 > » 正文

贪心之huffman树

来源: 未知 分享至:


贪心的思想很简单,关键在于用一个什么样的结构来实现贪心过程。

package Section9;

import java.util.Queue;
import java.util.Iterator;
import java.util.LinkedList;


/*第九章 贪婪算法 Huffman编码*/

public class Huffman {

/**
*
@param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
double[] P = {0.35,0.1,0.2,0.2,0.15};
char[] CC = {'B','-','C','D','A'};

TreeNode root
= Huffman(P,CC);

System.out.println(root.p);
}


public static TreeNode Huffman(double[] P,char[] CC){
//输入要编码的字符的概率数组,返回huffman树的root结点
int n = P.length;
TreeNode[] Roots
= new TreeNode[n]; //当前root结点数组
Queue<TreeNode> queue = new LinkedList<TreeNode>(); //注意java中Queue是一个接口

//树队列的初始化
for(int i = 0;i < n;i++)
{
Roots[i]
= new TreeNode(P[i]);
Roots[i].c
= CC[i];
queue.add(Roots[i]);
}

while(queue.size() != 1)
{
//找到最小的结点并删除
TreeNode leftNode = queue.peek();
Iterator it
= queue.iterator();
while(it.hasNext())
{
TreeNode node
= (TreeNode) it.next();
if(node.p < leftNode.p)
leftNode
= node;
}
queue.remove(leftNode);

//找到最小的结点并删除
TreeNode rightNode = queue.peek();
it
= queue.iterator();
while(it.hasNext())
{
TreeNode node
= (TreeNode) it.next();
if(node.p < rightNode.p)
rightNode
= node;
}
queue.remove(rightNode);

//用上述最小的2个结点构造一颗树,加入树队列
TreeNode Root = new TreeNode(leftNode.p + rightNode.p);
Root.leftNode
= leftNode;
Root.rightNode
= rightNode;

queue.add(Root);
}

return queue.peek();
}
}



描述略。




Tags:
分享至:
最新图文资讯
1 2 3 4 5 6
验证码:点击我更换图片 理智评论文明上网,拒绝恶意谩骂 用户名:
关于我们 - 联系我们 - 广告服务 - 友情链接 - 网站地图 - 版权声明 - 发展历史