求带权路径长度

带权9.1.3.5.6的五个叶子生成的哈夫曼树，带权路径长度怎么算~

五个叶子的权值是 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;}

1. 先建立哈夫曼树

   （33）

   （10）        （23）

   （5）        5        9        14

   2       3    

2. 带权路劲长度为每一层权值*（层数-1）的总和
   （2+3）*3+（5+9+14）*2=71

3. 详细概念和解释可去百科查看
   

根据哈夫曼树的原理（即最优二叉树）：WPL = 9 * 2 + 5*3 + 3*4 + 2*4 = 53

---

聊城市15089181159： 二叉数带权路径长度咋算? - ？
宰父欧方德：[答案] 树的带权路径长度=所有叶子节点带权路径长度之和 即所有叶子节点的权值乘以该叶子节点所在的层次(第一层为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) 结点的权:在一些应用中,赋予树中结点的一个...