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）、数组等进行存储

再者：分析可知可能是数据库，你也没说是那种数据库，每种数据库的连接方式也不同

最后：怎么进行写代码， 这个不只是代码的要求，你提取的数据是打印在控制台，还是用图形化界面，还是网页...等等 一系类问题你没有说清楚啊。

以上回答你满意么？