wpl算法java

⑴ 哈夫曼树左小右大是指什么

哈弗曼（Huffman）树，也称最优树，是一类带全路径长度最短的树，在实际中有广泛的应用，也是二叉树的一个具体应用。
在哈夫曼树的定义中，涉及到了路径、路径长度、权等概念，下面先给出概念的定义。

一、概念与定义

路径：从树的一个结点到另一个结点的分支构成这两个结点之间的路径，对于哈夫曼树特指从根节点到某节点的路径。

路径长度：路径上的分支数目叫做路径长度。
树的路径长度：从树根到每一结点的路径长度之和。
权：赋予某一个事物的一个量，是对事物的某个或某些属性数值化描述。在数据结构中，包括结点和边两大类，所以对应有结点权和边权。其具体代表的意义有具体情况而定。
结点的带权路径长度：从树根到结点之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和(WPL--weighted path length)。它的权值分别为，从根到各叶子结点的路径长度分别为。则其带权路径长度WPL通常记作：

WPL的计算如下所示：

对于图a：WPL=2*(9+8+1+6)=48;

对于图b：WPL=8*1+9*2+(1+6)*3=47;

对于图c：WPL=9*1+8*2+(1+6)*3=46;

由图可以看出，权值越大的结点离根节点越近。

二、哈夫曼树构造算法

哈弗曼树的构造步骤：

1、根据给定的n个权值（w1,w2,w3,....wn）,构造n棵只有根结点的二叉树，令起权值为wj；
2、在森林中选取两棵根结点权值最小的树作为左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和
3、在森林中删除这两棵树，同时将新得到的二叉树加入森林中；
4、重复上述两个步骤，最后构成的树即为哈弗曼树。
下图显示了构造一棵哈弗曼树的两种方法：
常见的构造比较简单，这里我选择了两种比较特殊的数据进行了构造：
哈弗曼树并行生长的原则：如果新形成的二叉树的根节点的值大于或等于森林中的另外两个只有根结点树的值，那么接下来的两棵树将并行生长。并不是线性的直接向上生长。

构造方法一：

构造方法二：

最后显示了哈夫曼树的编码，编码的原则左小右大。

三、哈夫曼树在编码中的应用
哈夫曼树最常应用的地方就是对报文进行编码传输通信。在数据的交流中，我们对数据是有要求的：
（1）解码结果与发送方发送的电文完全一样。也就是说发送方传输的二进制编码，到接收方解码后必须具有唯一性；
（2）为了传输的效率和网络的通信及时占用资源少，发送的二进制编码尽可能地短。
下面介绍两种编码方式：
1. 等长编码
这种编码方式的特点是每个字符的编码长度相同，编码长度就是每个编码被翻译的二进制位数。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。 若现在有一段电文为：ABACCDA，则应发送二进制序列：000100101011000111，总长度为16位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但是存在的问题是编码长度并不是最短的，不满足上面的（2）的要求，因为在大数据量的情况下，我们必须的考虑效率问题，那么如何得到最短的编码呢？使用哈夫曼树就可以解决这个问题。这里先介绍一个前缀吗的概念。
前缀码：如果在一个系统中，任意一个编码都不是其他任何编码的前缀（最左子串），则称此编码系统中的编码是前缀码。
例如：（A:110、B:111、C:10、D:0）就是前缀码。但是（A:110、B:11、C:00、D:0）就不是前缀码。0是00的前缀，11是110的前缀。如果不定长的编码不是前缀码，则在译码时会产生二义性。例如110是A呢？还是BD呢？所以对于不定长编码一定要是前缀码。
2. 不等长编码
不等长编码可以叫最优的前缀码。在传送报文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的， 使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。如何得到最优的前缀编码呢？我们就可以利用上述的哈夫曼树来设计，同常成这种编码为哈夫曼编码，它不仅减少电文的总长，还必须考虑编码的唯一性。

四、哈夫曼树中的唯一和不唯一
唯一：哈夫曼树的WPL一定是最小的，唯一，最优是不变的。
不唯一：编码不唯一（表现出来就是形态不唯一）。比如说左小右大，或者是左大右小，树枝左右顺序是可以交换的，也就是说所得的哈夫曼编码则可能不同

⑵ 到底什么是哈夫曼树啊，求例子

哈夫曼树是给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

例子：

1、将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

2、 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；

3、从森林中删除选取的两棵树，并将新树加入森林；

4、重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

(2)wpl算法java扩展阅读：

按照哈夫曼编码构思程序流程：

1、切割的顺序是从上往下，直至数组中的元素全部出现在叶节点；

