哈夫曼树编码一定是左边为0,右边为1吗?

画出一个二叉树,可如下：
o
/
O o
/
O o
/
O o
/
O O
这不是很明显的事吗?如果根的高度从0开始计,则该树树高为4,如果根的高度从1开始计,则该树高度为5.再怎么也不会是3啊.

d

哈夫曼树是没有度数为1的分支结点的二叉树.
哈夫曼树一般情况下共有2n-1个结点
2n-1=9
n=5
选B

首先1与2结合生出3节点,再选剩下的3与刚生成的3结合生出6节点,剩下的4,5都小于6,所以4,5结合生出9节点,最后9和6结合为根节点.
1的路径000
2的路径001
3的路径01
4的路径10
5的路径11

算上N个叶子的话一共2N-1个.参见定理：0度结点（即叶子）数比2度结点数多1.另外Huffman树中没有1度结点.

只有带权路径长度最小的二叉树,才是哈夫曼树.当然是可以证明带权路径长度最小

//在吗？ 我给你。另外我有自己的实验报告。
//里面有递归遍历，有迭代遍历。可以写文件，可以压缩编码。可以读文件。
//你不需要什么功能的话就删去相应的函数就行了。
//希望加分。
#include
#include
#include
#include
using namespace std;
const int maxlen = 10000; //结点最大数目
const int maxlen2 = 260; //字符最大数目，叶节点最大数目
const int maxchar = 260; //字符最大数目
#define INTMAX 10000000; //大数，大于任意一个权值
struct CharSet //程序初始化时保存字符和结点的结构体。
{
char ch;
int weight;
};
struct HaffNode //哈夫曼树结点结构
{
int weight,parent,lchild,rchild;
char ch;
HaffNode() {weight=0; parent=lchild=rchild=-1; ch='n';}
};
struct HaffCode //哈夫曼树字符编码信息结构
{
unsigned int bit; //通过位运算，用一个无符号整形来表示一串二进制编码。
int startb; //记录偏移量。
int weight;
char ch;
HaffCode() { bit=0; startb = -1; weight=0; ch='n';}
HaffCode& operator=(HaffCode & obj) //重载赋值符号
{
bit=obj.bit; startb=obj.startb;
ch=obj.ch; weight=obj.weight;
return *this;
}
};
class HaffmanSystem
{
private:
CharSet cs[maxlen/2]; //保存初始化时的字符和权值信息。
HaffNode hn[maxlen]; //保存哈夫曼树结点信息。
HaffCode hc[maxlen/2]; //保存哈夫曼树字符编码信息。
HaffCode hc2[maxchar]; //索引散列。考虑到字符数少，以字符的十进制数作为下标保存和索引字符编码信息，时间为O(1);
int head; //根结点的数组下标。
int n;
int leafnum; //叶节点个数，字符个数。
public:
HaffmanSystem() {n=head=leafnum=0;}
void Haffman(); //哈夫曼树生成函数。
void InitisLization(); //初始化，调用Haffman();
void Encoding(); //对文件"ToBeTran"进行编码。
void Decoding(); //对文件"CodeFile"译码。
void Print(); //印代码至屏幕。
static void TreePrinting(int pos,int i,int child_flag,HaffmanSystem * p,ofstream & fop);
void TreePrinting(); //输出哈夫曼树图形到屏幕和文件，其中要调用静态实例函数完成递归功能。
void TreeFromFile(); //从文件中获取哈夫曼树。
};
void HaffmanSystem::InitisLization()
{
cout

50
21 29
11 10 15 14
5 6 7 8
2 3
上图为树,
所以带权路径长度为 2x4+3x4+6x3+10x2+7x3+8x3+14x2=131

这还不够细?
3+5=8,此时序列为8 7 8 12 18 26 32
7+8=15,此时序列为15 8 12 18 26 32
8+12=20,此时序列为15 20 18 26 32
……每一步都挑最小的两个相加.
图见下面.
多看书,baidu上不好画图,打这些东西很累.
------------------
原答题者：plause
按权值大小排列后 3 5 7 8 12 18 26 32
只要按照将最小的两个合并, 合并后的值再入列中(最小的两个出列), 至到列中只有一个值.
按上面要求构造哈夫曼树如下:
/////树列完后, 可取左树编码 为0, 右为 1, (左为 1, 右为 0 亦可)
[3]`````[5]`````````[7]``````[8]
```````/```````````````````/
`0````/`1```````````0`````/`1
`````/```````````````````/
````(8)`````[12]````````(15)`````[18]
````````````/```````````````````/
`````0`````/`1```````````0`````/`1
``````````/```````````````````/
````````(20)``````[26]```````(33)``````[32]
`````````````````/```````````````````/
``````````0`````/`1```````````0`````/`1
```````````````/```````````````````/
`````````````(46)`````````````````(65)
`````````````````````````````````/
```````````````0````````````````/`1
```````````````````````````````/
```````````````````````(111)
则按上面的树可得到各权值所对应的编码:
//// 其编码是从树顶到该权值点所经过的 1 或 0 的序列
[`7]:``1`0`0`0
[18]:``1`0`1
[`3]:``0`0`0`0
[32]:``1`1
[`5]:``0`0`0`1
[26]:``0`1
[12]:``0`0`1
[`8]:``1`0`0`1

第1次必定是2个叶子组成二叉树,产生1新结点,接下来有2种情况：
1.此新结点与原剩下的叶子再组成二叉树又产生1新结点,这样就只有第1次时由2个叶子产生1新结点,以后每次由1叶子与新结点产生新结点,故n个叶子共有2n-1个结点.
2.剩下的叶子中又有2个叶子(比第1次产生的新结点权小)结合产生新结点,其它类似,那么必然会由2个都是新结点再产生新结点,所以实际上数量与第1种一样,共有2n-1个.

步骤：
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空.（为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列.）
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和.
三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中.
四、重复二和三两步,直到集合F中只有一棵二叉树为止.
简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率（即权值）分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3!

将8个权值赋给8个字符,这是程序运行后的哈夫曼树：

填空题
1.2的k-1次幂
2.根
3.中续
4.(log2n)+1
5.链式存储
6.最小
7.n-1
8.5
9.每个顶点的访问次数
10.任意
单选
1.B
2.D
3.C
4.B
5.A
6.A
7.B
8.B
9.B
10...

选出权值最小的两个相加得到新的结点,将原来的两个去掉,将新的结点放入w中依此类催

33
18 15
9 9 7 8
4 5
2 3
WPL=2*7+2*8+2*9+3*4+3*2+3*3=75

不一样,上机实验的时候基本得出的都是左边的
建议你多看看书,多做做实验,实验中很快就能明白.

带权路径=6*2+5*2+4*2+3*3+2*3=45

编译哈夫曼树的广义表表示为27（11（5c,6(2d,4a)),16(7b,9e)),5种字符a、b、c、d、e的哈夫曼编码依次为011、10、00、010、11

243
/
145 98
/ /
61 84 43 55
/ /
34 27 20 23
/
15 19
/
1 14
WPL=(84+55)*2+(27+20+23)*3+19*4+(1+14)*5=639

最小的两个值合起来还是最小的情况,生成的结点最多. 每次合成,生成一个结点,即共有n-1+n=2n-1个.

带权的路径长度WPL=3*4+4*4+7*3+14*2+15*2+20*2

设给定一个权值集合W=(3,5,7,9,11),要求根据给定的权值集合构造一棵哈夫曼树
夫曼树的构造：
（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn},其中Ti中只有一个权值为wi的根结点,左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树,且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和.
（3）将新的二叉树加入到F中,删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止,这棵树就是哈夫曼树.
哈夫曼.bmp (134.99 KB)
2008-8-5 17:55
以上图片是过程
最后的树是这样：
35
20 15
9 11 7 8
3 5
wpl=3*3 5*3 7*2 9*2 11*2=78
本文来自:冠威计算机网(

构建哈夫曼树的步骤：
1,选取结点（node）中最小的两个,相加,构成一个新结点
2,重复第一步,直至所有结点都在同一个树型里面.
所以,大概构成后就是这样
.81
.0/ 1
./
.31 50
.0/ 1 0/1
./ /
.18 13 20 30
.0/ 1 0/ 1
./ /
.7 11 5 8
.0/ 1
./
.3 4
从最下面向上读,node3和node4是初始数据里面最小的两个,
它们组成一个新结点7,
然后再重复相同的步骤,在新数据里面,7和11是最小,他们组成18,
原始数据里面的18可以消去.
重复步骤直至所有结点在同一个树型里面
现在看看
3的哈夫曼编码就是0000,而数字最大的30编码就是11

哈夫曼树的形状如下：
24
/
11 13
/
6 7
/
2 5
带权路径长度=(2+5)*3+6*2+11*1=44

哈夫曼树如下：
106
/
63 43
/ /
29 34 20 23
/ / / /
14 15 16 18 10 10 11 12
/ /
6 8 9 9
/
4 5
/
2 3
WPL=361

给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman tree).

