⑴ 简述哈夫曼树的性质。
哈 夫 曼 树
2.9 二叉树的应用
2.9.1 哈夫曼树及应用
哈夫曼树又称最优树（二叉树），是一类带权路径最短的树。构造这种树的算法最早是由哈夫曼(Huffman)1952年提出，这种树在信息检索中很有用。
结点之间的路径长度：从一个结点到另一个结点之间的分支数目。
树的路径长度：从树的根到树中每一个结点的路径长度之和。
结点的带权路径长度：从该结点到树根之间的路径长度与结点上权的乘积。
树的带权路径长度：树中所有叶子结点的带权路径长度之和，记作：
WPL为最小的二叉树就称作最优二叉树或哈夫曼树。
完全二叉树不一定是最优二叉树。
哈夫曼树的构造：
（1）根据给定的n个权值{w1,w2,...,wn}构造n棵二叉树的集合F={T1,T2,...,Tn}，其中Ti中只有一个权值为wi的根结点，左右子树为空；
（2）在F中选取两棵根结点的权值为最小的数作为左、右子树以构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。
（3）将新的二叉树加入到F中，删除原两棵根结点权值最小的树；
（4）重复（2）和（3）直到F中只含一棵树为止，这棵树就是哈夫曼树。
例1：
例2：
结点的存储结构:
构造哈夫曼树的算法说明：
#define n /* 叶子总数 */
#define m 2*n-1 /* 结点总数 */
证：由性质3，叶子结点数 n0=n2+1，故哈夫曼树结点总数为 n0+n2=n0+(n0-1)=2*n0-1
例3 在解某些判定问题时，利用哈夫曼树获得最佳判定算法。
（a)
WPL=0.05*1+0.15*2+0.4*3+0.3*4+0.1*4=3.15
（b)(c)
WPL=0.4*1+0.3*2+0.15*3+0.05*4+0.1*4=2.05 WPL=0.05*3+0.15*3+0.4*2+0.3*2+0.1*2=2.2
哈夫曼编码
从哈夫曼树根结点开始，对左子树分配代码“0”，右子树分配代码“1”，一直到达叶子结点为止，然后将从树根沿每条路径到达叶子结点的代码排列起来，便得到了哈夫曼编码。
例，对电文 EMCAD 编码。若等长编码，则
EMCAD => 000001010011100 共15位
设各字母的使用频度为 {E,M,C,A,D}={1,2,3,3,4}。用频度为权值生成哈夫曼树，并在叶子上标注对应的字母，树枝分配代码“0”或“1”:
各字母的编码即为哈夫曼编码： EMCAD => 000001011011 共12位
2.9.2 二叉排序树
二叉排序树是一种特殊结构的二叉树，它作为一种表的组织手段，通常被称为树表。可以作为一种排序和检索的手段。
定义 二叉排序树或是空树，或是具有下述性质的二叉树：其左子树上所有结点的数据值均小于根结点的数据值；右子树上所有结点的数据值均大于或等于根结点的数据值。左子树和右子树又各是一棵二叉排序树。
对二叉排序树，若按中序遍历就可以得到由小到大的有序序列。如上图，中序遍历得：
{2，3，4，8，9，9，10，13，15，18}
二叉排序树的生成
对任意一组数据元素序列{R1,R2,...,Rn}，要生成一棵二叉排序树的过程为：
（1）令R1为二叉树的根；
（2）若R2<R1，令R2为R1左子树的根结点，否则R2为R1右子树的根结点；
（3）对R3,...,Rn结点的插入方法同上。
例，数据元素序列{10，18，3，8，12，2，7，3}，其生成二叉排序树的过程如下：
二叉排序树中结点的删除
要求删除一个结点后的二叉树仍是一棵二叉排序树。算法思想，分以下几种情况考虑：
（1）被删除的结点是叶子结点，则只需修改其双亲结点的指针既可；
（2）被删除结点p只有左子树pL或右子树pR，此时只要使左子树pL或右子树pR成为p双亲结点q的左子树或右子树即可。
（3）若被删除结点p的左、右子树均非空，有两种做法：
*
令pL直接链接到q的左（或右）孩子链域上，pR链接到p结点中序前趋结点s上（s是pL最右下的结点）；
*
以p结点的直接中序前趋或后继替代p所指结点，然后再从原二叉排序树中删去该直接前趋或后继。
⑵ 关于哈夫曼编码试题的计算
太复杂了，楼主一会记得多给我点分！谢谢啦！
先设权w=(31,22,18,14,10,4,1),n=7,则m=13,按照哈夫曼算法可以构造一棵哈夫曼树如下：
100
40 60
22 18 31 29
14 15
10 5
4 1
末端结点为22，18，31，14，10，4，1，你自己把上面的加上线连成一棵二叉树就行，记得左分支标0，右分支标1（为了得出后面的哈夫曼编码HC）
然后需要列出HT初态表和HT终态表，如下：
HT初态表 HT终态表
weight parent lchild rchild weight parent lchild rchild
1 31 0 0 0 31 12 0 0
2 22 0 0 0 22 11 0 0
3 18 0 0 0 18 11 0 0
4 14 0 0 0 14 10 0 0
5 10 0 0 0 10 9 0 0
6 4 0 0 0 4 8 0 0
7 1 0 0 0 1 8 0 0
8 - 0 0 0 5 9 6 7
9 - 0 0 0 15 10 5 8
10 - 0 0 0 29 12 4 9
11 - 0 0 0 40 13 2 3
12 - 0 0 0 60 13 1 10
13 - 0 0 0 100 0 11 12
最后得出哈夫曼编码HC：
1——>10
2——>00
3——>01
4——>110
5——>1110
6——>11110
7——>11111
平均码字长度为（0.31＋0.22＋0.18）×2＋0.14×3＋0.1×4
＋（0.04＋0.01）×5＝2.47
编码效率为[（1－0.01）×3＋0.01×2]/2.47=1.21
解答完毕！
补充：对于其中的编码效率问题本人有点淡忘，我选择的是用
普通平均编码长度除上了哈夫曼平均编码长度得出，不知对否。
辛苦半天，望楼主能赐我分数，不胜感激！
注：提交后发现格式不太规整，对于哈夫曼树谁是谁的左孩子、右孩子比较容易分出（左右孩子结点相加可知父亲结点），对于HT初态表和HT终态表1列1列的看就行！其中数字第一列为序号，从第2列到第9列分别对应HT初态表的weight parent lchild rchild 和HT终态表的weight parent lchild rchild 。
⑶ 数据结构树和二叉树的实际应用
数据结构树和二叉树的实际应用：哈夫曼编码。
利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。
从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求出各字符的哈夫曼编码。
要求：输出存放哈夫曼树的数组HT的初态和终态；输出每个字符的哈夫曼编码；输入由上述若干字符组成的字符串，对电文进行编码并输出；输入电文的哈夫曼编码，进行译码并输出。
在计算机科学中，树是用来模拟具有树状结构性质的数据集合。它是由n（n>=0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。(n = 0 时称为空树)
特点有：每个节点有零个或多个子节点；没有父节点的节点称为根节点；每一个非根节点有且只有一个父节点；除了根节点外，每个子节点可以分为多个不相交的子树。
二叉树的性质：
二叉树的第ii层至多拥有2i−12i−1个节点数, ii>=1)；
深度为 kk的二叉树至多总共有 2k−12k−1 个节点数,(kk>=1)；
对任何一棵非空的二叉树TT，如果其叶片(终端节点)数为 n0n0，分支度为22的节点数为 n2n2，则 n0=n2+1。
(3)哈夫曼树ht存储结构初态和终态扩展阅读：
树状图由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：
每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；
单个结点是一棵树，树根就是该结点本身。
设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称T1,T2,..,Tk为结点n的子树。
空集合也是树，称为空树。空树中没有结点。
⑷ 什么是哈夫曼树呢
夫曼树是带权路径长度最小的二叉树，用途是平均查找信息的代价最小。
普通二叉树的用途也普通，比较通用，就是信息存储和查找。
普通二叉树可能有的只有一个子节点，而哈夫曼树一定有两个。
⑸ 哈夫曼树HT存储结构的初态和末态怎么写
定义哈夫曼树与编码的存储结构与数据类型
typedef struct
{
char data;//节点值
int weight; //权重
int parent; //双亲节点
int lchild; //左孩子节点
int rchild; //右孩子节点
} HTNode;
typedef struct
{
char cd[N]; //存放哈夫曼码
int start;
} HCode;
void CreateHT(HTNode ht[],int n) //创建哈夫曼树
void CreateHCode(HTNode ht[],HCode hcd[],int n) //根据哈夫曼树计算每个元素的哈夫曼编码
void DispHCode(HTNode ht[],HCode hcd[],int n) //输出每个元素的哈夫曼编码
⑹ 哈夫曼树的构造是什么
哈夫曼树构造：结构化的Huffman算法生成的Huffman树子树都是有序的，所以一般生成Huffman树时都为节点排序，即使这样结果也不唯一。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
历史
1951年，哈夫曼在麻省理工学院（MIT）攻读博士学位，他和修读信息论课程的同学得选择是完成学期报告还是期末考试。
导师罗伯特·法诺（Robert Fano）出的学期报告题目是：查找最有效的二进制编码。由于无法证明哪个已有编码是最有效的，哈夫曼放弃对已有编码的研究，转向新的探索，最终发现了基于有序频率二叉树编码的想法，并很快证明了这个方法是最有效的。
哈夫曼使用自底向上的方法构建二叉树，避免了次优算法香农-范诺编码（Shannon–Fano coding）的最大弊端──自顶向下构建树。
1952年，于论文《一种构建极小多余编码的方法》（A Method for the Construction of Minimum-Rendancy Codes）中发表了这个编码方法。
⑺ 哈夫曼树的建立
。。作业吧，运行可用，自己再试试。
//huffman_h.h 哈夫曼树的头文件
#include"iostream.h"
#include "stdio.h"
#include "stdlib.h"
#include "string.h"
typedef char ElemType;
typedef struct{
ElemType elem;
unsigned int weight;
unsigned int parent,lchild,rchild,tag;
}HTNode,*HuffmanTree;
typedef char** HuffmanCode;
typedef int Status;
typedef struct weight
{
char elem;
unsigned int m_weight;
}Weight; // 保存符号信息;
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int i;
s1=s2=0;
for(i=1;i<=n;i++){
if(HT[i].weight<HT[s2].weight&&HT[i].parent==0&&s2!=0){
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
}
if((s1==0||s2==0)&&HT[i].parent==0){
if(s1==0) s1=i;
else if(s2==0) {
if(HT[i].weight<HT[s1].weight) {
s2=s1; s1=i; }
else s2=i;
} // end of else if
if(s1>s2) {i=s1; s1=s2; s2=i;}
// end of if
// end of for
}
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, Weight* &w, int n) {
// w存放n个字符的权值(均>0)，构造哈夫曼树HT，
// 并求出n个字符的哈夫曼编码HC
//本函数实现选择方式：从左往右选择两个小权值结点，结点信息在前面的为左子树，其后为右子树
//修改选择方式：依序选择两个小权值结点，权值小的为左子树。！！
int i, j, m, s1,s2;
char *cd;
int p;
int cdlen;
if (n<=1) return;
m = 2 * n - 1;
HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号单元未用
for (i=1; i<=n; i++) { //初始化
HT[i].elem=w[i-1].elem;
HT[i].weight=w[i-1].m_weight;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for (i=n+1; i<=m; i++) { //初始化
HT[i].weight=0;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
printf("\n哈夫曼树的构造过程如下所示：\n");
printf("HT初态:\n 结点 weight parent lchild rchild");
for (i=1; i<=m; i++)
printf("\n%4d%8d%8d%8d%8d",i,HT[i].weight,
HT[i].parent,HT[i].lchild, HT[i].rchild);
printf(" 按任意键，继续 ...");
getchar();
for (i=n+1; i<=m; i++) { // 建哈夫曼树
// 在HT[1..i-1]中选择parent为0且weight最小的两个结点，
// 其序号分别为s1和s2。
Select(HT, i-1, s1, s2);
HT[s1].parent = i; HT[s2].parent = i;
HT[i].lchild = s1; HT[i].rchild = s2;
HT[i].weight = HT[s1].weight + HT[s2].weight;
printf("\nselect: s1=%d s2=%d\n", s1, s2);
printf(" 结点 weight parent lchild rchild");
for (j=1; j<=i; j++)
printf("\n%4d%8d%8d%8d%8d",j,HT[j].weight,
HT[j].parent,HT[j].lchild, HT[j].rchild);
printf(" 按任意键，继续 ...");
getchar();
}//for
//------无栈非递归遍历哈夫曼树，求哈夫曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
cd = (char *)malloc((n+1)*sizeof(char)); // 分配求编码的工作空间
p = m; cdlen = 0;
for (i=1; i<=m; ++i) // 遍历哈夫曼树时用作结点状态标志
HT[i].tag = 0;
while (p) {
if (HT[p].tag==0) { // 向左
HT[p].tag = 1;
if (HT[p].lchild != 0) { p = HT[p].lchild; cd[cdlen++] ='0'; }
else if (HT[p].rchild == 0) { // 登记叶子结点的字符的编码
HC[p] = (char *)malloc((cdlen+1) * sizeof(char));
cd[cdlen] ='\0'; strcpy(HC[p], cd); // 复制编码(串)
}
} else if (HT[p].tag==1) { // 向右
HT[p].tag = 2;
if (HT[p].rchild != 0) { p = HT[p].rchild; cd[cdlen++] ='1'; }
} else { // HT[p].weight==2，退回退到父结点，编码长度减1
HT[p].tag = 0; p = HT[p].parent; --cdlen;
}//else
}//while
} // HuffmanCoding
/*
//--- 从叶子到根逆向求每个字符的哈夫曼编码 ---
cd = (char *)malloc(n*sizeof(char)); // 分配求编码的工作空间
cd[n-1] = '\0'; // 编码结束符。
for (i=1; i<=n; ++i) { // 逐个字符求哈夫曼编码
start = n-1; // 编码结束符位置
for (c=i, f=HT[i].parent; f!=0; c=f, f=HT[f].parent)
// 从叶子到根逆向求编码
if (HT[f].lchild==c) cd[--start] = '0';
else cd[--start] = '1';
HC[i] = (char *)malloc((n-start)*sizeof(char));
// 为第i个字符编码分配空间
strcpy(HC[i], &cd[start]); // 从cd复制编码(串)到HC
}
free(cd); // 释放工作空间
*/
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---element---weight---huffman code\n");
for(i=1;i<=n;i++)
printf(" %d %c %d %s\n",i,HT[i].elem,HT[i].weight,HC[i]);
}
//主函数
//huffman.cpp
#include"huffman_h.h"
void main()
{
HuffmanTree HT;
HuffmanCode HC;
Weight *w;
char c; // the symbolizes;
int i,n; // the number of elements;
int wei; // the weight of a element;
printf("请输入构建哈夫曼树的结点数:" );
cin>>n; //cout<<endl;
w=(Weight *)malloc(n*sizeof(Weight));
for(i=0;i<n;i++)
{
//cout<<"请输入第"<<i+1<<"个结点编号及其权值（如a 100）:"<<endl;
printf("请输入结点编号及其权值（如a 100）:" );
scanf("%1s%d",&c,&wei);
w[i].elem=c;
w[i].m_weight=wei;
}
HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
}
⑻ 数据结构 请问那个终态图中 parent lchild rchild 这三行数据是怎样算出来的。。。
typedef struct
{unsigned int weight;
unsigned int parent,lchild,rchild;
}htnode,*huffmantree;
typedef char *huffmantree;
算法：
huffmantree crt_huffmantree(int *w,int n)
{huffmantree ht;
m=2*n-1;
ht=(huffmantree)malloc((m+1)*sizeof(htnode));
for(p=ht,i=1;i<=n;i++,p++,w++)
*p={*w,0,0,0};
for(;i<=m;i++,p++)
*p={0,0,0,0};
for(i=n+1;i<=m;i++)
{select(ht,i-1,s1,s2);
ht[s1].parent=i;
ht[s2].parent=i;
ht[i].lchild=s1;
ht[i].rchild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
}
return ht;
}
带权路径长度：
w=(3+6+7+8)*4+(9+10+16+17)*3+24*2=300
(8)哈夫曼树ht存储结构初态和终态扩展阅读：
构成初始集合
对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的升序排列。）
选取左右子树
在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。
⑼ Huffman编码，存储结构的终结状态是什么意思怎么来的
哈夫曼树 在一般的数据结构的书中，树的那章后面，着者一般都会介绍一下哈夫曼(HUFFMAN)树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。