2、我们思路正好相反，从数组中找出最小的两个元素作为最下面的叶节点，在向备选数组中存入这两个叶节点的和（这个新的和加入累加运算，这个和也就是所求的最小值的一部分，原因如上图）。

3、以本题为例，备选数组中现有元素为{30，30}，再次取出两个最小元素进行求和，得到新的元素，回归备选数组并记入累加。

4、上述2.3布重复执行直至备选数组中只有一个元素，此时累加结束，返回累加值即可

5、求数组中的最小值，可以用小根堆进行提取最为方便；此题用到了贪心的思路，即用相同的策略重复执行，直至我们得到所需的结果。

⑶ 对于给定的一组权值W={1, 3, 7, 8, 14},建立哈夫曼树.

五个权值是137814

(1)从小到大排序137814(这是有序序列)
(2)每次提取最小的两个结点,取结点1和结点3,组成新结点N4,其权值=1+3=4,
取数值较小的结点作为左分支,1作为左分支,而3就作为右分支.
(3)将新结点N4放入有序序列,保持从小到大排序:
N47814
(4)重复步骤(2),提取最小的两个结点,N4与结点7组成新结点N11,其权值=4+7=11,
N4数值较小,作为左分支,而结点7就作为右分支.
(5)将新结点N11放入有序序列,保持从小到大排序:
8N1114
(6)重复步骤(2),提取最小的两个结点,结点8与N11组成新结点N19,其权值=8+11=19,
结点8的数值较小,作为左分支,N11就作为右分支.
(7)将新结点N19放入有序序列,保持从小到大排序:
14N19
(8)重复步骤(2),提取剩下的两个结点,结点14与N19组成新结点N33,其权值=14+19=33,
数值较小的结点14作为左分支,N19就作为右分支.
有序序列已经没有结点,最后得到"哈夫曼树":

N33
/
14N19
/
8N11
/
N47
/
13

带权路径长度(WPL):
根结点N33到结点14的路径长度是1,结点14的带权路径长度是14*1
根结点N33到结点8的路径长度是2,结点8的带权路径长度是8*2
根结点N33到结点7的路径长度是3,结点7的带权路径长度是7*3
根结点N33到结点3的路径长度是4,结点3的带权路径长度是3*4
根结点N33到结点1的路径长度是4,结点1的带权路径长度是1*4
所以,哈夫曼树的带权路径长度(WPL)等于
14*1+8*2+7*3+3*4+1*4=67

哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N33到结点14,经历一次左分支,结点14的编码就是0
从根结点N33到结点8,先经历右分支,后经历左分支,结点8的编码就是10
从根结点N33到结点7,先后经历三次右分支,结点7的编码就是111
从根结点N33到结点3,先经历两次右分支,再经历左分支,最后经历右分支,结点3的编码就是1101
从根结点N33到结点1,先经历两次右分支,再经历两次左分支,结点1的编码就是1100
得出所有结点的"哈夫曼编码":
权值14:0
权值8:10
权值7:111
权值3:1101
权值1:1100


//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：5
//输入5个整数作为权值：137814
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.

#include<stdio.h>
#include<stdlib.h>
typedefintElemType;
structBTreeNode
{
ElemTypedata;
structBTreeNode*left;
structBTreeNode*right;
};

//1、输出二叉树，可在前序遍历的基础上修改。
//采用广义表格式，元素类型为int
voidPrintBTree_int(structBTreeNode*BT)
{
if(BT!=NULL)
{
printf("%d",BT->data);//输出根结点的值
if(BT->left!=NULL||BT->right!=NULL)
{
printf("(");
PrintBTree_int(BT->left);//输出左子树
if(BT->right!=NULL)
printf(",");
PrintBTree_int(BT->right);//输出右子树
printf(")");
}
}
}

//2、根据数组a中n个权值建立一棵哈夫曼树，返回树根指针
structBTreeNode*CreateHuffman(ElemTypea[],intn)
{
inti,j;
structBTreeNode**b,*q;
b=malloc(n*sizeof(structBTreeNode));
//初始化b指针数组，使每个指针元素指向a数组中对应的元素结点
for(i=0;i<n;i++)
{
b[i]=malloc(sizeof(structBTreeNode));
b[i]->data=a[i];
b[i]->left=b[i]->right=NULL;
}
for(i=1;i<n;i++)//进行n-1次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标，k2为次最小的下标
intk1=-1,k2;
//让k1初始指向森林中第一棵树，k2指向第二棵
for(j=0;j<n;j++)
{
if(b[j]!=NULL&&k1==-1)
{
k1=j;
continue;
}
if(b[j]!=NULL)
{
k2=j;
break;
}
}
//从当前森林中求出最小权值树和次最小
for(j=k2;j<n;j++)
{
if(b[j]!=NULL)
{
if(b[j]->data<b[k1]->data)
{
k2=k1;
k1=j;
}
elseif(b[j]->data<b[k2]->data)
k2=j;
}
}
//由最小权值树和次最小权值树建立一棵新树，q指向树根结点
q=malloc(sizeof(structBTreeNode));
q->data=b[k1]->data+b[k2]->data;
q->left=b[k1];
q->right=b[k2];

b[k1]=q;//将指向新树的指针赋给b指针数组中k1位置
b[k2]=NULL;//k2位置为空
}
free(b);//删除动态建立的数组b
returnq;//返回整个哈夫曼树的树根指针
}

