哈夫曼树怎么画例题,权值w={2.,3,5,7,9,12}，画出哈夫曼树，并求出其带权路径长度

哈夫曼树怎么画例题,权值w={2.,3,5,7,9,12}，画出哈夫曼树，并求出其带权路径长度详细介绍

本文目录一览： 16 28 12 6 14 24怎么画成哈夫曼树求解？

哈夫曼树是一种带权路径长度最短的树，可以用来压缩数据，其中权值越大的节点离根节点越近。
下面是将16 28 12 6 14 24这些权值画成哈夫曼树的步骤：
将这些权值从小到大排序，得到6 12 14 16 24 28。
把权值最小的两个节点（6和12）合并为一个节点，它们的权值之和作为新节点的权值，得到18。把这个新节点作为一棵树的根节点，它的两个子节点分别是之前合并的两个节点。
把权值次小的节点（14）加入这棵树中，与之前合并的节点合并，得到新的节点权值为32。
重复上述步骤，将16和18合并为34，24和28合并为52。
最后再将32和34合并为66，得到完整的哈夫曼树。
下面是6 12 14 16 24 28这些权值画成哈夫曼树的示意图：
66
/ \
32 34
/ \ / \
14 18 16 24
/ \
6 12

权值w={5,29,7,8,14,23,3,11},画出哈夫曼树。

