‘壹’ 哈夫曼树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) //输出每个元素的哈夫曼编码
‘贰’ 哈夫曼树
这是我们的作业题，自己写 的……（可能输入的格式跟你要的不一致，自己改一下）
如果有什么不懂的就问我，我可以把其中所有相关的文件发给你 ^^
注：1、 初始化创建哈夫曼树有三种选择，其中选择编译课本测试数据时和编译源文件是，调用的输入文件分别是：test.txt和input.txt；字母的哈夫曼编码都保存在文件：hmfTree.txt；
2、 用户自定义模式下，需要编码的文件内容保存在ToBeTran.txt中；课本测试数据和源文件代码分别保存在course.txt和sorse.txt中，在（1）中选择不同的选项，则在编码时调用相应的文件进行编码，编码结果保存在文件CodeFile.txt中。
3、 文件译码时，调用文件CodeFile.txt进行译码，得到的结果保存在文件TextFile.txt中。
4、 打印代码文件：调用CodeFile.txt，结果显示在终端并保存在文件CodePrin.txt中。
5、 打印哈夫曼树：用凹入表形式把哈夫曼树显示在终端，同时将它保存在文件TreePrint..txt中。
#include <stdio.h>
#include<malloc.h>
#include <string.h>
#include<fstream>
#include<iostream>
using namespace std;
typedef struct {
unsigned int weight;
char ch1;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
char ch;
char code[7];
}codenode,*code;
void select(HuffmanTree HT,int n,int & s1,int &s2){ //从哈夫曼树中选择出最小的两个节点
for(int i=1;i<=n;i++)
if(!HT[i].parent){
s1=i; break;
}
for(i++;i<=n;i++)
if(!HT[i].parent){
s2=i; break;
}
if(HT[s1].weight-HT[s2].weight){
int temp; temp=s1; s1=s2; s2=temp;
}
for(i=1;i<=n;i++) //对数组进行遍历，寻找最小的两个节点
if(!HT[i].parent){
if(HT[i].weight<HT[s1].weight){
s2=s1; s1=i;
}
else if(HT[i].weight<HT[s2].weight&&i!=s1)
s2=i;
}
}
void prin(){ //终端输出选择菜单
cout<<"----------------------------------------------------\n\n"
<<" ∣ I---创建哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ E---文件编码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ D---文件译码 ∣\n"
<<" ∣ ∣\n"
<<" ∣ P---打印代码文件 ∣\n"
<<" ∣ ∣\n"
<<" ∣ T---印哈夫曼树 ∣\n"
<<" ∣ ∣\n"
<<" ∣ O---哈夫曼树的存储结构 ∣\n"
<<" ∣ ∣\n"
<<" ∣ Q---退出 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
}
void output (HuffmanTree th,int n){ //输出哈夫曼树的存储结构
int i=0;
cout<<"序号"<<" "<<"字符"<<" "<<"双亲"<<" "<<"左孩子"<<" "<<"右孩子"<<" "<<"权值"<<endl;
for(;i<2*n-1;i++){
th++;
cout<<i<<" "<<th->ch1<<" "<<th->parent<<" "<<th->lchild<<" "<<th->rchild<<" "<<th->weight <<endl;
}
}
void initial(HuffmanTree &HT,HuffmanCode &HC,int w[],int &n,char ch[],int &k){ //创建哈夫曼树
cout<<"----------------------------------------------------\n\n"
<<" ∣ 1---自定义 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 2---编码课本测试数据 ∣\n"
<<" ∣ ∣\n"
<<" ∣ 3---编码源程序 ∣\n"
<<"\n-----------------------------------------------------\n\n";
printf("选择菜单功能选项：");
scanf("%d",&k);
if(k==1){
printf("输入需要编码的字符总数: ");
scanf("%d",&n);
printf("\n输入需要编码字符的权值:\n");
for(int d=0;d<n;d++) {
scanf("%d",&w[d]);
}
printf("\n输入需要编码的字符串: ");
scanf("%s",ch);
}
else if(k==2){
ifstream fin2 ("test.txt");
fin2>>n;
for(int d=0;d<n;d++)
fin2>>w[d];
fin2>>ch;
fin2.close();
}
else if(k==3){
ifstream fin1 ("input.txt");
fin1>>n;
for(int d=0;d<n;d++)
fin1>>w[d];
fin1>>ch;
fin1.close();
}
if(n<=1)
return;
int s1,s2,i,num=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));
for(p=HT+1,i=1;i<=n;i++,p++){
p->weight=w[i-1]; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 =ch[i-1];
}
for(;i<=num;p++,i++){
p->weight=0; p->lchild=0; p->parent=0; p->rchild=0; p->ch1 ='$';
}
for(i=n+1;i<=num;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;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
char * temp=(char *)malloc(n*sizeof(char));
temp[n-1]='\0';
for(i=1;i<=n;i++){
int start=n-1;
for(int f=HT[i].parent,h=i;f;h=f,f=HT[f].parent)
if(HT[f].lchild==h)
temp[--start]='0';
else
temp[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&temp[start]);
}
ofstream fout ("hfmTree.txt");
fout<<ch<<endl;
for(int j=1;j<=n;j++)
fout<<HC[j]<<endl;
fout.close();
free(temp);
}
void encoding(int n,int select){ //编码：对文件TobeTran.txt进行译码
char a[100],b[100][20];
ifstream fin ("hfmTree.txt");
fin>>a;
for(int j=0;j<n;j++) fin>>b[j];
fin.close();
ifstream fin1 ("course.txt");
ifstream fin2 ("sorse.txt");
ifstream fin3 ("ToBeTran.txt");
char s[1000];
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
ofstream fout ("CodeFile.txt");
while(s[0]!='\0'){
for(int i=0;s[i]!='\n'&&s[i]!='\0'&&i<30;i++ ){
for(int g=0;a[g]!=s[i];g++) ;
fout<<b[g];
}
fout<<'\n';
if(select==3)
fin2>>s;
else if(select==2)
fin1>>s;
else fin3>>s;
}
fin3.close();
fin2.close();
fin1.close();
fout.close();
}
void decoding(HuffmanTree ht,int n){ //译码：对CodeFile.txt文件进行译码
ifstream fin ("CodeFile.txt");
ofstream fout ("TextFile.txt");
char s[500];
fin>>s;
HuffmanTree head=ht+2*n-1;
int i=0;
while(s[0]!='\0'){
while(s[i]!='\0'){
if(s[i]=='1') head=ht+head->rchild;
else if(s[i]=='0') head=ht+head->lchild;
if((head->lchild)==0&&(head->rchild) ==0) {
fout<<(head->ch1);
head=ht+2*n-1;
}
i++;
}
fout<<' ' ;
i=0;
fin>>s;
}
fin.close();
fout.close();
}
void Print(){ //打印代码文件，显示在终端，每行50个代码
ifstream fin ("CodeFile.txt");
char s[2000];
int j=0;
int i=1;
fin>>s;
ofstream fout ("CodePrin.txt");
while(s[0]!='\0'){
for(;s[j]!='\0';j++){
printf("%c",s[j]);
fout<<s[j];
if(i%50==0){
fout<<endl;
printf("\n");
}
i++;
}
j=0;
fin>>s;
}
fin.close();
printf("\n");
fout.close();
}
void printTree( HuffmanTree node,HuffmanTree node1, int level ) { //打印哈夫曼树形（在参数的传递上，是文科给自己提出的意见才很好的解决了之后的操作难题^^）
if( node == NULL ) return;
if( node1->rchild!=0) {
printTree( node,node+node1->rchild, level + 1 );
}
fstream fout ;
fout.open ("TreePrint.txt",ios::in | ios::out|ios::ate);//这个挺有用的：在文件末尾加入内容
for( int i = 0; i < level; i++ ) {
fout<<"|……";
printf( "……");
}
fout<<node1->weight<<endl;
printf( "%d\n", node1->weight );
if( node1->lchild!=0 ) {
printTree( node,node+node1->lchild, level + 1 );
}
fout.close();
}
void main(){
int select;
int n;
char ch[100];
int w[100];
HuffmanTree HT=NULL;
HuffmanCode hc=NULL;
prin();
char c='I';
scanf("%c",&c);
while(c!='Q'){
switch(c){
case 'I':
initial(HT,hc,w,n,ch,select);
prin();
break;
case 'E':
encoding(n,select);
prin();
break;
case 'D':
decoding(HT,n);
prin();
break;
case 'P':
Print();
prin();
break;
case 'T':
printTree(HT,HT+2*n-1,1);
prin();
break;
case 'O':
output(HT,n);
prin();
break;
}
scanf("%c",&c);
}
}
注：
input.txt文件中保存一下数据：
88
56
26
89
45
62
78
61
13
20
29
89
46
51
25
86
123
20
10
9
57
6
1
57
62
2
37
61
15
19
89
91
2
8
19
49
67
18
19
64
35
67
61
61
84
20
30
50
84
19
28
84
67
31
67
29
20
10
56
56
12
23
56
23
45
85
16
29
94
68
35
97
58
21
29
3
94
58
16
21
64
29
84
64
59
19
48
37
186
!,./;':[]\1234567890-=+)(*&%$#<>"|{}
‘叁’ 赫夫曼树
注：第一题 huffman 树以及 huffman编码
我将第二题与第三题与用邻接矩阵存储图相关的操作放在了一起完成
第三题则是利用邻接表
1.第一题
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<malloc.h>
#define LEN 8
#define MAXLEAF 6 // 最大叶子结点数目
#define MAXNODE (MAXLEAF*2)-1
typedef float ElemType;
typedef struct /* this structure stores the information of code */
{
int start; /* 存放编码的起始位置右至左（高位至低位）*/
int bit[LEN]; /* 存放 huffman编码 */
}HCode;
typedef HCode HuffCode[MAXLEAF];
typedef struct /* huffman tree结点的结构 */
{
int parent;
int LChild;
int RChild;
ElemType weight;
}HNode;
typedef HNode Huffman[MAXLEAF*2-1];
void createHuffmanTree(Huffman h,int leaves,ElemType *weight)
{
int i,j;
for(i=0;i<leaves*2-1;i++) /* 初始化huffman tree */
{
(h+i)->parent=-1;
(h+i)->LChild=-1;
(h+i)->RChild=-1;
(h+i)->weight=0;
}
for(i=0;i<leaves;i++) /* 给叶子赋权重 */
{
(h+i)->weight=*(weight+i);
}
/* 上一个循环叶子已经带权,下面这个循环用来生成新根
* 新根数量为n-1
*/
for(i=0;i<leaves-1;i++)
{
ElemType m1, m2;
int m1_pos, m2_pos;
m1=m2=65536; /* m1存放最小的权值m2存放次小的权值 */
m1_pos=m2_pos=0; /* m1存放最小的权值对应下标m2存放次小的权值对应下标*/
for(j=0;j<leaves+i;j++)
{
if((h+j)->weight<m1&&(h+j)->parent==-1)
{
m2=m1;
m1=(h+j)->weight;
m2_pos=m1_pos;
m1_pos=j;
}
else if((h+j)->weight<m2&&(h+j)->parent==-1)
{
m2=(h+j)->weight;
m2_pos=j;
}
}
(h+leaves+i)->parent=-1; // 生成新根，无双亲-1
(h+leaves+i)->LChild=m1_pos; // 新根左孩子在数组中的下标
(h+leaves+i)->RChild=m2_pos; // 新根右孩子在数组中的下标
(h+m1_pos)->parent=leaves+i; // 原根的父亲位置
(h+m2_pos)->parent=leaves+i; // 原根的父亲位置
(h+leaves+i)->weight=m2+m1;
}
}
void huffmancode(Huffman h,HuffCode code,int leaves)
{
int i,j,p,c;
HCode hf;
/*从叶子结点开始向上回溯 从而计算出huffman code */
for(i=0;i<leaves;i++)
{
c=i;
p=h[i].parent;
hf.start=LEN-1;
while(p!=-1)
{
if(h[p].LChild==c)
{
hf.bit[hf.start]=0;
}
else
{
hf.bit[hf.start]=1;
}
--hf.start;
c=p;
p=h[c].parent;
}
for(j=hf.start+1;j<LEN;j++)
{
code[i].bit[j]=hf.bit[j];
}
code[i].start=hf.start+1;
}
}
void printhuffmantree(Huffman h,int leaves)
{
int i;
for(i=0;i<leaves*2-1;i++)
{
printf("weight=%-3.2f",h[i].weight);
printf("parent=%-3d",h[i].parent);
printf("LChild=%-3d",h[i].LChild);
printf("RChild=%-3d\n",h[i].RChild);
}
}
void printhuffcode(HuffCode hcode,char characters[])
{
int i,j;
for(i=0;i<strlen(characters);i++)
{
printf("%c的huffman编码:",characters[i]);
for(j=hcode[i].start;j<LEN;j++)
{
printf("%d",hcode[i].bit[j]);
}
printf("\n");
}
}
int main(void)
{
Huffman h;
HuffCode hcode;
char characters[]={"abcdef"}; /* 待编码的字符 */
ElemType weights[]={0.3,0.7,0.4,0.5,0.9,0.1}; /* 字符出现的频率 */
createHuffmanTree(h,strlen(characters),weights);
printhuffmantree(h,strlen(characters));
huffmancode(h,hcode,sizeof(characters));
printhuffcode(hcode,characters);
system("pause");
return 0;
}
2.第二题 代码如下，以及使用说明
例如有如下的图
a->b
/ \
|
c
首先输入顶点与弧的数目
3 2
提示输入顶点
abc
输入弧（弧头弧尾）
ab
ca
那些插入以及删除的操作已经放入主函数
顾回车后可以看到进行相关操作后图的变化
#include<stdio.h>
#include<stdlib.h>
#define MAXVERT 10 // 需要在图中进行插入操作所以设定一个最大值
#define INFINITE 32767
#define ERROR -1
#define FALSE 0
#define OK 1
typedef int ElemType;
enum maritype{DG,UDG,DN,UDN};
typedef struct
{
char vertex[MAXVERT];
ElemType arc[MAXVERT][MAXVERT];
int ArcNum;
int VertexNum;
}adjacentMatrix;
int locate(adjacentMatrix *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->VertexNum;i++)
{
if(G->vertex[i]==v)
{
k=i;
break;
}
}
return(k);
}
void init(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
G->arc[i][j]=0;
}
}
}
void createDN(adjacentMatrix *G)
{
int i,j,k;
char v1,v2,blank;
printf("请输入顶点与弧的数目 \n");
scanf("%d%d",&G->VertexNum,&G->ArcNum);
init(G);
printf("请输入顶点（用字母表示）:\n");
getchar();
for(i=0;i<G->VertexNum;i++)
{
scanf("%c",&G->vertex[i]);
}
getchar();
for(i=0;i<G->ArcNum;i++)
{
printf("请输入弧%d的弧头与弧尾",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
G->arc[j][k]=1;
}
}
int InsertVex(adjacentMatrix *G,char v) /* insert vertex */
{
int i;
if(G->VertexNum>MAXVERT-1)
{
return(FALSE);
}
G->vertex[G->VertexNum++]=v;
for(i=0;i<G->VertexNum;i++)
{
G->arc[i][G->VertexNum-1]=G->arc[G->VertexNum-1][i]=0;
}
return(OK);
}
int InsertAar(adjacentMatrix *G,char v,char w) //插入边
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(FALSE);
}
G->arc[i][j]=1;
return(OK);
}
int DeleteVex(adjacentMatrix *G,char v) //（删除顶点）
{
int i, k;
k=locate(G,v);
if(k==-1)
{
printf("The vertex has not found\n");
return(FALSE);
}
for(i=k;i<G->VertexNum;i++)
{
G->vertex[i]=G->vertex[i+1];
}
--G->VertexNum;
return(OK);
}
int DeleteArc(adjacentMatrix *G,char v,char w)
{
int i,j;
i=locate(G,v);
j=locate(G,w);
if(i==-1||j==-1)
{
return(ERROR);
}
G->arc[i][j]=0;
return(OK);
}
void degree(adjacentMatrix *G)
{
int i, j, odsum, idsum, zero=0;
for(i=0;i<G->VertexNum;i++)
{
odsum=0;
idsum=0;
for(j=0;j<G->VertexNum;j++)
{
odsum+=G->arc[i][j];
idsum+=G->arc[j][i];
}
if(!odsum)
{
++zero;
}
printf("顶点 %c 的出度与入度是",G->vertex[i]);
printf("%3d%3d\n",odsum,idsum);
}
printf("度为0的顶点 %d\n",zero);
}
void print(adjacentMatrix *G)
{
int i,j;
for(i=0;i<G->VertexNum;i++)
{
printf("%8c",G->vertex[i]);
}
printf("\n");
for(i=0;i<G->VertexNum;i++)
{
for(j=0;j<G->VertexNum;j++)
{
if(!j)
{
printf("%c",G->vertex[i]);
}
printf("%8d",G->arc[i][j]);
}
printf("\n");
}
}
int main(void)
{
int k;
char v, w;
adjacentMatrix G;
createDN(&G);
print(&G); // 邻接矩阵打印
degree(&G); // 求所有顶点出度入度 及度为0的点
InsertVex(&G,'f'); // 插入顶点f
InsertAar(&G,'f','c'); // 插入边 fc
degree(&G); // 观察插入边顶点后度的变化
print(&G); // 邻接矩阵打印
DeleteArc(&G,'f','c'); // 删除边 fc
print(&G); // 邻接矩阵打印 观察变化
DeleteVex(&G,'a'); // 删除顶点a
print(&G); // 邻接矩阵打印 观察删除顶点a后变化
system("pause");
return(0);
}
3.使用同上 示例图也如上所画 使用方式也基本一直
按你的要求只输出 顶点的出度入度以及度为0的顶点
#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 10
#define ERROR -1
#define FALSE 0
#define OK 1
typedef char VertexType;
typedef struct ArcNode // 边表的结构
{
int adjvex; // 与顶点相邻接的顶点在表头结点表（图中）的位置
struct ArcNode *nextarc;
}ArcNode;
typedef struct VertexNode // 表头结点表的结构
{
VertexType data;
ArcNode *firstarc;
}VertexNode;
typedef struct // 存放图信息的结构
{
int vexnum, arcnum; // 顶点与弧的数目
VertexNode vertex[MAX_VERTEX_NUM];
}Adjlist;
int locate(Adjlist *G,char v)
{
int i, k=ERROR;
for(i=0;i<G->vexnum;i++)
{
if(G->vertex[i].data==v)
{
k=i;
break;
}
}
return(k);
}
void createDG(Adjlist *G)
{
int i, j, k;
char v1, v2;
ArcNode *s;
printf("输入顶点与弧的数目 \n");
scanf("%d%d",&G->vexnum,&G->arcnum);
getchar();
printf("请输入顶点（用字母表示）:");
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
scanf("%c",&G->vertex[i].data);
G->vertex[i].firstarc=NULL;
}
getchar();
for(i=0;i<G->arcnum;i++)
{
printf("请输入第%d条边的信息 弧尾与弧头:",i+1);
scanf("%c%c",&v1,&v2);
getchar();
j=locate(G,v1);
k=locate(G,v2);
s=(ArcNode *)malloc(sizeof(ArcNode));
s->adjvex=k;
s->nextarc=G->vertex[j].firstarc;
G->vertex[j].firstarc=s;
}
}
void od(Adjlist *G)
{
int odsum, i;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
odsum=0;
p=G->vertex[i].firstarc;
while(p)
{
++odsum;
p=p->nextarc;
}
printf("\n%c的出度是:%d\n ",G->vertex[i].data,odsum);
}
}
void ind(Adjlist *G)
{
int insum, i, j, k;
ArcNode *p;
for(i=0;i<G->vexnum;i++) // 生成表头结点表
{
insum=0;
for(j=0;j<G->vexnum;j++)
{
if(i==j)
{
continue;
}
p=G->vertex[j].firstarc;
while(p)
{
if(p->adjvex==i)
{
++insum;
}
p=p->nextarc;
}
}
printf("\n%c的入度是:%d\n ",G->vertex[i].data,insum);
}
}
int main(void)
{
Adjlist G;
int i;
createDG(&G);
od(&G);
ind(&G);
system("pause");
return(0);
}
‘肆’ 简述哈夫曼树的性质。
哈 夫 曼 树
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所指结点，然后再从原二叉排序树中删去该直接前趋或后继。