1, T->lchild == NULL && T->rchild == NULL //叶节点
2, n + T->weight * h //加上当前叶节点的带权路径长度
3, WPL(T->lchild, h+1) //遍历左子树
4, WPL(T->rchild, h+1) //遍历右子树

B D B B B B
B A B B A
B B B B A
A B B

哈夫曼树的叶子结点总比内结点多一个,不信可以试一下,画个图.

真不容易啊,给你查出问题了.是申请和释放内存出错了.

把
free(cd);

放在 第二个for循环的外面即可.
#include
#include
#include
#define MAXSIZE 30
#define MAX 100
using namespace std;
typedef struct
{
char data;
int weight;
int parent;
int left;
int right;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct
{
char data;
int weight;
} Tdata;
HuffmanTree HT;
HuffmanCode HC;
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2);
void HuffmanCoding(HuffmanTree HT,Tdata *w,int n);
void SelectMinTree(HuffmanTree HT,int n,int *s1,int *s2)
{
int i,min1,min2;
*s2=*s1=0;
min1=min2=MAX;
for(i=1; iparent=0;
}
for(; iweight=0;
p->left=0;
p->right=0;
p->parent=0;
}
for(i=n+1; i>>>>>>>>>>>>>>>>>
}
int main()
{
Tdata w[MAXSIZE];
int n,i;
cout>n;
for(i=1; i>w[i].data>>w[i].weight;
}
cout

（2+4）*3+5*2+7*1=35

WPL=（2+3）*4+（6+7+8）*3+（10+14）*2=131
树的结点总数：14
如下图：

abcdef是五个字符么?只考虑前五个是ecabc

因为第一组,编码“0”是编码“00”的前缀,在译码的时候遇到两个0不知道应该译成“0”+“0”还是“00”,而后面则没有这个问题,没有任何一个编码是另一个编码的前缀

#include
#include
int n;
int m=2*n-1;

struct tree
{
float weight;
int parent;
int lch,rch;
};
struct codetype
{
int bits[100];
int start;
char ch;
};
tree hftree[100];
codetype code[99];
void creathuffmantree(int n,int m)
{

int i,j ,p1,p2;
float s1,s2;
for(i=1;i

16*2+17*2+14*3+15*3+9*3+6*4+2*5+3*5=229

B

对的

WPL = 45,可能会出现生成的Huffman树高度不一样的,但是这个wpl唯一

哈夫曼树没有度为1的结点
你仔细想想 如果有度为1的结点 就不可能称之为最优二叉树 也就不是哈夫曼树
画个图试试就明白了

我会.
选择两个最小的5,7叶子节点构成一个二叉树,该二叉树的根节点的权重为5+7=12.
同理认为12是一个叶子节点,选出最小的两个10,12构成一个二叉树,权重为22.
依次类推,直到无叶子节点.
因此,最终的答案是 根节点85,左子树33,右子树52. 33的左子树14（叶子节点d）,右子树19（叶子节点e）.52的左子树22,右子树30（叶子节点f）.22的左子树10（叶子节点b）,右子树12.12的左子树5（叶子节点a）,右子树7（叶子节点c）.
左子树的编码为0 右子树编码为1
a的编码是1010
b的编码是100
c的编码是1011
d的编码是00
e的编码是01
f 的编码是11

哈夫曼树：
100
/
36 64
/ /
A17 B19 29 F35
/
E13 16
/
D6 C10
带权路径长度：（17+19 + 35）*2 + 13*3 + （6+10）*4 = 245
哈夫曼编码是
A：00 B：01 C：1011 D：1010 E：100 F：11
如果有疑问,可以追问.

答:问题一4,5,6,7,10,12,15,18,23
6,7,9,10,12,15,18,23
9,10,12,13,15,18,23
12,13,15,18,19,23
15,18,19,23,25
19,23,25,33
25,33,42
42,58
100

二叉树定义：二叉树(BinaryTree)是n(n≥0)个结点的有限集,它或者是空集(n=0),或者由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树组成.
注意,如果子树是两棵那就要求两棵子树不相交,AB都存在这个问题不选；同时二叉树要求是有序的,D不能满足这个要求也不选；哈夫曼树就是按二叉树构造出来的,必须是二叉树

哈夫曼树如下:
(24)
(10) (14)
(5) 5 6 8
2 3
带权路径长度为 2*3 + 3*3 +5*2 +6*2 +8*2 = 53

从大到小排列,然后将最小的两项相加,始终是最小的两项相加,加到最后就OK啦···