我觉得你的是对的，哈夫曼树是不唯一的，只要得到的带权路径长度是最小的就没问题，答案是100，你的也是100，我个人认为是正确的。如果我说的不对还请帮忙纠正，一起进步
权值w={5,29,7,8,14,23,3,11},画出哈夫曼树.个人认为, 图2的画法有不妥的地方.问题点就是:结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.分析过程如下:八个权值从小到大排序是: 3 5 7 8 11 14 23 29图1 : 哈夫曼树 N100 / \ N42 N58 / \ / \ 23 N19 29 N29 / \ / \ 11 N8 14 N15 / \ / \ 3 5 7 8根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4如此类推,哈夫曼树的带权路径长度(WPL)等于29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.权值29: 10权值23: 00权值14: 110权值11: 010权值8 : 1111权值7 : 1110权值5 : 0111权值3 : 0110图2 : 哈夫曼树 N100 / \ N58 N42 / \ / \ N29 29 N19 23 / \ / \ 14 N15 8 11 / \ 7 N8 / \ 3 5根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点3的路径长度是5,结点3的带权路径长度是3*5如此类推,哈夫曼树的带权路径长度(WPL)等于29*2 +23*2 +14*3 +11*3 +8*3 +7*4 +5*5 +3*5 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.权值29: 01权值23: 11权值14: 000权值11: 101权值8 : 100权值7 : 0010权值5 : 00111权值3 : 00110从 WPL 的角度看,图1和图2的WPL都是等于271.从 哈夫曼编码 的角度看:图1, 权值29的编码是10, 权值3的编码是0110 图2, 权值29的编码是01, 权值3的编码是00110图2的权值29和权值3的编码长度相差大了一点.相比下,图1的方案更加合适,所以优先选择图1的哈夫曼树.图1和图2出现编码差异大的主要原因是:结点3和结点5组成新结点N8,那么新结点N8应该排在原有结点8的后面,还是前面?图1的做法是将新结点N8排在原有结点8的后面,所以结点7与原有结点8先合并.而图2的做法是新结点将N8排在原有结点8的前面,所以结点7和新结点N8先合并了.个人认为,应该按照图1的做法,将新结点N8排在原有结点8的后面.另外,个人认为,图1的结点11和N8的左右位置互换一下,结点23和N19左右位置互换一下,这样会更加合适,保证从左到右,结点是从小到大,让最后编码的时候,更加统一.以下是详细的构建过程:(1) 从小到大排序 3 5 7 8 11 14 23 29 (这是有序序列)(2) 每次提取最小的两个结点,取结点3和结点5,组成新结点N8,其权值=3+5=8, 取数值较小的结点作为左分支,结点3作为左分支,而结点5就作为右分支.(3) 将新结点N8放入有序序列,保持从小到大排序: 7 8 N8 11 14 23 29 [注意,新结点N8排在原结点8的后面](4) 重复步骤(2),提取最小的两个结点,结点7与结点8组成新结点N15,其权值=7+8=15, 结点7的数值较小,将结点7作为左分支,结点8就作为右分支.(5) 将新结点N15放入有序序列,保持从小到大排序: N8 11 14 N15 23 29(6) 重复步骤(2),提取最小的两个结点,N8与结点11组成新结点N19,其权值=8+11=19, N8的数值较小,作为左分支,结点11就作为右分支.(7) 将新结点N19放入有序序列,保持从小到大排序: 14 N15 N19 23 29(8) 重复步骤(2),提取最小的两个结点,结点14与N15组成新结点N29,其权值=14+15=29, 结点14的数值较小,作为左分支,N15就作为右分支.(9) 将新结点N29放入有序序列,保持从小到大排序: N19 23 29 N29 [注意,新结点N29排在原结点29的后面](10)重复步骤(2),提取最小的两个结点,N19与结点23组成新结点N42,其权值=19+23=42, N19的数值较小,作为左分支,结点23就作为右分支.(11)将新结点N42放入有序序列,保持从小到大排序: 29 N29 N42(12)重复步骤(2),提取最小的两个结点,结点29与N29组成新结点N58,其权值=29+29=58, 结点29与N29的数值相同,将原结点29作为左分支,N29就作为右分支.(13)将新结点N58放入有序序列,保持从小到大排序: N42 N58(14)重复步骤(2),提取剩下的两个结点,N42与N58组成新结点N100,其权值=42+58=100, 数值较小的N42作为左分支,N58就作为右分支. 最后得到"哈夫曼树": N100 / \ N42 N58 / \ / \ N19 23 29 N29 / \ / \ N8 11 14 N15 / \ / \ 3 5 7 8带权路径长度(WPL):根结点N100到结点29的路径长度是2,结点29的带权路径长度是29*2根结点N100到结点23的路径长度是2,结点23的带权路径长度是23*2根结点N100到结点14的路径长度是3,结点14的带权路径长度是14*3根结点N100到结点11的路径长度是3,结点11的带权路径长度是11*3根结点N100到结点8的路径长度是4,结点8的带权路径长度是8*4根结点N100到结点7的路径长度是4,结点7的带权路径长度是7*4根结点N100到结点5的路径长度是4,结点5的带权路径长度是5*4根结点N100到结点3的路径长度是4,结点3的带权路径长度是3*4所以,哈夫曼树的带权路径长度(WPL)等于29*2 + 23*2 + 14*3 + 11*3 + 8*4 + 7*4 + 5*4 + 3*4 = 271哈夫曼编码:规定哈夫曼树的左分支代表0,右分支代表1.从根结点N100到结点29,先经历右分支,再经历左分支,结点29的编码就是10从根结点N100到结点23,先经历左分支,再经历右分支,结点23的编码就是01从根结点N100到结点14,经历两次右分支,再经历左分支,结点14的编码就是110如此类推,得出所有结点的"哈夫曼编码":权值29: 10权值23: 01权值14: 110权值11: 001权值8 : 1111权值7 : 1110权值5 : 0001权值3 : 0000

怎样构造哈夫曼树？

问题一：哈夫曼树的构造 10分 第一步：排序 2 4 5 9
第二步：挑出2个最小的 2 4 为叶子构造出
6
2 4
第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：
11
6 5
2 4
第四步：继续生长
20
11 9
6 5
2 4
权值为 2*3+4*3+5*2+9*1=37
也可以20+11+6=37
例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2

问题二：怎样构造合适的哈夫曼树？ 5分 来自百度百科：哈夫曼树构造方法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
简单的说，就是选择两个权值最小的节点，构造一棵树，树的根权值是两个权值最小的节点之和，将新的权值节点放回序列，继续按照上述方法构造，直到只有一棵树为止，这样的树其WPL最小。

问题三：哈夫曼树怎样构造编码？ 先编造哈夫曼树，哈夫曼树构造规则：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止

构造完成之后，从这个树根结点开始，默认左子树为0，右子树为1，直到叶子结点为止，叶子结点的编码就是需要的编码。
举例
知字符A B C D E F的权值为8 12 5 20 4 11
哈夫曼树就是：
60
/ \
23 37
/ \ / \
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
编码就是 A：100， B：01， C：1011， D： 11， E：1010 ，F：00

问题四：如何构造哈夫曼树，详细点 要方法 还是要代码

