已知叶子结点的权值集合w=2,2,3,3,5,8 构造哈夫曼树并计算带权路径长度
答案:1 悬赏:60
解决时间 2021-01-15 02:45
- 提问者网友:杀生予夺
- 2021-01-14 13:43
已知叶子结点的权值集合w=2,2,3,3,5,8 构造哈夫曼树并计算带权路径长度
最佳答案
- 二级知识专家网友:迷人又混蛋
- 2021-01-14 15:20
六个权值是 2(0) 2(1) 3(0) 3(1) 5 8
注意: 第一个"2"的顺序在前,所以写成2(0),第二个"2"的顺序在后,所以写成2(1),
同理,两个"3"分别写成3(0),3(1)
(1) 从小到大排序 2(0) 2(1) 3(0) 3(1) 5 8 (这是有序序列)
(2) 每次提取最小的两个结点,取结点2(0)和结点2(1),组成新结点N4,其权值=2+2=4,
取数值较小的结点作为左分支,尽管两个结点的数值一样,但是,
把顺序在前的2(0)作为左分支,而2(1)就作为右分支.
(3) 将新结点N4放入有序序列,保持从小到大排序:
3(0) 3(1) N4 5 8
(4) 重复步骤(2),提取最小的两个结点,结点3(0)与结点3(1)组成新结点N6,其权值=3+3=6,
结点3(0)与结点3(1)的数值一样,但是,结点3(0)的顺序在前,所以,
把结点3(0)作为左分支,而结点3(1)就作为右分支.
(5) 将新结点N6放入有序序列,保持从小到大排序:
N4 5 N6 8
(6) 重复步骤(2),提取最小的两个结点,N4与结点5组成新结点N9,其权值=4+5=9,
N4的数值较小,作为左分支,5就作为右分支.
(7) 将新结点N9放入有序序列,保持从小到大排序:
N6 8 N9
(8) 重复步骤(2),提取最小的两个结点,N6与结点8组成新结点N14,其权值=6+8=14,
N6作为左分支,结点8就作为右分支.
(9) 将新结点N4放入有序序列,保持从小到大排序:
N9 N14
(10)重复步骤(2),提取剩下的两个结点,N9与N14组成新结点N23,其权值=9+14=23,
数值较小的N9作为左分支,N14就作为右分支.
有序序列已经没有结点,最后得到"哈夫曼树":
N23
/
N9 N14
/ /
N4 5 N6 8
/ /
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个整数作为权值:2 2 3 3 5 8
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.
#include
#include
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//1、输出二叉树,可在前序遍历的基础上修改。
// 采用广义表格式,元素类型为int
void PrintBTree_int(struct BTreeNode* 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 个权值建立一棵哈夫曼树,返回树根指针
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
//初始化b指针数组,使每个指针元素指向a数组中对应的元素结点
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
int k1 = -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;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小权值树和次最小权值树建立一棵新树,q指向树根结点
q = malloc(sizeof(struct BTreeNode));
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
return q; //返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0
{
if (FBT == NULL) //空树返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点
{
printf("+ %d * %d ",FBT->data,len);
return FBT->data * len;
}
else //访问到非叶子结点,进行递归调用,
{ //返回左右子树的带权路径长度之和,len递增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼编码(可以根据哈夫曼树带权路径长度的算法基础上进行修改)
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0
{
//定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
static int a[10];
int i;
//访问到叶子结点时输出其保存在数组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);
}
}
}
int main()
{
int n, i;
ElemType* a;
struct BTreeNode* 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);
return 0;
}
注意: 第一个"2"的顺序在前,所以写成2(0),第二个"2"的顺序在后,所以写成2(1),
同理,两个"3"分别写成3(0),3(1)
(1) 从小到大排序 2(0) 2(1) 3(0) 3(1) 5 8 (这是有序序列)
(2) 每次提取最小的两个结点,取结点2(0)和结点2(1),组成新结点N4,其权值=2+2=4,
取数值较小的结点作为左分支,尽管两个结点的数值一样,但是,
把顺序在前的2(0)作为左分支,而2(1)就作为右分支.
(3) 将新结点N4放入有序序列,保持从小到大排序:
3(0) 3(1) N4 5 8
(4) 重复步骤(2),提取最小的两个结点,结点3(0)与结点3(1)组成新结点N6,其权值=3+3=6,
结点3(0)与结点3(1)的数值一样,但是,结点3(0)的顺序在前,所以,
把结点3(0)作为左分支,而结点3(1)就作为右分支.
(5) 将新结点N6放入有序序列,保持从小到大排序:
N4 5 N6 8
(6) 重复步骤(2),提取最小的两个结点,N4与结点5组成新结点N9,其权值=4+5=9,
N4的数值较小,作为左分支,5就作为右分支.
(7) 将新结点N9放入有序序列,保持从小到大排序:
N6 8 N9
(8) 重复步骤(2),提取最小的两个结点,N6与结点8组成新结点N14,其权值=6+8=14,
N6作为左分支,结点8就作为右分支.
(9) 将新结点N4放入有序序列,保持从小到大排序:
N9 N14
(10)重复步骤(2),提取剩下的两个结点,N9与N14组成新结点N23,其权值=9+14=23,
数值较小的N9作为左分支,N14就作为右分支.
有序序列已经没有结点,最后得到"哈夫曼树":
N23
/
N9 N14
/ /
N4 5 N6 8
/ /
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个整数作为权值:2 2 3 3 5 8
//可以得出哈夫曼树的广义表形式,带权路径长度,以及哈夫曼编码.
#include
#include
typedef int ElemType;
struct BTreeNode
{
ElemType data;
struct BTreeNode* left;
struct BTreeNode* right;
};
//1、输出二叉树,可在前序遍历的基础上修改。
// 采用广义表格式,元素类型为int
void PrintBTree_int(struct BTreeNode* 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 个权值建立一棵哈夫曼树,返回树根指针
struct BTreeNode* CreateHuffman(ElemType a[], int n)
{
int i, j;
struct BTreeNode **b, *q;
b = malloc(n*sizeof(struct BTreeNode));
//初始化b指针数组,使每个指针元素指向a数组中对应的元素结点
for (i = 0; i < n; i++)
{
b[i] = malloc(sizeof(struct BTreeNode));
b[i]->data = a[i];
b[i]->left = b[i]->right = NULL;
}
for (i = 1; i < n; i++)//进行 n-1 次循环建立哈夫曼树
{
//k1表示森林中具有最小权值的树根结点的下标,k2为次最小的下标
int k1 = -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;
}
else if (b[j]->data < b[k2]->data)
k2 = j;
}
}
//由最小权值树和次最小权值树建立一棵新树,q指向树根结点
q = malloc(sizeof(struct BTreeNode));
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
return q; //返回整个哈夫曼树的树根指针
}
//3、求哈夫曼树的带权路径长度
ElemType WeightPathLength(struct BTreeNode* FBT, int len)//len初始为0
{
if (FBT == NULL) //空树返回0
return 0;
else
{
if (FBT->left == NULL && FBT->right == NULL)//访问到叶子结点
{
printf("+ %d * %d ",FBT->data,len);
return FBT->data * len;
}
else //访问到非叶子结点,进行递归调用,
{ //返回左右子树的带权路径长度之和,len递增
return WeightPathLength(FBT->left,len+1)+WeightPathLength(FBT->right,len+1);
}
}
}
//4、哈夫曼编码(可以根据哈夫曼树带权路径长度的算法基础上进行修改)
void HuffManCoding(struct BTreeNode* FBT, int len)//len初始值为0
{
//定义静态数组a,保存每个叶子的编码,数组长度至少是树深度减一
static int a[10];
int i;
//访问到叶子结点时输出其保存在数组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);
}
}
}
int main()
{
int n, i;
ElemType* a;
struct BTreeNode* 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);
return 0;
}
我要举报
如以上问答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息,可以点下面链接进行举报!
大家都在看
推荐资讯