//3、求哈夫曼树的带权路径长度
ElemTypeWeightPathLength(structBTreeNode*FBT,intlen)//len初始为0
{
if(FBT==NULL)//空树返回0
return0;
else
{
if(FBT->left==NULL&&FBT->right==NULL)//访问到叶子结点
{
printf("+%d*%d",FBT->data,len);
returnFBT->data*len;
}
else//访问到非叶子结点，进行递归调用，
{//返回左右子树的带权路径长度之和，len递增
returnWeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}

//4、哈夫曼编码（可以根据哈夫曼树带权路径长度的算法基础上进行修改）
voidHuffManCoding(structBTreeNode*FBT,intlen)//len初始值为0
{
//定义静态数组a，保存每个叶子的编码，数组长度至少是树深度减一
staticinta[10];
inti;
//访问到叶子结点时输出其保存在数组a中的0和1序列编码
if(FBT!=NULL)
{
if(FBT->left==NULL&&FBT->right==NULL)
{
printf("权值为%d的编码：",FBT->data);
for(i=0;i<len;i++)
printf("%d",a[i]);
printf("
");
}
else//访问到非叶子结点时分别向左右子树递归调用，
{//并把分支上的0、1编码保存到数组a的对应元素中，
//向下深入一层时len值增1
a[len]=0;
HuffManCoding(FBT->left,len+1);
a[len]=1;
HuffManCoding(FBT->right,len+1);
}
}
}

intmain()
{
intn,i;
ElemType*a;
structBTreeNode*fbt;
printf("输入构造哈夫曼树中带权叶子结点数(n)：");
while(1)
{
scanf("%d",&n);
if(n>1)
break;
else
printf("重输n值：");
}
a=malloc(n*sizeof(ElemType));
printf("输入%d个整数作为权值：",n);
for(i=0;i<n;i++)
scanf("%d",&a[i]);
fbt=CreateHuffman(a,n);
printf("广义表形式的哈夫曼树：");
PrintBTree_int(fbt);
printf("
");
printf("哈夫曼树的带权路径长度：
");
printf("=");
printf("
=%d
",WeightPathLength(fbt,0));
printf("树中每个叶子结点的哈夫曼编码：
");
HuffManCoding(fbt,0);

return0;
}

⑷ 哈夫曼树

转自： http://blog.csdn.net/hikvision_java_gyh/article/details/8952596
哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=(W1 L1+W2 L2+W3 L3+...+ Wn Ln)，N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为: (a)WPL=7 2+5 2+2 2+4 2=36 (b)WPL=7 3+5 3+2 1+4 2=46 (c)WPL=7 1+5 2+2 3+4 3=35其中(c)树的WPL最小，可以验证，它就是哈夫曼树。

构造哈夫曼树的算法如下： 1）对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 2）在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 3）从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 4）重复2）和3），直到集合F中只有一棵二叉树为止。 例如，对于4个权值为1、3、5、7的节点构造一棵哈夫曼树，其构造过程如下图所示：

可以计算得到该哈夫曼树的路径长度WPL＝(1+3) 3+2 5+1*7=26。
哈夫曼编码应用 大数据 量的图像信息会给存储器的存储容量，通信干线信道的带宽，以及计算机的处理速度增加极大的压力。单纯靠增加存储器容量，提高信道带宽以及计算机的处理速度等方法来解决这个问题是不现实的，这时就要考虑压缩。压缩的关键在于编码，如果在对数据进行编码时，对于常见的数据，编码器输出较短的码字；而对于少见的数据则用较长的码字表示，就能够实现压缩。【例】：假设一个文件中出现了8种符号S0，SQ，S2，S3，S4，S5，S6，S7，那么每种符号要编码，至少需要3bit。假设编码成 000，001， 010，011，100，101，110，111。那么符号序列S0S1S7S0S1S6S2S2S3S4S5S0S0S1编码后变成 ，共用了42bit。我们发现S0，S1，S2这3个符号出现的频率比较大，其它符号出现的频率比较小，我们采用这样的编码方案：S0到S7的码辽分别01，11，101，0000，0001，0010，0011， 100，那么上述符号序列变成，共用了39bit。尽管有些码字如 S3，S4，S5，S6变长了(由3位变成4位)，但使用频繁的几个码字如S0，S1变短了，所以实现了压缩。对于上述的编码可能导致解码出现非单值性：比如说，如果S0的码字为01，S2的码字为011，那么当序列中出现011时，你不知道是S0的码字后面跟了个1，还是完整的一个S2的码字。因此，编码必须保证较短的编码决不能是较长编码的前缀。符合这种要求的编码称之为前缀编码。要构造符合这样的二进制编码体系，可以通过二叉树来实现。以下是哈夫曼树的 Java 实现：
[java] view plain

// 二叉树节点
public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = value; } public int getValue() { return value; } public void setValue(int value) { this.value = value; } public Node getLeftChild() { return leftChild; } public void setLeftChild(Node leftChild) { this.leftChild = leftChild; } public Node getRightChild() { return rightChild; } public void setRightChild(Node rightChild) { this.rightChild = rightChild; } public int compareTo(Object o) { Node that = (Node) o; double result = this.value - that.value; return result > 0 ? 1 : result == 0 ? 0 : -1; } }

private static Node build(List<Node> nodes) {
nodes = new ArrayList<Node>(nodes);
sortList(nodes);
while (nodes.size() > 1) {
createAndReplace(nodes);
}
return nodes.get(0);
}

/**

/**

private static void sortList(List<Node> nodes) {
Collections.sort(nodes);
}

`
/**

⑸ 两道题，求详细过程，讲解的。

首先声明，我没学过数据结构，以下专业术语不正确的或者做错了那么。。。请自己翻书查相关的准确术语
nk=(k-1)n0+1
如果nk成为父节点有nk个，n0成为子节点有n0个。对于k叉树而言，每当一个子节点拓展为一个父节点时，则子节点变为父节点即ak+=1同时a0-=1，同时子节点又多了k个即an+=k，两式子联立得每拓展一次时
ak+=1 a0+=k-1
又因为树的根节点是没有父亲的，所以n0要再加1
就得到上面的关系了。

自己画画图就出来了

第二题
树的形状如下图
○
○ 8
○ 7
○ 4
○ 3
1 2
中间的线不知道怎么画，就是A的子女分别是B和8，B的子女分别是C和7，下同，最后的E的子女是1和2
WPL算法 1*5+2*5+3*4+4*3+7*2+8*1 答案自己算（如果所有的路径的权都是1的话。。）

哈弗曼数算法如下
霍夫曼算法
（1）由给定的n个权值构造具有n棵扩充二叉树的森林F，其中每一棵扩充二叉树只有一个带有权值的根结点；
（2）在F中选取两棵根结点的权值最小的扩充二叉树作为左、右子树构造一棵新的二叉树，置新的二叉树的根结点的权值为其左、右子树上根结点的权值的之和。在F中删去这两棵二叉树，把新的二叉树加入F；
（3）重复步骤（2）直到F中仅剩下一棵树为止。

反正简单的理解就是说越是小的数越是放下面，然后每个根节点下面就放一个带有权的数，另一个当然就是根节点了，然后小的放下面，大的放上面，所谓WPL就是根节点到叶节点有几条路径，简单来说就是几条线，再乘以那个叶节点上的权值，然后都加起来就可以了。哈弗曼算法是这样的，怎么证明的忘记了。。。

⑹ java 题目 最好有简短的思路 谢谢

数据结构题，和java木有啥关系的。

⑺ 哈夫曼算法简介

看官们建议在看我的这篇文章之前，先看一下RlE算法  这个是计算机压缩算法的入门级，如果连这个算法的思想都不清楚的，请私聊我，单独讲解

简单说一下rle=字符乘以重复数量

举个例子，aaaaaabbbbbb的rlu就是a6b6

说回哈夫曼算法

第一  统计每个字符出现的次数

第二  将出现次数最少的字符连线并求数量和

第三  重复第二步完成哈夫曼树

第四  将哈夫曼树的左边的边写上0，右边的边也写上  1 

第五  从根节点开始沿着边去将数字写在对应的字符下面

这样一个哈夫曼编码就完成了

#include <iostream>

#include <iomanip>

using namespace std;

//哈夫曼树的存储表示

typedef struct

{

    int weight;    // 权值

    int parent, lChild, rChild;    // 双亲及左右孩子的下标

}HTNode, *HuffmanTree;

// 选择权值最小的两颗树

void SelectMin(HuffmanTree hT, int n, int &s1, int &s2)

{

    s1 = s2 = 0;

    int i;

    for(i = 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(0 == s1){

                s1 = i;

            }

            else{

                s2 = i;

                break;

            }

        }

    }

    if(hT[s1].weight > hT[s2].weight){

        int t = s1;

        s1 = s2;

        s2 = t;

    }

    for(i += 1; i < n; ++ i){

        if(0 == hT[i].parent){

            if(hT[i].weight < hT[s1].weight){

                s2 = s1;

                s1 = i;

            }else if(hT[i].weight < hT[s2].weight){

                s2 = i;

            }

        }

    }

}

// 构造有n个权值（叶子节点）的哈夫曼树

void CreateHufmanTree(HuffmanTree &hT)

{

    int n, m;

    cin >> n;

    m = 2*n - 1;

    hT = new HTNode[m + 1];    // 0号节点不使用

    for(int i = 1; i <= m; ++ i){

        hT[i].parent = hT[i].lChild = hT[i].rChild = 0;

    }

    for(int i = 1; i <= n; ++ i){

        cin >> hT[i].weight;    // 输入权值

    }

    hT[0].weight = m;    // 用0号节点保存节点数量

    /****** 初始化完毕, 创建哈夫曼树 ******/

    for(int i = n + 1; i <= m; ++ i){

        int s1, s2;

        SelectMin(hT, i, s1, s2);

        hT[s1].parent = hT[s2].parent = i;

        hT[i].lChild = s1; hT[i].rChild = s2;    // 作为新节点的孩子

        hT[i].weight = hT[s1].weight + hT[s2].weight;    // 新节点为左右孩子节点权值之和

    }

}

int HuffmanTreeWPL_(HuffmanTree hT, int i, int deepth)

{

    if(hT[i].lChild == 0 && hT[i].rChild == 0){

        return hT[i].weight * deepth;

    }

    else{

        return HuffmanTreeWPL_(hT, hT[i].lChild, deepth + 1) + HuffmanTreeWPL_(hT, hT[i].rChild, deepth + 1);

    }

}

// 计算WPL（带权路径长度）

int HuffmanTreeWPL(HuffmanTree hT)

{

    return HuffmanTreeWPL_(hT, hT[0].weight, 0);

}

// 输出哈夫曼树各节点的状态

void Print(HuffmanTree hT)

{

    cout << "index weight parent lChild rChild" << endl;

    cout << left;    // 左对齐输出

    for(int i = 1, m = hT[0].weight; i <= m; ++ i){

        cout << setw(5) << i << " ";

        cout << setw(6) << hT[i].weight << " ";

        cout << setw(6) << hT[i].parent << " ";

        cout << setw(6) << hT[i].lChild << " ";

        cout << setw(6) << hT[i].rChild << endl;

    }

}

// 销毁哈夫曼树

void DestoryHuffmanTree(HuffmanTree &hT)

{

    delete[] hT;

    hT = NULL;

}

int main()

{

    HuffmanTree hT;

    CreateHufmanTree(hT);

    Print(hT);

    cout << "WPL = " << HuffmanTreeWPL(hT) << endl;

    DestoryHuffmanTree(hT);

    return 0;

}

⑻ 用JAVA实现HUFFMAN算法 1 HUFFMAN算法原理 2 流程图 3 用JAVA语言编写代码

import java.util.*;
class HuffmanCode{
String name;
double weight;
int lc,rc,pa;
public HuffmanCode(){
name="";
weight=0;
lc=-1;rc=-1;pa=-1;
}
}

public class Huffman {
HuffmanCode[] codes;
String[] huffstring;
StringBuffer buffer=new StringBuffer();
public Huffman(String s) {
for(int i=0;i<s.length();i++){
if(buffer.indexOf(s.substring(i,i+1))==-1){
buffer.append(s.charAt(i));
}
}
System.out.println("字母："+buffer);
huffstring=new String[buffer.length()];
codes=new HuffmanCode[2*buffer.length()-1];
for(int i=0;i<2*buffer.length()-1;i++)
codes[i]=new HuffmanCode();
for(int i=0;i<buffer.length();i++){
codes[i].name=buffer.substring(i,i+1);
codes[i].weight=haveNum(buffer.charAt(i),s);
}
getHuffstring();
getCode(2*buffer.length()-2,huffstring,"");
//for(int i=0;i<codes.length;i++){
// System.out.println(""+i+":"+codes[i].name+codes[i].weight+" "+codes[i].lc+" "+codes[i].rc+" "+codes[i].pa);
//}
for(int i=0;i<huffstring.length;i++){
System.out.println(codes[i].name+" code:"+huffstring[i]);
}
System.out.println("编码："+getHuffmanCode(s));
System.out.println("平均码长为："+getLength());
}
public double getLength(){
double n=0;
for(int i=0;i<buffer.length();i++){
n+=huffstring[i].length();
}
return n/buffer.length();
}
public String getHuffmanCode(String s){
StringBuffer buf=new StringBuffer();
for(int i=0;i<s.length();i++){
buf.append(getEachCode(s.substring(i,i+1)));
}
return buf.toString();
}
public String getEachCode(String name){
for(int i=0;i<buffer.length();i++){
if(name.equals(codes[i].name)){
return huffstring[i];
}
}
return "";
}
public void getCode(int n,String[] thecodes,String thebuffer){
if(n<thecodes.length){
thecodes[n]=thebuffer;
return;
}
getCode(codes[n].lc,thecodes,thebuffer+"0");
getCode(codes[n].rc,thecodes,thebuffer+"1");
}
public void getHuffstring(){
int[] twos={0,0};
for(int i=buffer.length();i<2*buffer.length()-1;i++){
twos=findLastTwo(0,i);
codes[i].lc=twos[0];
codes[i].rc=twos[1];
codes[i].weight=codes[twos[0]].weight+codes[twos[1]].weight;
}
}
public int[] findLastTwo(int start,int end){
double[] weights={1.0,1.0};
int[] t={-1,-1};
for(int i=start;i<end;i++){
if(codes[i].pa!=-1)continue;
if(weights[0]>codes[i].weight){
weights[0]=codes[i].weight;
t[1]=t[0];
t[0]=i;
}
else if(weights[1]>codes[i].weight){
weights[1]=codes[i].weight;
t[1]=i;
}
}
codes[t[0]].pa=end;
codes[t[1]].pa=end;
return t;
}
public double haveNum(char c,String s){
double n=0;
for(int i=0;i<s.length();i++){
if(c==s.charAt(i))n++;
}
return n/s.length();
}
public static void main (String[] args) {
System.out.print("输入编码字符串：");
Scanner sr=new Scanner(System.in);
new Huffman(sr.nextLine());
}
}

⑼ 数据结构题、大哥大姐帮我做下题吧。万分感谢啊

什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。
2、面向对象概念：理解什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象。由于目前关于这个问题有许多说法，我们采用了一种最流行的说法，即Coad与Yourdon 给出的定义：面向对象 = 对象 + 类 + 继承 + 通信。
要点：
·抽象数据类型的封装性
·面向对象系统结构的稳定性
·面向对象方法着眼点在于应用问题所涉及的对象
3、数据结构的抽象层次：理解用对象类表示的各种数据结构
4、算法与算法分析：理解算法的定义、算法的特性、算法的时间代价、算法的空间代价。
要点：·算法与程序的不同之处需要从算法的特性来解释
·算法的正确性是最主要的要求
·算法的可读性是必须考虑的
·程序的程序步数的计算与算法的事前估计
·程序的时间代价是指算法的渐进时间复杂性度量

第二章 数组
1、作为抽象数据类型的数组：数组的定义、数组的按行顺序存储与按列顺序存储
要点：
·数组元素的存放地址计算
2、顺序表：顺序表的定义、搜索、插入与删除
要点：
·顺序表搜索算法、平均比较次数的计算
·插入与删除算法、平均移动次数的计算
3、多项式：多项式的定义
4、字符串：字符串的定义及其操作的实现
要点：
·串重载操作的定义与实现

第三章 链接表
1、单链表：单链表定义、相应操作的实现、单链表的游标类。
要点：
·单链表的两种定义方式（复合方式与嵌套方式）
·单链表的搜索算法与插入、删除算法
·单链表的递归与迭代算法
2、循环链表：单链表与循环链表的异同
3、双向链表：双向链表的搜索、插入与删除算法、链表带表头结点的优点
4、多项式的链接表示

第四章 栈与队列
1、栈：栈的特性、栈的基本运算
要点：
·栈的数组实现、栈的链表实现
·栈满及栈空条件、抽象数据类型中的先决条件与后置条件
2、栈的应用：用后缀表示计算表达式，中缀表示改后缀表示
3、队列：队列的特性、队列的基本运算
要点：
·队列的数组实现：循环队列中队头与队尾指针的表示，队满及队空条件
·队列的链表实现：链式队列中的队头与队尾指针的表示、
4、双向队列：双向队列的插入与删除算法
5、优先级队列：优先级队列的插入与删除算法

第五章 递归与广义表
1、递归：递归的定义、递归的数据结构、递归问题用递归过程求解
要点：·链表是递归的数据结构，可用递归过程求解有关链表的问题
2、递归实现时栈的应用
要点：·递归的分层（树形）表示：递归树
·递归深度（递归树的深度）与递归工作栈的关系
·单向递归与尾递归的迭代实现
3、广义表：广义表定义、广义表长度、广义表深度、广义表表头、广义表表尾
要点：
·用图形表示广义表的存储结构
·广义表的递归算法

第六章 树与森林
1、树：树的定义、树的基本运算
要点：
·树的分层定义是递归的
·树中结点个数与高度的关系
2、二叉树：二叉树定义、二叉树的基本运算
要点：
·二叉树性质、二叉树中结点个数与高度的关系、不同种类的二叉树棵数
·完全二叉树的顺序存储、完全二叉树的双亲、子女和兄弟的位置
·二叉树的前序·中序·后序·层次遍历
·前序
·中序
·后序的线索化二叉树、前驱与后继的查找方法
3、霍夫曼树：霍夫曼树的构造方法、霍夫曼编码、带权路径长度的计算
4、树的存储：树的广义表表示、树的双亲表示、树与二叉树的对应关系、树的先根·中根·后根·层次遍历。
5、堆：堆的定义、堆的插入与删除算法
要点：
·形成堆时用到的向下调整算法及形成堆时比较次数的上界估计
·堆插入时用到的向上调整算法

第七章 集合与搜索
1、集合的概念：集合的基本运算、集合的存储表示
要点：
·用位数组表示集合时集合基本运算的实现
·用有序链表表示集合时集合基本运算的实现
2、并查集：并查集定义、并查集的三种基本运算的实现
3、基本搜索方法
要点：
·对一般表的顺序搜索算法（包括有监视哨和没有监视哨）
·对有序顺序表的顺序搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。
·对有序顺序表的折半搜索算法、用判定树（即扩充二叉搜索树）描述搜索，以及平均搜索长度（成功与不成功）的计算。
4、二叉搜索树：
要点：
·动态搜索树与静态搜索树的特性
·二叉搜索树的定义、二叉搜索树上的搜索算法、二叉搜索树搜索时的平均搜索长度（成功与不成功）的计算。
·AVL树结点上的平衡因子、AVL树的平衡旋转方法
·高度为h的AVL树上的最少结点个数与最多结点个数
· AVL树的搜索方法、插入与删除方法

第八章 图
1、图：图的定义与图的存储表示
要点：
·邻接矩阵表示（通常是稀疏矩阵）
·邻接表与逆邻接表表示
·邻接多重表(十字链表)表示
2、深度优先遍历与广度优先遍历
要点：
·生成树与生成树林的定义
·深度优先搜索是个递归的过程，而广度优先搜索是个非递归的过程
·为防止重复访问已经访问过的顶点，需要设置一个访问标志数组visited
3、图的连通性
要点：
·深度优先搜索可以遍历一个连通分量上的所有顶点
·对非连通图进行遍历，可以建立一个生成森林
·对强连通图进行遍历，可能建立一个生成森林
·关节点的计算和以最少的边构成重连通图
4、最小生成树
要点：
·对于连通网络、可用不会构成环路的权值最小的n-1条边构成最小生成树
·会画出用Kruskal算法及Prim算法构造最小生成树的过程
5、单源最短路径
要点：
·采用逐步求解的方式求某一顶点到其他顶点的最短路径
·要求每条边的权值必须大于零
6、活动网络
要点：
·拓扑排序、关键路径、关键活动、AOE网
·拓扑排序将一个偏序图转化为一个全序图。
·为实现拓扑排序，要建立一个栈，将所有入度为零的顶点进栈
·关键路径的计算

第九章 排序
1、基本概念：关键码、初始关键码排列、关键码比较次数、数据移动次数、稳定性、附加存储、内部排序、外部排序
2、插入排序：
要点：
·当待排序的关键码序列已经基本有序时，用直接插入排序最快
3、选择排序：
要点：
·用直接选择排序在一个待排序区间中选出最小的数据时，与区间第一个数据对调，而不是顺次后移。这导致方法不稳定。
·当在n个数据（n很大）中选出最小的5 ~ 8个数据时，锦标赛排序最快
·锦标赛排序的算法中将待排序的数据个数n补足到2的k次幂2k-1<n≤2k
·在堆排序中将待排序的数据组织成完全二叉树的顺序存储。
4、交换排序：
要点：
·快速排序是一个递归的排序方法
·当待排序关键码序列已经基本有序时，快速排序显着变慢。
5、二路归并排序：
要点：
·归并排序可以递归执行
·归并排序需要较多的附加存储。可以采用一种"推拉法"（参见教科书上习题）实现归并排序，算法的时间复杂度为O (n)、空间复杂度为O(1)
·归并排序对待排序关键码的初始排列不敏感，排序速度较稳定
6、外排序
要点：
·多路平衡归并排序的过程、I/O缓冲区个数的配置
·外排序的时间分析、利用败者树进行多路平衡归并
·利用置换选择方法生成不等长的初始归并段
·最佳归并树的构造及WPL的计算

第十章 索引与散列
1、线性索引：
要点：
·密集索引、稀疏索引、索引表计算
·基于属性查找建立倒排索引、单元式倒排表
2、动态搜索树
要点：
·平衡的m路搜索树的定义、搜索算法
·B树的定义、B树与平衡的m路搜索树的关系
·B树的插入（包括结点分裂）、删除（包括结点调整与合并）方法
·B树中结点个数与高度的关系
·B+树的定义、搜索、插入与删除的方法
3、散列表
要点：
·散列函数的比较
·装填因子 a 与平均搜索长度的关系，平均搜索长度与表长m及表中已有数据对象个数n的关系
·解决地址冲突的（闭散列）线性探查法的运用，平均探查次数的计算
·线性探查法的删除问题、散列表类的设计中必须为各地址设置三个状态
·线性探查法中的聚集问题
·解决地址冲突的（闭散列）双散列法的运用，平均探查次数的计算
·双散列法中再散列函数的设计要求与表长m互质，为此m设计为质数较宜
·解决地址冲突的（闭散列）二次散列法的运用，平均探查次数的计算
·注意：二次散列法中装填因子 a 与表长m的设置
·解决地址冲突的（开散列）链地址法的运用，平均探查次数的计算

⑽ 求助有关哈夫曼树的问题！急！满意的答案再加!

哈夫曼树
一、 基本术语
1. 路径与路径长度
若在一棵树中存在一个结点序列 k1, k2, …., kj ，使得kj是kj+1的双亲（1<=i<j），则称结点序列是从k1到kj 的路径（如树中的某个结点到它的某个祖先，或者到它的某个后代的的包括它本身的一系列按顺序的结点序列称为路径），因树中的每个结点只有一个双亲结点，所以这是两个结点间的唯一路径，从k1到kj 所经过的分支数称为这两点之间的路径长度。它等于结点数-1。
如： 从结点A到结点J的结点序
列为A，B，E，J。
路径长度为3。

8 10

4 5 3
2. 结点的权和带权路径长度
如果根据需要给树中的结点赋予一个有某中意义的实数，则称此实数为该结点的权，结点带权路径长度规定为从树根结点到该结点之间的路径长度乘上该结点的权值所得到的乘积。
3. 树的带权路径长度
树的带权路径长度定义为树中所有叶结点的带权路径长度之和，通常记为：
n
WPL=∑ wili wi和li 分别代表叶结点ki的权值和ki到
i=1 根结点的路径长度
例如：上图的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼树
哈夫曼树又称为最优二叉树，它是由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
例如：有四个叶结点a，b，c，d，分别带权为9，4，5，2，可以构成三棵不同的二叉树（当然可以构成更多的二叉树）见下图：

9 4 5 2 WPL=（9+4+5+2）*2=40

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

4

2

5 9
WPL=（9+5）*3+2*2+4*1=50

9

5

4 2
WPL=9*1+5*2+（2+4）*3=37
可以证明最后一棵二叉树是哈夫曼树。
二、 构造哈夫曼树
1. 将n个叶结点构成独立的n棵二叉树，每棵二叉树只有一个根结点。
2. 选择两棵权值最小的二叉树合并成一棵二叉树，并以这两棵二叉树的权值之和作为这棵二叉树的权值，取消原来的两棵二叉树。
3. 重复2，知道只剩一棵二叉树为止。
例如：有6个带权叶结点的权值分别为：3，6，8，5，2，2，构造一棵哈夫曼树，并计算WPL的结果。
1.构造6棵二叉树

3 6 8 5 2 2
2选出两个权值最小的二叉树的组成一棵二叉树

2 2 合并权值为4

3 6 8 5
3 6 8 5 4
2 2
选出两个权值最小的二叉树的组成一棵二叉树

7 6 8 5

3

2 2
选出两个权值最小的二叉树的组成一棵二叉树

7 11 8

3
5 6
2 2
选出两个权值最小的二叉树的组成一棵二叉树

15 11

8
5 6
3

2 2

选出两个权值最小的二叉树的组成一棵二叉树（最终的哈夫曼树）

8
5 6
3

2 2
WPL=（2+2）*4+3*3+（5+6+8）*2=16+9+38=63
作业：P221/9