Java代码实现哈夫曼树 生成哈夫曼树的算法
java 高手速度进
运动会分数统计
创新互联建站专注于郓城企业网站建设,自适应网站建设,商城网站制作。郓城网站建设公司,为郓城等地区提供建站服务。全流程按需定制开发，专业设计，全程项目跟踪，创新互联建站专业和态度为您提供的服务
一、 任务
参加运动会有n个学校，学校编号为1……n。比赛分成m个项目，项目编号为1……m。项目取前五名积分；积分分别为：7、5、3、2、1；（m=20,n=20）
功能要求：
1).可以输入各个项目的前五名的学校编号；
2)．能统计各学校总分；
3)．可以按学校编号输出、学校总分排序输出，输出内容包括学校编号，总分和名次。
规定：输入数据形式和范围：20以内的整数（如果做得更好可以输入学校的名称，运动项目的名称）；各学校分数为整形。
界面要求：有合理的提示，根据提示，可以完成相关的功能要求。
二、 存储分析
由于学校个数、项目个数是确定的，并不会随时需要增加或减少，所以采用顺序存储结构较好，并且能随机存取。即采用数组作为存储结构。
学校个数为数组长度，每个数组元素必须包含如下信息：学校编号，项目1成绩，项目2成绩，……，项目m成绩，总分，名次。（方便完成功能1，2，4和3部分）
由于功能3要求能按学校总分排序输出，宜另外按总分顺序存储学校的总分信息。
综合前面分析，需要两个数组，数组1按学校编号顺序存放学校编号，项目1成绩，项目2成绩，……，项目m成绩，总分，名次。数组2按学校总分存放学校编号，总分，名次。
三、 程序结构安排
1、 输入各个项目的前五名的学校编号，填写数组1；
2、 计算数组1的学校总分；
3、 对数组1按总分排序，结果存放在数组2。填写数组2的名次。
4、 将数组2的名次信息填回数组1。
四、 输出
1、 按学校编号输出：即输出数组1相关信息；
2、 按学校总分排序：即输出数组2相关信息；
3、 按学校编号查询学校各个项目的情况：即输出数组1相应学校信息。
五、 举例
有10个学校，5个项目。
数组1：
数组下标 学校编号 项目1 项目2 项目3 项目4 项目5 总分 名次
0 1 7 3 2 12 3
1 2 1 7 2 10 4
2 3 5 3 8 6
3 4 5 1 7 3 16 1
4 5 1 1 7
5 6 2 7 9 5
6 7 5 2 5 1 13 2
7 8 3 2 5 10 4
8 9 1 1 7
9 10 3 7 10 4
数组2：
数组下标 学校编号 总分 名次
0 4 16 1
1 7 13 2
2 1 12 3
3 2 10 4
4 8 10 4
5 10 10 4
6 6 9 5
7 3 8 6
8 5 1 7
9 9 1 7
我忘记发了
作者：recluse 发表时间：2008-10-10 16:01:00
第2楼
哈夫曼树的建立
一、功能
输入组成二叉树的各个叶子值和权值，建立最优二叉树，并输出最优二叉树的数组存储形式。
二、什么是最优二叉数
n个带权叶子组成的所有二叉数中，带权路径长度最小的二叉树。（带权路径长度=所有叶子结点权值乘以其到根结点路径长度之和）
三、建立最优二叉数
简述：每次选择权值最小的两个叶子合并成一个新的叶子结点，新叶子结点权值为这两个叶子结点权值之和。
四、程序分析
由于叶子结点个数n已知，根据二叉树性质得知，整棵二叉树结点总数为（2n-1）个，故可建立长度为（2n-1）的数组。
数组每个元素为二叉树的一个结点，由5个域组成，所以应采用结构体类型，包括结点值，权值，左孩子，右孩子，双亲。
Struct tree1
{char lerves;
int weight;
int rch;
int lch;
int parent;
}tree[9];
五、例子及程序流程
1、 输入叶子个数及初始化。
如叶子结点个数为5，数组长度就为9。
2、 输入各个叶子的值、权值，并对数组初步赋值。
如各个叶子值分别为A、B、C、D、E，各个权值分别为18，12，10，7，11。此部分信息由键盘一边输入，一边对数组初步赋值，结果如下：
数组下标 叶子值 权值 左孩子 右孩子 双亲
0 A 18 0 0 0
1 B 12 0 0 0
2 C 10 0 0 0
3 D 7 0 0 0
4 E 11 0 0 0
5
6
7
8
3、 计算二叉树其余结点信息。
由于5个叶子结点，要合并4次。每次从还无双亲（无双亲代表还未合并过）的叶子结点中选择权值最小的两个叶子结点进行合并，新结点下标为这两个叶子的双亲，新结点的权值为这两个叶子权值之和，左孩子为最小结点下标，右孩子为次小结点下标，叶子值不需要，双亲为0。
如下为合并一次后的结果，如此循环4次即可：
数组下标 叶子值 权值 左孩子 右孩子 双亲
0 A 18 0 0 0
1 B 12 0 0 0
2 C 10 0 0 5
3 D 7 0 0 5
4 E 11 0 0 0
5 17 3 2 0
6
7
8
4、 输出二叉树（即输出数组）。
将二叉树按上表以表格形式在屏幕上输出即可。
作者：recluse 发表时间：2008-10-14 12:20:00
第3楼
#includestdio.h
#includestring.h
struct{
int sport[5];
int zf;
int mc;
}student1[10];
struct{
int snum;
int zf;
int mc;
}student2[10];
void main()
{
int point[5],i,j,temp,bj=1,temp1;
int k=0;
printf("input the sport point:\n");
for(i=0;i5;i++){
printf("point%d:",i+1);
scanf("%d",point[i]); }
for(i=0;i5;i++)
{
for(j=0;j5;j++){
printf("Input Sport %d 's School Number ( Point is %d ) :\t",i+1,point[j]);
scanf("%d",k);
student1[k-1].sport[i]=point[j];
}
}
for(i=0;i10;i++)
{
for(j=0;j5;j++)
student1[i].zf=student1[i].sport[j]+student1[i].zf;
student2[i].zf=student1[i].zf;
student2[i].snum=i+1;
}
for(i=0;i9;i++)
{
k=1;
for(j=0;j9-i;j++)
if (student2[j+1].zfstudent2[j].zf) {
temp=student2[j].zf;
temp1=student2[j].snum;
student2[j].zf=student2[j+1].zf;
student2[j].snum=student2[j+1].snum;
student2[j+1].zf=temp;
student2[j+1].snum=temp1;
k=0;
}
if(k) break;
}
for(i=0;i10;i++)
{
if(student2[i+1].zf==student2[i].zf) student2[i].mc=bj;
else student2[i].mc=bj++;
}
for(i=0;i10;i++)
{
for(j=0;j10;j++)
if(student2[i].snum==j+1) student1[j].mc=student2[i].mc;
}
printf("\t\t\t\tFORM 1\n\n");
printf("School Number:\tSport1:\tSport2:\tSport3:\tSport4:\tSport5:\tSum:\tResult:\n");
for(i=0;i10;i++) {
printf(" %d\t ",i+1);
for(j=0;j5;j++)
printf("%d\t ",student1[i].sport[j]);
printf("%d\t %d\n",student1[i].zf,student1[i].mc);
printf("\n\n");
}
printf("Press Any Butter\n\n");
getch();
printf("\t\t\tFORM 2\n\n");
printf("School Number:\tSum:\tResult:\n");
for(i=0;i10;i++)
{
printf("\t%d\t %d\t %d\n",student2[i].snum,student2[i].zf,student2[i].mc);
}
printf("\n\nPress Any Butter\n\n");
getch();
printf("\n\n");
while(1)
{
printf("Input You Want To Find The School Number(1-10):\t");
scanf("%d",k) ;
printf("\n\n");
for(i=0;i10;i++){
if(k==i+1){
printf("School Number:\tSport1:\tSport2:\tSport3:\tSport4:\tSport5:\tSum:\tResult:\n");
printf(" %d\t ",k);
for(j=0;j5;j++)
printf("%d\t ",student1[i].sport[j]);
printf("%d\t %d\n\n",student1[i].zf,student1[i].mc); }
}
}
}
JAVA和数据结构大虾们帮下忙： 输入一段文字，该程序可以统计出每个字符出现的次数并对字符进行哈夫曼编码
写给你了，请发JAVA版块
package other;
import java.io.Serializable;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
/**
* 定义了一种接口，要进行编码的最小单元类必需实现些接口
*
*/
interface CombinableT extends ComparableT {
T combinate(T a, T b);
}
/**
*
* the huffman tree Class 哈夫曼树，包括当前节点数据信息，左节点，右节点信息。
*/
class HuffmanTreeT extends CombinableT implements
ComparableHuffmanTreeT {
/** the root of huffman tree */
private T root;
/** the left node of huffman tree */
private HuffmanTreeT left;
/** the right node of huffman tree */
private HuffmanTreeT right;
/** 哈夫曼编码字符串，如:0000110 */
private String huffmanCodeString = "";
/** 是否对最终生成的哈夫曼进行过编码操作 */
private static boolean isSettedHuffmanCoderString = false;
public T getRoot() {
return root;
}
public void setRoot(T root) {
this.root = root;
}
public HuffmanTreeT getLeft() {
return left;
}
public void setLeft(HuffmanTreeT left) {
this.left = left;
}
public HuffmanTreeT getRight() {
return right;
}
public void setRight(HuffmanTreeT right) {
this.right = right;
}
/**
*
* 重写此方法用于递归合并节点后进行排序操作
*
*/
public int compareTo(HuffmanTreeT o) {
return o.getRoot().compareTo(this.getRoot());
}
public String toString() {
return "the root:" + this.getRoot() + "\r\nthe left:" + this.getLeft()
+ "\r\nthe right:" + this.getRight();
}
/**
*
* 对最终生成的树进行哈夫曼编码，使每个叶子节点生成01的路径编码
*
*/
private void setHuffmanCoderString() {
HuffmanTreeT left = this.getLeft();
// 如果有左节点则在路径中追加"0"
if (left != null) {
left.huffmanCodeString = this.huffmanCodeString + "0";
left.setHuffmanCoderString();// 递归编码
}
HuffmanTreeT right = this.getRight();
// 如果有右节点则在路径中追加"1"
if (right != null) {
right.huffmanCodeString = this.huffmanCodeString + "1";
right.setHuffmanCoderString();// 递归编码
}
}
public void printHuffmanCoderString() {
// 打印最终生成树的哈夫曼编码前要进行编码操作，
// 且此操作只执行一次，所以用全局标识变量判断
if (!HuffmanTree.isSettedHuffmanCoderString) {
this.setHuffmanCoderString();
HuffmanTree.isSettedHuffmanCoderString = true;// 标识已执行过编码
}
// 如果是叶子节点（即要编码的单元），则打印出编码信息，如果是非叶子结点（中间临时生成的节点），则不打印
if (this.left == null this.right == null)
System.out.println("the " + this.getRoot() + " huffmanCoder:"
+ this.huffmanCodeString);
if (this.left != null)
this.left.printHuffmanCoderString();// 递归打印
if (this.right != null)
this.right.printHuffmanCoderString();// 递归打印
}
}
/**
*
* 用类用于生成一个哈夫曼树
*/
class HuffmanTreeFactoryT extends CombinableT {
/** 初始时一个list列表当作要编码的单元类的容器 */
private ListHuffmanTreeT HuffmanTreeCollection;
/**
*
* @param unitClasses
* 待编码的单元类集合
*
*/
public HuffmanTreeFactory(ListT unitClasses) {
if (unitClasses == null || unitClasses.size() == 0)
throw new IllegalArgumentException(
"the unit classes collection can't be empty");
HuffmanTreeCollection = new LinkedListHuffmanTreeT();
// 初始化哈夫曼集合容器
for (T unitClass : unitClasses) {
HuffmanTreeT huffmanTree = new HuffmanTreeT();
huffmanTree.setRoot(unitClass);
huffmanTree.setLeft(null);
huffmanTree.setLeft(null);
HuffmanTreeCollection.add(huffmanTree);
}
Collections.sort(HuffmanTreeCollection);
}
/**
* 将待编码的哈夫曼集合处理成只含有一个元素的集合，则这最后一个元素 即为最终生成的哈夫曼树
*/
private void generateHuffmanTree() {
while (true) {
if (HuffmanTreeCollection == null
|| HuffmanTreeCollection.size() = 1)
break;
// 处理之前一定要重新排序，这是哈夫曼编码的关键原理
Collections.sort(HuffmanTreeCollection);
HuffmanTreeT huffmanTreeOne = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeTwo = HuffmanTreeCollection.remove(0);
HuffmanTreeT huffmanTreeNew = new HuffmanTreeT();
// 将集合中前面两个元素合并成一个元素插到集合中去
// 并将第一个元素和第二个元素分别作为新元素的左，右节点
huffmanTreeNew.setRoot(huffmanTreeOne.getRoot().combinate(
huffmanTreeOne.getRoot(), huffmanTreeTwo.getRoot()));
huffmanTreeNew.setLeft(huffmanTreeOne);
huffmanTreeNew.setRight(huffmanTreeTwo);
HuffmanTreeCollection.add(huffmanTreeNew);
}
}
/**
*
*
*
* @return 生成最终的哈夫曼树
*
*/
public HuffmanTreeT getHuffmanTree() {
generateHuffmanTree();
return this.HuffmanTreeCollection.get(0);
}
}
/**
* 自定义一个用于测试的单元类
*/
class UnitClass implements Serializable, CombinableUnitClass {
/** 出现概率数据 */
private int rate;
public UnitClass(int rate) {
this.rate = rate;
}
public int getRate() {
return rate;
}
public void setRate(int rate) {
this.rate = rate;
}
/**
* implements thid compartTo() in order to sort the
*
* collection stored from unitclass
*/
public int compareTo(UnitClass o) {
return o.getRate() this.rate ? 1 : o.getRate() this.rate ? -1 : 0;
}
public String toString() {
return "the rate is:" + rate;
}
/**
*
* 重写此方法用于哈夫曼编码时可以合并两个分支点信息
*
*/
public UnitClass combinate(UnitClass a, UnitClass b) {
if (a == null || b == null)
return null;
return new UnitClass(a.getRate() + b.getRate());
}
}
public class Test {
public static int counter(String s, char c) {
int count = 0;
for (int i = 0; i s.length(); i++) {
if (s.charAt(i) == c) {
count++;
}
}
return count;
}
public static void main(String[] args) {
String str = "你好呵呵123abbeab啊";
ListUnitClass l = new ArrayListUnitClass();
for (int i = 0; i str.length(); i++) {
char c = str.charAt(i);
System.out.println(c + "出现了" + counter(str, c) + "次");
l.add(new UnitClass(c));
}
HuffmanTreeFactoryUnitClass factory = new HuffmanTreeFactoryUnitClass(
l);
factory.getHuffmanTree().printHuffmanCoderString();
}
}
6、求java算法 已知四个带权的结点：(A,1),(B,2),(C,2),(D,3)，构造Huffman数，并给出每个结点的编码。
可以参考一下以下的代码:
/*
* 求哈夫曼树
*/
public class BinaryTree {
TreeNode[] node;
public BinaryTree(int[] w) {
int n = w.length;
node = new TreeNode[n];
node = initTree(node,n,w);
display(node,n);
node = createTree(node,n,w);
display2(node,n);
}
private void display2(TreeNode[] node2, int n) {
System.out.println("====================================================");
System.out.println("index\tweight\tleft\tright\tparent");
for(int i=0;in;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left+"\t"+node2[i].right+"\t"+node2[i].parent.getWeight());
}
for(int i=n;i2*n-2;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left.getWeight()+"\t"+node2[i].right.getWeight()+"\t"+node2[i].parent.getWeight());
}
System.out.println(2*n-2+"\t"+node2[2*n-2].getWeight()+"\t"+node2[2*n-2].left.getWeight()+"\t"+node2[2*n-2].right.getWeight()+"\t"+node2[2*n-2].parent);
}
private void display(TreeNode[] node2, int n) {
System.out.println("====================================================");
System.out.println("index\tweight\tleft\tright\tparent");
for(int i=0;i2*n-1;i++)
{
System.out.println(i+"\t"+node2[i].getWeight()+"\t"+node2[i].left+"\t"+node2[i].right+"\t"+node2[i].parent);
}
}
private TreeNode[] initTree(TreeNode[] a,int n,int[] weight) {
a=new TreeNode[2*n-1];
for(int i=0;i2*n-1;i++)
{
if(in)
a[i]=new TreeNode(weight[i]);
else
a[i]=new TreeNode(0);
}
return a;
}
private TreeNode[] createTree(TreeNode[] a, int n, int[] w) {
for(int i=n;i2*n-1;i++)
{
int min=65566,cmin=65566;
int x=0,cx=0;
for(int j=0;ji;j++)
{
if(a[j].parent==nulla[j].getWeight()min)
{
cmin=min;
cx=x;
min=a[j].getWeight();
x=j;
}
else if(a[j].parent==nulla[j].getWeight()cmin)
{
cmin=a[j].getWeight();
cx=j;
}
}
a[i].setWeight(min+cmin);
a[i].left=new TreeNode(x);
a[i].right=new TreeNode(cx);
a[x].parent=new TreeNode(i);
a[cx].parent=a[x].parent;
}
return a;
}
public static void main(String[] args) {
int[] w = new int[]{1,2,3,4,5,6,7,8,9};
new BinaryTree(w);
}
}
class TreeNode {
private int weight;
TreeNode left;
TreeNode right;
TreeNode parent;
public TreeNode(int weight) {
this.weight = weight;
this.left = null;
this.right = null;
this.parent = null;
}
public int getWeight() {
return this.weight;
}
public void setWeight(int weight) {
this.weight = weight;
}
}
java版的数据结构课程设计（数据结构（java版）叶核亚）
我记得有一本书，叫java算法设计，找一下看看会不会对你有帮助...
用java实现哈夫曼编码
只要自己再加个类Tree就可以了。
代码如下：
public class Tree {
double lChild, rChild, parent;
public Tree (double lChild, double rChild, double parent) {
this.lChild = lChild;
this.rChild = rChild;
this.parent = parent;
}
public double getLchild() {
return lChild;
}
public void setLchild(double lChild) {
this.lChild = lChild;
}
public double getRchild() {
return rChild;
}
public void setRchild(double rChild) {
this.rChild = rChild;
}
public double getParents() {
return parent;
}
public void setParents(double root) {
this.parent = root;
}
}
这个 用JAVA 怎么写啊
亲，你这是在考验这个题目的难度啊，
首先：学生注册登记，他是数据库的插入操作、还是利用集合（collection）、数组等进行存储
再者：分析可知可能是数据库，你也没说是那种数据库，每种数据库的连接方式也不同
最后：怎么进行写代码， 这个不只是代码的要求，你提取的数据是打印在控制台，还是用图形化界面，还是网页...等等 一系类问题你没有说清楚啊。
以上回答你满意么？
新闻标题：Java代码实现哈夫曼树 生成哈夫曼树的算法
网站URL：http://6mz.cn/article/dodhcos.html