㈠ 哈夫曼树的结点总个数一定是偶数吗
不是，哈夫曼节点总数一定是奇数。
除叶子节点外，其他节点都有左右子节点，再加上根节点，所以是奇数
㈡ 对于给定的一组权值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;
}
㈢ 我们有个数据结构的哈夫曼编码解码的课程设计，你能帮帮我吗
树和哈夫曼树实验报告
一．实验目的
练习树和哈夫曼树的有关操作，和各个算法程序，理解哈夫曼树的编码和译码
二．实验环境
Microsoft visual c++
三．实验问题描述
1. 问题描述：建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
基本要求：从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立），并将此二叉树按照“树状形式”打印输出，然后对其进行遍历（先序、中序和后序），最后将遍历结果打印输出。在遍历算法中要求至少有一种遍历采用非递归方法。
测试数据：
ABCØØDEØGØØFØØØ（其中Ø表示空格字符）
输出结果为：
先序：ABCDEGF
先序：CBEGDFA
先序：CGEFDBA
2. 问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接受端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站写一个哈夫曼码的编/译码系统。
基本要求：(至少完成功能1-2）
一个完整的系统应具有以下功能：
I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。
基本要求：
E：编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。
D：译码（Decoding )。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。
P：印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。
T：印哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。
测试数据：
设权值w=（5，29，7，8，14，23，3，11），n=8。
按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：
5：0001，29：11，7：1110，8：1111
14：110，23：01，3：0000，11：001
用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”。
四．实验主要程序流
实验题目一主要程序：
1．
void CreatBiTree(BitTree *bt)//用扩展先序遍历序列创建二叉树，如果是#当前树根置为空，否则申请一个新节点//
{
char ch;
ch=getchar();
if(ch=='.')*bt=NULL;
else
{
*bt=(BitTree)malloc(sizeof(BitNode));
(*bt)->data=ch;
CreatBiTree(&((*bt)->LChild));
CreatBiTree(&((*bt)->RChild));
}
}
2．void Visit(char ch)//访问根节点
{
printf("%c ",ch);
}
3．
void PreOrder(BitTree root)
{
if (root!=NULL)
{
Visit(root ->data);
PreOrder(root ->LChild);
PreOrder(root ->RChild);
}
}
4． void InOrder(BitTree root)
{
if (root!=NULL)
{
InOrder(root ->LChild);
Visit(root ->data);
InOrder(root ->RChild);
}
}
5．int PostTreeDepth(BitTree bt) //后序遍历求二叉树的高度递归算法//
{
int hl,hr,max;
if(bt!=NULL)
{
hl=PostTreeDepth(bt->LChild); //求左子树的深度
hr=PostTreeDepth(bt->RChild); //求右子树的深度
max=hl>hr?hl:hr; //得到左、右子树深度较大者
return(max+1); //返回树的深度
}
else return(0); //如果是空树，则返回0
}
6．void PrintTree(BitTree Boot,int nLayer) //按竖向树状打印的二叉树 //
{
int i;
if(Boot==NULL) return;
PrintTree(Boot->RChild,nLayer+1);
for(i=0;i<nLayer;i++)
printf(" ");
printf("%c\n",Boot->data);
PrintTree(Boot->LChild,nLayer+1);
}
7．void main()
{
BitTree T;
int h;
int layer;
int treeleaf;
layer=0;
printf("请输入二叉树中的元素(以扩展先序遍历序列输入,其中.代表空子树):\n");
CreatBiTree(&T);
printf("先序遍历序列为:");
PreOrder(T);
printf("\n中序遍历序列为:");
InOrder(T);
printf("\n后序遍历序列为:");
PostOrder(T);
h=PostTreeDepth(T);
printf("\此二叉树的深度为:%d\n",h);
printf("此二叉树的横向显示为：\n");
PrintTree(T,layer);
}
实验二主要程序流：
1．int main(){
HuffmanTree huftree;
char Choose;
while(1){
cout<<"\n**********************欢迎使用哈夫曼编码/译码系统**********************\n";
cout<<"*您可以进行以下操作: *\n";
cout<<"*1.建立哈夫曼树 *\n";
cout<<"*2.编码(源文已在文件ToBeTra中，或键盘输入) *\n";
cout<<"* 3.译码(码文已在文件CodeFile中) *\n";
cout<<"* 4.显示码文 *\n";
cout<<"* 5.显示哈夫曼树 *\n";
cout<<"* 6.退出 *\n"; cout<<"***********************************************************************\n";
cout<<"请选择一个操作:";
cin>>Choose;
switch(Choose)
{
case '1':
huftree.CreateHuffmanTree();
break;
case '2':
huftree.Encoder();
break;
case '3':
huftree.Decoder();
break;
case '4':
huftree.PrintCodeFile();
break;
case '5':
huftree.PrintHuffmanTree();
break;
case '6':
cout<<"\n**********************感谢使用本系统!*******************\n\n";
system("pause");
return 0;
}//switch
}//while
}//main
2．// 建立哈夫曼树函数
// 函数功能：建立哈夫曼树（调用键盘建立哈夫曼树或调用从文件建立哈夫曼树的函数）
void HuffmanTree::CreateHuffmanTree()
{char Choose;
cout<<"你要从文件中读入哈夫曼树(按1)，还是从键盘输入哈夫曼树(按2)？";
cin>>Choose;
if(Choose=='2') { //键盘输入建立哈夫曼树 CreateHuffmanTreeFromKeyboard();
}//choose=='2'
else { //从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
}
}
3. // 从键盘建立哈夫曼树函数
// 函数功能：从键盘建立哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromKeyboard(){
int Num;
cout<<"\n请输入源码字符集个数：";
cin>>Num;
if (Num<=1) {
cout<<"无法建立少于2个叶子结点的哈夫曼树。\n\n";
return;
}
LeafNum=Num;
Node=new HuffmanNode[2*Num-1];
for(int i=0;i<Num;i++) {//读入哈夫曼树的叶子结点信息
cout<<"请输入第"<<i+1<<"个字符值";
getchar();
Node[i].sourcecode=getchar(); //源文的字符存入字符数组Info[]
getchar();
cout<<"请输入该字符的权值或频度";
cin>>Node[i].weight; //源文的字符权重存入Node[].weight
Node[i].parent=-1;
Node[i].lchild=-1;
Node[i].rchild=-1;
Node[i].code="\0";
}
for(int j=Num;j<2*Num-1;j++) {//循环建立哈夫曼树内部结点
int pos1,pos2;
int max1,max2;
pos2=pos1=j;
max2=max1=numeric_limits<int>::max( );
//在所有子树的根结点中，选权重最小的两个根结点，pos1最后应指向权重最小的根结点的下标
//pos2最后应指向权重第二小的根结点的下标
//max1存放当前找到的权重最小的根结点的权重
//max2存放当前找到的权重第二小的根结点的权重
for(int k=j-1;k>=0;k--) {
if (Node[k].parent==-1){//如果是某棵子树的根结点
if (Node[k].weight<max1){ //发现比当前最大值还大的权重
max2=max1;
max1=Node[k].weight;
pos2=pos1;
pos1=k;
}
else
if(Node[k].weight<max2){ //发现比当前次大值还大的次大权重
max2=Node[k].weight;
pos2=k;
}
}//if (Node[j].parent==-1)
} //for
//在下标i处新构造一个哈夫曼树的内部结点，其左、右孩子就是以上pos1、pos2所指向的结点
Node[pos1].parent=j;
Node[pos2].parent=j;
Node[j].lchild=pos1;
Node[j].rchild=pos2;
Node[j].parent=-1;
Node[j].weight=Node[pos1].weight+Node[pos2].weight;
} //for
//产生所有叶子结点中字符的编码
for (int m=0;m<Num;m++) {
//产生Node[i].sourcecode的编码，存入Node[i].code中
int j=m;
int j1;
while(Node[j].parent!=-1) { //从叶结点开始往根结点走，每往上走一层，就产生一位编码存入code[]
j1=Node[j].parent;
if(Node[j1].lchild==j)
Node[m].code.insert(0,"0");
else
Node[m].code.insert(0,"1");
j=j1; }}
cout<<"哈夫曼树已成功构造完成。\n";
//把建立好的哈夫曼树写入文件hfmTree.dat
char ch;
cout<<"是否要替换原来的哈夫曼树文件(Y/N):";
cin>>ch;
if (ch!='y'&&ch!='Y') return;
ofstream fop;
fop.open("hfmTree.dat",ios::out|ios::binary|ios::trunc); //打开文件
if(fop.fail()) {
cout<<"\n哈夫曼树文件打开失败，无法将哈夫曼树写入hfmTree.dat文件。\n";
return;
}
fop.write((char*)&Num,sizeof(Num)); //先写入哈夫曼树的叶子结点个数
for(int n=0;n<2*Num-1;n++) { //最后写入哈夫曼树的各个结点（存储在Node[]中）
fop.write((char*)&Node[n],sizeof(Node[n]));
flush(cout); }
fop.close(); //关闭文件
cout<<"\n哈夫曼树已成功写入hfmTree.dat文件。\n";}
4. // 从文件建立哈夫曼树函数
// 函数功能：从文件建立哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::CreateHuffmanTreeFromFile(){
ifstream fip;
fip.open("hfmTree.dat",ios::binary|ios::in);
if(fip.fail()) {
cout<<"哈夫曼树文件hfmTree.dat打开失败，无法建立哈夫曼树。\n";
return;
}
fip.read((char*)&LeafNum,sizeof(LeafNum));
if (LeafNum<=1) {
cout<<"哈夫曼树文件中的数据有误，叶子结点个数少于2个，无法建立哈夫曼树。\n";
fip.close();
return;
}
Node=new HuffmanNode[2*LeafNum-1];
for(int i=0;i<2*LeafNum-1;i++)
fip.read((char*)&Node[i],sizeof(Node[i]));
fip.close();
cout<<"哈夫曼树已从文件成功构造完成。\n";
}
5. // 编码函数
// 函数功能：为哈夫曼树编码
//函数参数：无
//参数返回值：无
void HuffmanTree::Encoder()
{
if(Node==NULL) { //内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}//if
char *SourceText; //字符串数组，用于存放源文
//让用户选择源文是从键盘输入，还是从源文文件ToBeTran.txt中读入
char Choose;
cout<<"你要从文件中读入源文(按1)，还是从键盘输入源文(按2)？";
cin>>Choose;
if(Choose=='1') {
ifstream fip1("ToBeTran.txt");
if(fip1.fail()) {
cout<<"源文文件打开失败!无法继续执行。\n";
return;
}
char ch;
int k=0;
while(fip1.get(ch)) k++; //第一次读文件只统计文件中有多少个字符，将字符数存入k
fip1.close();
SourceText=new char[k+1]; //申请存放源文的字符数组空间
ifstream fip2("ToBeTran.txt"); //第二次读源文文件，把内容写入SourceText[]
k=0;
while(fip2.get(ch)) SourceText[k++]=ch;
fip2.close();
SourceText[k]='\0';
}
else { //从键盘输入源文
string SourceBuff;
cin.ignore();
cout<<"请输入需要编码的源文(可输入任意长，按回车键结束):\n";
getline(cin,SourceBuff,'\n');
int k=0;
while(SourceBuff[k]!='\0')
k++;
SourceText=new char[k+1];
k=0;
while(SourceBuff[k]!='\0') {
SourceText[k]=SourceBuff[k];
k++;
}
SourceText[k]='\0';
}
cout<<"需编码的源文为：";
cout<<SourceText<<endl;
//开始译码
ofstream fop("CodeFile.dat",ios::trunc); //打开码文存放文件
int k=0;
while(SourceText[k]!='\0') //源文串中从第一个字符开始逐个编码
{
int i;
for(i=0;i<LeafNum;i++){ //找到当前要编码的源文的字符在哈夫曼树Node[]中的下标
if(Node[i].sourcecode==SourceText[k]) { //将对应编码写入码文文件
fop<<Node[i].code;
break;
};
}
if (i>=LeafNum) {
cout<<"源文中存在不可编码的字符。无法继续执行。\n"<<endl;
fop.close();
return;
}
k++; //源文串中的字符后移一个
}
fop.close();
cout<<"已完成编码，码文已写入文件CodeFile.dat中。\n\n";
}
6. // 译码函数
// 函数功能：对哈夫曼树进行译码
//函数参数：无
//参数返回值：无
void HuffmanTree::Decoder()
{//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return;
}
}
//将码文从文件CodeFile.dat中读入 CodeStr[]
ifstream fip1("CodeFile.dat");
if(fip1.fail()) {
cout<<"没有码文，无法译码。\n";
return;
}
char* CodeStr;
int k=0;
char ch;
while(fip1.get(ch)){
k++;
}
fip1.close();
CodeStr=new char[k+1];
ifstream fip2("CodeFile.dat");
k=0;
while(fip2.get(ch))
CodeStr[k++]=ch;
fip2.close();
CodeStr[k]='\0';
cout<<"经译码得到的源文为：";
ofstream fop("TextFile.dat");
int j=LeafNum*2-1-1; //j指向哈夫曼树的根
int i=0; //码文从第一个符号开始，顺着哈夫曼树由根下行，按码文的当前符号决定下行到左孩子还是右孩子
while(CodeStr[i]!='\0') { //下行到哈夫曼树的叶子结点处，则译出叶子结点对应的源文字符
if(CodeStr[i]=='0')
j=Node[j].lchild;
else
j=Node[j].rchild;
if(Node[j].rchild==-1) { //因为哈夫曼树没有度为1的结点，所以此条件等同于Node[j]为叶结点
cout<<Node[j].sourcecode; //屏幕输出译出的一个源文字符
fop<<Node[j].sourcecode;
j=LeafNum*2-1-1; //j再指向哈夫曼树的根
}
i++;
}
fop.close();
cout<<"\n译码成功且已存到文件TextFile.dat中。\n\n";
}
7. // 输出码文函数
// 函数功能：从文件中输出哈夫曼树的码文
//函数参数：无
//参数返回值：无
void HuffmanTree::PrintCodeFile()
{
char ch;
int i=1;
ifstream fip("CodeFile.dat");
ofstream fop("CodePrin.dat");
if(fip.fail())
{
cout<<"没有码文文件，无法显示码文文件内容。\n";
return;
}
while(fip.get(ch))
{cout<<ch;
fop<<ch;
if(i==50)
{
cout<<endl;
fop<<endl;
i=0;
}
i++;
}
cout<<endl;
fop<<endl;
fip.close();
fop.close();
}
8. // 输出函数
// 函数功能：从内存或文件中直接输出哈夫曼树
//函数参数：无
//参数返回值：无
void HuffmanTree::PrintHuffmanTree()
{
//如果内存没有哈夫曼树，则从哈夫曼树文件hfmTree.dat中读入信息并建立哈夫曼树
if(Node==NULL)
{
CreateHuffmanTreeFromFile();
if (LeafNum<=1) {
cout<<"内存无哈夫曼树。操作撤销。\n\n";
return; }}
ofstream fop("TreePrint.dat",ios_base::trunc);
fop.close();
PrintHuffmanTree_aoru(2*LeafNum-1-1);
return;
}
㈣ 二叉树遍历演示
四、 遍历二叉树 二叉树是一种非线性的数据结构，在对它进行操作时，总是需要逐一对每个数据元素实施 操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作。所谓遍历二叉树就 是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比 较、更新、查看元素内容等等各种操作。
二叉树的遍历方式分为两大类：一类按根、左子树和右子树三个部分进行访问；另一类按 层次访问。下面我们将分别进行讨论。
1、 按根、左子树和右子树三部分进行遍历 遍历二叉树的顺序存在下面6种可能： TLR（根左右）, TRL（根右左） LTR（左根右）, RTL（右根左） LRT（左右根）, RLT（右左根） 其中，TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树，这与人们先左后右的习惯不同，因此，往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。（1）先序遍历若二叉树为空，则结束遍历操作；否则访问根结点；先序遍历左子树；先序遍历右子树。（2）中序遍历若二叉树为空，则结束遍历操作；否则中序遍历左子树；访问根结点；中序遍历右子树。（3）后序遍历若二叉树为空，则结束遍历操作；否则后序遍历左子树；后序遍历右子树；访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法：（1）对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列
（2）任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来，我们将它称为二叉树的包线，这条包线对于理解二叉树的遍历过程很有用。 由此可以看出：（1）遍历操作实际上是将非线性结构线性化的过程，其结果为线性序列，并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列；（2）遍历操作是一个递归的过程，因此，这三种遍历操作的算法可以用递归函数实现。（1）先序遍历递归算法
void PreOrder(BTree BT) {
if (BT) { Visit(BT);
PreOrder(BT->Lchild);
PreOrder(BT->Rchild);
}（2）中序遍历递归算法
void InOrder(BTree BT) {
if (BT) {
InOrder(BT->Lchild);
Visit(BT);
InOrder(BT->Rchild);
}
}（3）后序遍历递归算法
void PostOrder(BTree BT) {
if (BT) {
PostOrder(BT->Lchild);
PostOrder(BT->Rchild);
Visit(BT);
}
} 2 、按层次遍历二叉树 实现方法为从上层到下层，每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。
void LevelOreder(QBTree BT) {
for (i=1;i<=BT.n;i++)
if (BT.elem[i]!='#') Visite(BT.elem[i]);
}二叉树用链式存储结构表示时，按层遍历的算法实现访问过程描述如下：访问根结点，并将该结点记录下来；若记录的所有结点都已处理完毕，则结束遍历操作；否则重复下列操作。取出记录中第一个还没有访问孩子的结点，若它有左孩子，则访问左孩子，并将记录下来；若它有右孩子，则访问右孩子，并记录下来。 在这个算法中，应使用一个队列结构完成这项操作。所谓记录访问结点就是入队操作； 而取出记录的结点就是出队操作。这样一来，我们的算法就可以描述成下列形式：（1）访问根结点，并将根结点入队；（2）当队列不空时，重复下列操作：从队列退出一个结点；若其有左孩子，则访问左孩子，并将其左孩子入队；若其有右孩子，则访问右孩子，并将其右孩子入队；void LevelOrder(BTree *BT) {
if (!BT) exit;
InitQueue(Q); p=BT; //初始化
Visite(p); EnQueue(&Q,p); //访问根结点，并将根结点入队
while (!QueueEmpty(Q)) { //当队非空时重复执行下列操作
DeQueue(&Q,&p); //出队
if (!p->Lchild) {Visite(p->Lchild);EnQueue(&Q,p->Lchild); //处理左孩子<br> if (!p->Rchild) {Visite(p->Rchild);EnQueue(&Q,p->Rchild); //处理右孩子<br> }
}
五、典型二叉树的操作算法 1、 输入一个二叉树的先序序列，构造这棵二叉树 为了保证唯一地构造出所希望的二叉树，在键入这棵树的先序序列时，需要在所有空二叉 树的位置上填补一个特殊的字符，比如，'#'。在算法中，需要对每个输入的字符进行判 断，如果对应的字符是'#'，则在相应的位置上构造一棵空二叉树；否则，创建一个新结 点。整个算法结构以先序遍历递归算法为基础，二叉树中结点之间的指针连接是通过指针 参数在递归调用返回时完成。算法：BTree Pre_Create_BT( ) {
getch(ch);
if (ch=='#') return NULL; //构造空树
else { BT=(BTree)malloc(sizeof(BTLinklist)); //构造新结点
BT->data=ch;
BT->lchild =Pre_Create_BT( ); //构造左子树
BT->rchild =Pre_Create_BT( ); //构造右子树
return BT;
}
} 2、 计算一棵二叉树的叶子结点数目 这个操作可以使用三种遍历顺序中的任何一种，只是需要将访问操作变成判断该结点是否 为叶子结点，如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法：void Leaf(BTree BT,int *count) {
if (BT) {
Leaf(BT->child,&count); //计算左子树的叶子结点个数
if (BT->lchild==NULL&&BT->rchild==NULL) (*count)++;
Leaf(BT->rchild,&count); //计算右子树的叶子结点个数
}
} 3、 交换二叉树的左右子树 许多操作可以利用三种遍历顺序的任何一种，只是某种遍历顺序实现起来更加方便一 些。而有些操作则不然，它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法：void change_left_right(BTree BT) {
if (BT) {
change_left_right(BT->lchild);
change_left_right(BT->rchild);
BT->lchild<->BT->rchild;
}
} 4 、求二叉树的高度 这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树 的高度，在此基础上得出该棵树的高度，即左右子树较大的高度值加1。算法：int hight(BTree BT) { //h1和h2分别是以BT为根的左右子树的高度
if (BT==NULL) return 0;
else {
h1=hight(BT->lchild);
h2=hight(BT->right);
return max{h1,h2}+1;
}
} 六、树、森林与二叉树的转换 1、 树、森林转换成二叉树 将一棵树转换成二叉树的方法： 将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可，此时，树中的每个结点最多有两个指针：一个指针指向第一个孩子，另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时，就是一棵二叉树了。 特点：一棵树转换成二叉树后，根结点没有右孩子。 将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似，只是把森林中所有树的根 结点看作兄弟关系，并对其中的每棵树依依地进行转换。 2 、二叉树还原成树或森林 这个过程实际上是树、森林转换成二叉树的逆过程，即将该二叉树看作是树或森林的孩子兄弟表示法。比如，若二叉树为空，树也为空；否则，由二叉树的根结点开始，延右指针向下走，直到为空，途经的结点个数是相应森林所含树的棵数；若某个结点的左指针非空，说明这个结点在树中必有孩子，并且从二叉树中该结点左指针所指结点开始，延右指针向下走，直到为空，途经的结点个数就是这个结点的孩子数目。
第 3 节 哈夫曼树及其应用 1、哈夫曼树的定义及特点
在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是：没有度为1的结点。
2、构造哈夫曼树的过程：
（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。 例如： 假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。
它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713．判定树 在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着 程序的执行效率。例如，编制一个程序，将百分制转换成五个等级输出。大家可能认为 这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad");
else if (socre<70) printf("pass");
else if (score<80) printf("general");
else if (score<90) printf("good");
esle printf("very good"); 在实际应用中，往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况：
4．前缀编码 在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两 个原则：（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；（2）发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。
（1）等长编码 这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位 数）。假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性，但编码长度并不是最短的。（2）不等长编码 在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。例如，可以为A，B，C，D四个字符分别分配0，00，1，01，并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符，每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}，现以此为例设计哈夫曼编码。
哈夫曼编码设计过程为：
（1）为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到{5,29,7,8,14,23,3,11}；
（2）以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图5-27所示；
（3）由此哈夫曼树生成哈夫曼编码，如图5-28所示。
最后得出每个字符的编码为：比如，发送一段编码：0000011011010010， 接收方可以准确地通过译码得到：⑥⑥⑦⑤②⑧。
㈤ 带权9.1.3.5.6的五个叶子生成的哈夫曼树，带权路径长度怎么算
五个叶子的权值是91356
(1)将权值从小到大排序后是13569(这是有序序列)
(2)每次提取最小的两个节点,取节点1和节点3,组成新节点N4,其权值=1+3=4,
节点1的数值较小,作为左分支,节点3就作为右分支.
(3)将新节点N4放入有序序列,保持从小到大排序:
N4569(节点1和3已经提取掉)
(4)重复步骤(2),提取最小的两个节点,N4与节点5组成新节点N9,其权值=4+5,
N4的数值较小,作为左分支,节点5就作为右分支.
(5)将新节点N9放入有序序列,保持从小到大排序:
69N9(注意,要将新节点N9排在后,如果顺序是6N99则会有不同的结果)
(6)重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树":
N24
/
N9N15
//
N4569
/
13
根节点N24到节点9的路径长度是2,节点9的带权路径长度是9*2
根节点N24到节点6的路径长度是2,节点6的带权路径长度是6*2
如此类推,可以得出其它节点的带权路径长度.
所以,哈夫曼树的带权路径长度WPL等于
9*2+6*2+5*2+3*3+1*3=52
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根节点N24到节点9,先后经历两次右分支,节点9的编码就是11
从根节点N24到节点6,先经历右分支,再经历左分支,节点6的编码就是10
从根节点N24到节点5,先经历左分支,再经历右分支,节点5的编码就是01
如此类推,可以得出所有的节点的"哈夫曼编码":
权值9:11
权值6:10
权值5:01
权值3:001
权值1:000
//C语言测试程序
//输入构造哈夫曼树中带权叶子结点数n：5
//输入5个整数作为权值：91356
//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码.
#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;
}
㈥ 1、建立二叉树，并进行先序、中序和后序遍历。 2、求二叉树的深度及叶子结点的个数。 3、构造哈夫曼树及哈
0是初始节点数
输入时请一次性输完ABCффDEфGффFффф在按ENTER键 不要输入一个按一下
#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //结点的最大个数
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定义二叉树的结点类型
typedef BinTNode *BinTree; //定义二叉树的指针
int NodeNum,leaf; //NodeNum为结点数，leaf为叶子数
//==========基于先序遍历算法创建二叉树==============
//=====要求输入先序序列，其中加入虚结点"#"以示空指针的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //读入#，返回空指针
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成结点
T->data=ch;
T->lchild=CreatBinTree(); //构造左子树
T->rchild=CreatBinTree(); //构造右子树
return(T);
}
}
//========NLR 先序遍历=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //访问结点
Preorder(T->lchild); //先序遍历左子树
Preorder(T->rchild); //先序遍历右子树
}
}
//========LNR 中序遍历===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍历左子树
printf("%c",T->data); //访问结点
Inorder(T->rchild); //中序遍历右子树
}
}
//==========LRN 后序遍历============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //后序遍历左子树
Postorder(T->rchild); //后序遍历右子树
printf("%c",T->data); //访问结点
}
}
//=====采用后序遍历求二叉树的深度、结点数及叶子数的递归算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求结点数
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度为0，即为叶子。
return(max+1);
}
else return(0);
}
//====利用"先进先出"（FIFO）队列，按层次遍历二叉树==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定义结点的指针数组cq
cq[1]=T; //根入队
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出队
printf("%c",p->data); //出队，输出结点的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子树入队
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子树入队
}
}
}
//==========主函数=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //输入完全二叉树的先序序列，
// 用#代表虚结点，如ABD###CE##F##
root=CreatBinTree(); //创建二叉树，返回根结点
do { //从菜单中选择遍历方式，输入序号。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t5: Level Depth\n"); //先判断节点数是否已有。不用再先选择4，求出该树的结点数。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //输入菜单序号（0-5）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍历
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍历
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍历
break;
case 4: depth=TreeDepth(root); //求树的深度及叶子数
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按层次遍历
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}
㈦ 计算哈夫曼编码
六个权值(频率)是0.040.060.130.250.280.33
(1)从小到大排序0.040.060.130.250.280.33(这是有序序列)
(2)每次提取最小的两个结点,取结点0.04和结点0.06,组成新结点N0.10,其权值=0.04+0.06=0.10,
取数值较小的结点作为左分支,结点0.04为左分支,结点0.06为右分支.
(3)将新结点N0.10放入有序序列,保持从小到大排序:
N0.100.130.250.280.33
(4)重复步骤(2),提取最小的两个结点,N0.10与结点0.13组成新结点N0.23,其权值=0.10+0.13=0.23,
N0.10的数值较小,作为左分支,结点0.13就作为右分支.
(5)将新结点N0.23放入有序序列,保持从小到大排序:
N0.230.250.280.33
(6)重复步骤(2),提取最小的两个结点,N0.23与结点0.25组成新结点N0.48,其权值=0.23+0.25=0.48,
N0.23的数值较小,作为左分支,结点0.25就作为右分支.
(7)将新结点N0.48放入有序序列,保持从小到大排序:
0.280.33N0.48
(8)重复步骤(2),提取最小的两个结点,结点0.28与结点0.33组成新结点N0.61,其权值=0.28+0.33=0.61,
结点0.28的数值较小,作为左分支,结点0.33就作为右分支.
(9)将新结点N0.61放入有序序列,保持从小到大排序:
N0.48N0.61
(10)重复步骤(2),提取剩下的两个结点,N0.48与N0.61组成新结点N1.09,其权值=0.48+0.61=1.09,
数值较小的N0.48作为左分支,N0.61就作为右分支.
有序序列已经没有结点,得到"哈夫曼树":
N1.09
/
N0.48N0.61
//
N0.230.250.280.33
/
N0.100.13
/
0.040.06
带权路径长度(WPL):
根结点N1.09到结点0.33的路径长度是2,结点0.33的带权路径长度是0.33*2
根结点N1.09到结点0.28的路径长度是2,结点0.28的带权路径长度是0.28*2
根结点N1.09到结点0.25的路径长度是2,结点0.25的带权路径长度是0.25*2
根结点N1.09到结点0.13的路径长度是3,结点0.13的带权路径长度是0.13*3
根结点N1.09到结点0.06的路径长度是4,结点0.06的带权路径长度是0.06*4
根结点N1.09到结点0.04的路径长度是4,结点0.04的带权路径长度是0.04*4
所以,哈夫曼树的带权路径长度(WPL)等于
0.33*2+0.28*2+0.25*2+0.13*3+0.06*4+0.04*4=2.51
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N1.09到结点0.33,先后经历两次右分支,结点0.33的编码就是11
从根结点N1.09到结点0.28,先经历右分支,后经历左分支,结点0.28的编码就是10
从根结点N1.09到结点0.25,先经历左分支,后经历右分支,结点0.25的编码就是01
从根结点N1.09到结点0.13,先经历两次左分支,后经历右分支,结点0.13的编码就是001
从根结点N1.09到结点0.06,先经历三次左分支,后经历右分支,结点0.06的编码就是0001
从根结点N1.09到结点0.04,先后经历四次左分支,结点0.04的编码就是0000
得出所有结点的"哈夫曼编码":
字符f(频率0.33):11
字符e(频率0.28):10
字符d(频率0.25):01
字符c(频率0.13):001
字符b(频率0.06):0001
字符a(频率0.04):0000
//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：6
//输入6个整数作为权值：4613252833(将频率的小数形式改为整数形式)
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.
#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;
}
㈧ 已知叶子结点的权值集合w=2,2,3,3,5,8 构造哈夫曼树并计算带权路径长度
六个权值是2(0)2(1)3(0)3(1)58
注意:第一个"2"的顺序在前,所以写成2(0),第二个"2"的顺序在后,所以写成2(1),
同理,两个"3"分别写成3(0),3(1)
(1)从小到大排序2(0)2(1)3(0)3(1)58(这是有序序列)
(2)每次提取最小的两个结点,取结点2(0)和结点2(1),组成新结点N4,其权值=2+2=4,
取数值较小的结点作为左分支,尽管两个结点的数值一样,但是,
把顺序在前的2(0)作为左分支,而2(1)就作为右分支.
(3)将新结点N4放入有序序列,保持从小到大排序:
3(0)3(1)N458
(4)重复步骤(2),提取最小的两个结点,结点3(0)与结点3(1)组成新结点N6,其权值=3+3=6,
结点3(0)与结点3(1)的数值一样,但是,结点3(0)的顺序在前,所以,
把结点3(0)作为左分支,而结点3(1)就作为右分支.
(5)将新结点N6放入有序序列,保持从小到大排序:
N45N68
(6)重复步骤(2),提取最小的两个结点,N4与结点5组成新结点N9,其权值=4+5=9,
N4的数值较小,作为左分支,5就作为右分支.
(7)将新结点N9放入有序序列,保持从小到大排序:
N68N9
(8)重复步骤(2),提取最小的两个结点,N6与结点8组成新结点N14,其权值=6+8=14,
N6作为左分支,结点8就作为右分支.
(9)将新结点N4放入有序序列,保持从小到大排序:
N9N14
(10)重复步骤(2),提取剩下的两个结点,N9与N14组成新结点N23,其权值=9+14=23,
数值较小的N9作为左分支,N14就作为右分支.
有序序列已经没有结点,最后得到"哈夫曼树":
N23
/
N9N14
//
N45N68
//
2(0)2(1)3(0)3(1)
带权路径长度(WPL):
根结点N23到结点8的路径长度是2,结点8的带权路径长度是8*2
根结点N23到结点5的路径长度是2,结点3的带权路径长度是5*2
根结点N23到结点3(0)的路径长度是3,结点3(0)的带权路径长度是3*3
根结点N23到结点3(1)的路径长度是3,结点3(1)的带权路径长度是3*3
根结点N23到结点2(0)的路径长度是3,结点2(0)的带权路径长度是2*3
根结点N23到结点2(1)的路径长度是3,结点2(1)的带权路径长度是2*3
所以,哈夫曼树的带权路径长度(WPL)等于
8*2+5*2+3*3+3*3+2*3+2*3=56
哈夫曼编码:
规定哈夫曼树的左分支代表0,右分支代表1.
从根结点N23到结点8,先后经历两次右分支,结点8的编码就是11
从根结点N23到结点5,先经历左分支,后经历右分支,结点5的编码就是01
从根结点N23到结点3(0),先经历右分支,后经历两次左分支,结点3(0)的编码就是100
从根结点N23到结点3(1),先经历右分支,后经历左分支,最后经历右分支,结点3(1)的编码就是101
从根结点N23到结点2(0),先后经历三次左分支,结点2(0)的编码就是000
从根结点N23到结点2(1),先经历两次左分支,最后经历右分支,结点2(1)的编码就是001
得出所有结点的"哈夫曼编码":
权值8:11
权值5:01
权值3(0):100
权值3(1):101
权值2(0):000
权值2(1):001
//C语言测试程序(来自其他网友)
//
//输入构造哈夫曼树中带权叶子结点数(n)：6
//输入6个整数作为权值：223358
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.
#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;
}