求带权路径长度
五个叶子的权值是 9 1 3 5 6(1) 将权值从小到大排序后是 1 3 5 6 9 (这是有序序列)(2) 每次提取最小的两个节点,取节点1和节点3,组成新节点N4,其权值=1+3=4, 节点1的数值较小,作为左分支,节点3就作为右分支.(3) 将新节点N4放入有序序列,保持从小到大排序: N4 5 6 9 (节点1和3已经提取掉)(4) 重复步骤(2),提取最小的两个节点,N4与节点5组成新节点N9,其权值=4+5, N4的数值较小,作为左分支,节点5就作为右分支.(5) 将新节点N9放入有序序列,保持从小到大排序: 6 9 N9 (注意,要将新节点N9排在后,如果顺序是 6 N9 9 则会有不同的结果)(6) 重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树": N24 / \ N9 N15 / \ / \ N4 5 6 9 / \ 1 3根节点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个整数作为权值:9 1 3 5 6//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码.#include#includetypedef int ElemType;struct BTreeNode{ ElemType data; struct BTreeNode* left; struct BTreeNode* right;};//1、输出二叉树,可在前序遍历的基础上修改。// 采用广义表格式,元素类型为intvoid 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 data = a[i]; b[i]->left = b[i]->right = NULL; } for (i = 1; i data data) { k2 = k1; k1 = j; } else if (b[j]->data 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 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;}
七个权值3 3 7 7 11 13 17(1) 从小到大排序 3 3 7 7 11 13 17 (这是有序序列)(2) 每次提取最小的两个节点,取节点3和另一个节点3,组成新节点N6,其权值=3+3=6, 取数值较小的节点作为左分支,两个权值都是3,一个为左分支,另个为右分支.(3) 将新节点N6放入有序序列,保持从小到大排序: N6 7 7 11 13 17 (两个节点3已经提取掉)(4) 重复步骤(2),提取最小的两个节点,N6与节点7组成新节点N13,其权值=6+7=13, N6的数值较小,作为左分支,节点7就作为右分支.(5) 将新节点N13放入有序序列,保持从小到大排序: 7 11 13 N13 17 (注意,要将新节点N13排在节点13的后面)(6) 重复步骤(2),提取最小的两个节点,节点7与节点11组成新节点N18,其权值=7+11=18, 节点7的数值较小,作为左分支,节点11就作为右分支.(7) 将新节点N18放入有序序列,保持从小到大排序: 13 N13 17 N18(8) 重复步骤(2),提取最小的两个节点,节点13与N13组成新节点N26,其权值=13+13=26, 节点13作为左分支,N13就作为右分支.(9) 将新节点N26放入有序序列,保持从小到大排序: 17 N18 N26(10)重复步骤(2),完成剩下的节点,最后,得到"哈夫曼树": N61 / \ N26 N35 / \ / \ 13 N13 17 N18 / \ / \ N6 7 7 11 / \ 3 3根节点N61到节点17的路径长度是2,节点17的带权路径长度是17*2根节点N61到节点13的路径长度是2,节点13的带权路径长度是13*2根节点N61到节点11的路径长度是3,节点11的带权路径长度是11*3如此类推,可以得出其它节点的带权路径长度.所以,哈夫曼树的带权路径长度WPL等于17*2 + 13*2 + 11*3 + 7*3 + 7*3 + 3*4 + 3*4 = 159哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根节点N61到节点17,先经历右分支,再经历左分支,节点6的编码就是10从根节点N61到节点13,先后经历两次左分支,节点13的编码就是00从根节点N61到节点11,先后经历三次右分支,节点11的编码就是111如此类推,可以得出所有的节点的"哈夫曼编码":权值17: 10权值13: 00权值11: 111权值 7: 011权值 7: 110权值 3: 0100权值 3: 0101//C语言测试程序//输入构造哈夫曼树中带权叶子结点数n:7//输入5个整数作为权值:17 13 11 7 7 3 3//可以得出哈夫曼树的带权路径长度,以及哈夫曼编码.#include#includetypedef int ElemType;struct BTreeNode{ ElemType data; struct BTreeNode* left; struct BTreeNode* right;};//1、输出二叉树,可在前序遍历的基础上修改。// 采用广义表格式,元素类型为intvoid 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 data = a[i]; b[i]->left = b[i]->right = NULL; } for (i = 1; i data data) { k2 = k1; k1 = j; } else if (b[j]->data 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 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;}
先建立哈夫曼树
(33)
(10) (23)
(5) 5 9 14
2 3
带权路劲长度为每一层权值*(层数-1)的总和
(2+3)*3+(5+9+14)*2=71详细概念和解释可去百科查看
根据哈夫曼树的原理(即最优二叉树):WPL = 9 * 2 + 5*3 + 3*4 + 2*4 = 53
树的路径长度
树路径长度是一个通信信息科学术语,是从根结点到某结点的边数 最优二叉树。树的带权路径长度(Weighted Path Length of Tree,简记为WPL)。节点的权为在一些应用中,赋予树中节点的一个有某种意义的实数。节点地带权路径长度为结点到树根之间的路径长度与该节点上权的乘积。树地带权路径长度(Weighted...
哈夫曼树的带权路径长度怎么求
哈夫曼树的带权路径长度算法如下:1.将w1、w2、?,wn看成是有n棵树的森林(每棵树仅有一个结点)。2.在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和。3.从森林中删除选取的两棵树,并将新树加入森林。4.重复2、3...
{4,5,6,7,8}作为权值构造Huffman树,带权路径长度?
先是4和5合并为9,再就是6和7合并为13,接着是8和9合并为17,最后是13和17合并为30,所以WPL = (6+7+8)*2 + (4+ 5)*3= 69。例如:假设有n个权值,则构造出的哈夫曼树有n个叶子结点,n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为:(1) 将w1、w2、…,wn看成是有...
WPL是什么意思?
wpl怎么算如下:树的所有叶结点的带权路径长度之和,称为树的带权路径长度表示为WPL。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln)。1.什么是WPL:WPL是一种用于衡量数据集中各项权重及其对应损失的方法。它将不同数据项的重要性考虑进去,使得在计算总体损失时能更加准确地反映出...
由一组权值(2,5,4,9)对应的二叉树的带权路径长度是多少?
对于一棵有 $n$ 个叶子节点的带权二叉树,其带权路径长度(WPL)定义为每个叶子节点的权值乘以该节点到根节点的路径长度之和,即:\\text{WPL}=\\sum_{i=1}^n w_i d_i 其中,$w_i$ 表示第 $i$ 个叶子节点的权值,$d_i$ 表示第 $i$ 个叶子节点到根节点的路径长度。根据题意,给定的...
哈夫曼树的定义是:带权路径长度最小的二叉树。 我先请问:为何它是带全...
只有带权路径长度最小的二叉树,才是哈夫曼树。当然是可以证明带权路径长度最小。树的路径长度是从树根到树中每一结点的路径长度之和,在结点数目相同的二叉树中,完全二叉树的路径长度最短。结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。结点的带权路径长度:结点到树根之间的路径...
数据结构,求带权路径长度
8*2+4*3+5*3+7*2+6*2=69
二叉数带权路径长度咋算?
树的带权路径长度=所有叶子节点带权路径长度之和 即所有叶子节点的权值乘以该叶子节点所在的层次(第一层为0)之和
...2 6 10 14,以他们的叶子为结点构造哈夫曼树,计算带权路径长度...
50 21 29 11 10 15 14 5 6 7 8 2 3 上图为树,所以带权路径长度为 2x4+3x4+6x3+10x2+7x3+8x3+14x2=131
哈夫曼树是带权路径长度最短的树,路径上权值较大的结点离根较近...
在一棵树中,从一个结点往下可以达到的孩子或孙子结点之间的通路,称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1,则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值,则这个数值称为该结点的权。结点的带权路径长度为:从...
宰父欧方德:[答案] 树的带权路径长度=所有叶子节点带权路径长度之和 即所有叶子节点的权值乘以该叶子节点所在的层次(第一层为0)之和
聊城市15089181159: 求带权路径长度 - ?
宰父欧方德: 1. 先建立哈夫曼树 (33) (10) (23) (5) 5 9 14 2 3 2. 带权路劲长度为每一层权值*(层数-1)的总和 (2+3)*3+(5+9+14)*2=71 3. 详细概念和解释可去百科查看
聊城市15089181159: 求二叉树的带权路径长度? - ?
宰父欧方德: 哈弗曼树的大体形状18 (A)7 11 (B)5 6 (C)2 (D)4 带全路径长度为21
聊城市15089181159: 已知五个权值分别为9,2,5,7,14的叶子结点,试构造赫夫曼树,并求树的带权路径长度 - ?
宰父欧方德: 答案很多,下面是其中一种,带权路径长度wpl = (2 + 5) * 3 + (7 + 9 + 14) *2 = 81
聊城市15089181159: 给定一组权值W=(14.15.7.3.20.4)请构造出相应的哈夫曼树,并计算其带权的路径长度WPL? - ?
宰父欧方德:[答案] 带权的路径长度WPL=3*4+4*4+7*3+14*2+15*2+20*2
聊城市15089181159: 设一组权值集合W=(15,3,14,2,6,9,16,17)根据这些权值集合构造一棵哈夫曼树带权路径长度为多少?求 - ?
宰父欧方德:[答案] WPL=5*(2+3)+4*6+3*(9+14+15)+2*(16+17)=229
聊城市15089181159: 给定一组权W={3,5,10,12,15,22} 构造哈夫曼树,并计算它的带权外部路径长度WPL. - ?
宰父欧方德: 从根节点到各个百叶节点的路径长度与对应叶节点权值的乘度积之和内 22的路径长度是1 10、12、15的路径长度是3 3、5的路径长度是4 所以容WPL = 22 + (10 + 12 + 15) * 3 + (3 + 5) * 4 = 22 + 111 + 32 = 165
聊城市15089181159: 求二叉树的带权路径长度?有4个叶子节点A,B,C,D,分别具有权值7,5,2,4,试作图构造一相映成棵哈夫曼树,并计算出该二叉树的带权路径长度 - ?
宰父欧方德:[答案] 18 . . A(7) 11 . . B(5) 6 . . C(2) D(4)
聊城市15089181159: 有30,15,9,18,47,90,25试求哈夫曼树的带权路径长度 - ?
宰父欧方德: 哈夫曼树:234/ \90 144/ \55 89/ \ / \25 30 42 47/ \18 24/ \9 15 带权路径长度: 90*1+ 25*3 + 30 *3 + 47*3 + 18*4 + 9*5 + 15*5 = 1098 可能显示的时候空格被去掉了,树的样式可以自己再画一下
聊城市15089181159: 哈夫曼树的带权路径长度是什么? - ?
宰父欧方德:[答案] 1.树的路径长度树的路径长度是从树根到树中每一结点的路径长度之和.在结点数目相同的二叉树中,完全二叉树的路径长度最短. 2.树的带权路径长度(Weighted Path Length of Tree,简记为WPL) 结点的权:在一些应用中,赋予树中结点的一个...