问题五：哈夫曼树的构造算法 5分 /*------------------------------------------------------------------------- * Name: 哈夫曼编码源代码。 * Date: 2011.04.16 * Author: Jeffrey Hill+Jezze(解码部分) * 在 Win-TC 下测试通过 * 实现过程：着先通过 HuffmanTree() 函数构造哈夫曼树，然后在主函数 main()中 * 自底向上开始(也就是从数组序号为零的结点开始)向上层层判断，若在 * 父结点左侧，则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。 *------------------------------------------------------------------------*/#include #include #define MAXBIT 100#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1 typedef struct { int bit[MAXBIT]; int start;} HCodeType; /* 编码结构体 */typedef struct{ int weight; int parent; int lchild; int rchild; int value;} HNodeType; /* 结点结构体 */ /* 构造一颗哈夫曼树 */void HuffmanTree (HNodeType HuffNode[MAXNODE], int n){ /* i、j： 循环变量，m1、m2：构造哈夫曼树不同过程中两个最小权值结点的权值， x1、x2：构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/ int i, j, m1, m2, x1, x2; /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */ for (i=0; i>

问题六：数据结构怎样构造三叉哈夫曼树？ 哈夫曼树构造是将所有的点看做森林的树，选择两个最小权值的点来构造树，直到森林只有一个树为止，这样推三叉哈夫曼树是选择三个最小权值的点来构造树，作为左中右三个子树，根结点的权值是三个结点的权值的和。

问题七：3 4 5 6 8 9怎么构造哈夫曼树，怎么我总是构造不对，是这样的么 对的，不过通常习惯性会从左到右，从下到上来构造

问题八：哈夫曼树的构造 10分 第一步：排序 2 4 5 9
第二步：挑出2个最小的 2 4 为叶子构造出
6
2 4
第三步：判断 6 不大于 5或9（剩余叶子中最小的2个）=》 同方向生长，得出：
11
6 5
2 4
第四步：继续生长
20
11 9
6 5
2 4
权值为 2*3+4*3+5*2+9*1=37
也可以20+11+6=37
例题：6、13、18、30、7、16
排序 6 7 13 16 18 30
13
6 7
26 26大于16或18 =》分支生长
13 13
6 7
26 34
13 13 16 18
6 7
此时最小的2个数为 26 30 得出
56 34
26 30 16 18
13 13
6 7
最后得出 90
56 34
26 30 16 18
13 13
6 7 权值 219
90+56+26+13+34 or 6*4+7*4+13*3+30*2+16*2+18*2

问题九：怎样构造合适的哈夫曼树？ 5分 来自百度百科：哈夫曼树构造方法：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
简单的说，就是选择两个权值最小的节点，构造一棵树，树的根权值是两个权值最小的节点之和，将新的权值节点放回序列，继续按照上述方法构造，直到只有一棵树为止，这样的树其WPL最小。

问题十：哈夫曼树怎样构造编码？ 先编造哈夫曼树，哈夫曼树构造规则：
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止

构造完成之后，从这个树根结点开始，默认左子树为0，右子树为1，直到叶子结点为止，叶子结点的编码就是需要的编码。
举例
知字符A B C D E F的权值为8 12 5 20 4 11
哈夫曼树就是：
60
/ \
23 37
/ \ / \
F(11) B(12) 17 D(20)
/ \
A(8) 9
/ \
E(4) C(5)
编码就是 A：100， B：01， C：1011， D： 11， E：1010 ，F：00

权值w={2.,3,5,7,9,12}，画出哈夫曼树，并求出其带权路径长度

我认为应该这样算的。
哈夫曼树见图。用word随便画的，比较难看。
带权路径长度 （2+3）*3+(5+7+9)*2+12*1=15+42+12=69
其实你可以根据下面的直接求。
哈夫曼树的构造
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树

权值w={5，29,7,8,14,23,3,11}，画出哈夫曼树

先最小的两个，5和3 变成权值为8一棵树
再选最小的两个为7 和8，这个8也可以是5和3的那个组成两个8选一个，变成权值15的一棵树
按这个规律
①首先把 n 个叶子结点看做 n 棵树（仅有一个结点的二叉树），把它们看做一个森林。
②在森林中把权值最小和次小的两棵树合并成一棵树，该树根结点的权值是两棵子树权值之和。这时森林中还有 n-1 棵树。
③重复第②步直到森林中只有一棵为止。

某通信电文有A B C D E F 六个字符组成，在电文中出现的次数分别为16 ，5 ，9，3，20，1，画哈夫曼树

哈夫曼树的构造规则为： 　
(1) 将16 ，5 ，9，3，20，1看成是有n 棵树的森林(每棵树仅有一个结点)； 　　
(2) 在16 ，5 ，9，3，20，1森林中选出两个根结点的权值最小的树合并，（即1,3）　
作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树（即1,3），并将新树（4）加入森林； 　权值数列为(4,5,9,16,20)　
(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树
哈夫曼树编码
在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码
A10 B1111 C110 D11101 E0 F11100

2，3，6，7，14，19，22怎么画成哈夫曼树求解？

画成哈夫曼树：
假设有n个值，则构造出的哈夫曼树有n个叶子结点。 n个值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的值最小的树合并，作为一棵新树的左、右子树，且新树的根结点值为其左、右子树根结点值之和；
扩展资料
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。
解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
如图。
如有帮助，望采纳
哈夫曼树为：
100
/ \
60 40
/ \ / \
28 32 19 21
/ \
11 17
/ \ / \
5 6 7 10
/ \
2 3
编码左子树/为0 右子树\为1
a:0010,b10 c 00000，其他自己看一下
哈夫曼树为：
100
/ \
60 40
/ \ / \
28 32 19 21
/ \
11 17
/ \ / \
5 6 7 10
/ \
2 3
编码左子树/为0 右子树\为1
假设有n个值，则构造出的哈夫曼树有n个叶子结点。 n个值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
(2) 在森林中选出两个根结点的值最小的树合并，作为一棵新树的左、右子树，且新树的根结点值为其左、右子树根结点值之和；
扩展资料：
哈夫曼树也可以是k叉的，只是在构造k叉哈夫曼树时需要先进行一些调整。构造哈夫曼树的思想是每次选k个权重最小的元素来合成一个新的元素，该元素权重为k个元素权重之和。但是当k大于2时，按照这个步骤做下去可能到最后剩下的元素少于k个。
解决这个问题的办法是假设已经有了一棵哈夫曼树(且为一棵满k叉树)，则可以计算出其叶节点数目为(k-1)nk+1,式子中的nk表示子节点数目为k的节点数目。
参考资料来源：百度百科-哈夫曼树

数据结构，如题求问

对频率进行升序排序：6，7，14，19，32，22
画出哈夫曼树如下：
所以频率为7的编码为1110，频率为32的编码为10
构造哈夫曼树的方法：
每次从待编码的数组中取出最小的两个数，让他们向上生长，其值为两个数的和，然后将这个和加入待编码的数组并删除最小的那两个数。

赫夫曼树

注：第一题 huffman 树以及 huffman编码
我将第二题与第三题与用邻接矩阵存储图相关的操作放在了一起完成
第三题则是利用邻接表
1.第一题
#include

#include

#include

#include

#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

parent==-1)

{

m2=m1;

m1=(h+j)->weight;

m2_pos=m1_pos;

m1_pos=j;

}

else if((h+j)->weight

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

#include

#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

VertexNum;i++)

{

if(G->vertex[i]==v)

{

k=i;

break;

}

}

return(k);

}

void init(adjacentMatrix *G)

{

int i,j;

for(i=0;i

VertexNum;i++)

{

for(j=0;j

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

VertexNum;i++)

{

scanf("%c",&G->vertex[i]);

}

getchar();

for(i=0;i

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

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

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

VertexNum;i++)

{

odsum=0;

idsum=0;

for(j=0;j

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

VertexNum;i++)

{

printf("%8c",G->vertex[i]);

}

printf("\n");

for(i=0;i

VertexNum;i++)

{

for(j=0;j

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

#include

#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

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

vexnum;i++) // 生成表头结点表

{

scanf("%c",&G->vertex[i].data);

G->vertex[i].firstarc=NULL;

}

getchar();

for(i=0;i

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

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

vexnum;i++) // 生成表头结点表

{

insum=0;

for(j=0;j

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);

}

</len;j++)
</strlen(characters);i++)
</leaves*2-1;i++)
</len;j++)
</leaves;i++)

</leaves+i;j++)