Question

两道题，求详细过程，讲解的。

设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个
数,试求出n0,nk之间的关系(n0=数学表达式,数学表达式仅含nk,k和数字)
给出一组顶点（顶点值用A，B，C，D，E，F表示），其对应权值分别为2，3，1，7，8，4。请以A，B，C，D，E，F为叶子顶点构造一棵哈夫曼树，并求出它的最小带权路径长度WPL的值。

Answer 1

首先声明，我没学过数据结构，以下专业术语不正确的或者做错了那么。。。请自己翻书查相关的准确术语
nk=(k-1)n0+1
如果nk成为父节点有nk个，n0成为子节点有n0个。对于k叉树而言，每当一个子节点拓展为一个父节点时，则子节点变为父节点即ak+=1同时a0-=1，同时子节点又多了k个即an+=k，两式子联立得每拓展一次时
ak+=1 a0+=k-1
又因为树的根节点是没有父亲的，所以n0要再加1
就得到上面的关系了。

自己画画图就出来了

第二题
树的形状如下图
○
○ 8
○ 7
○ 4
○ 3
1 2
中间的线不知道怎么画，就是A的子女分别是B和8，B的子女分别是C和7，下同，最后的E的子女是1和2
WPL算法 1*5+2*5+3*4+4*3+7*2+8*1 答案自己算（如果所有的路径的权都是1的话。。）

哈弗曼数算法如下
霍夫曼算法
（1）由给定的n个权值构造具有n棵扩充二叉树的森林F，其中每一棵扩充二叉树只有一个带有权值的根结点；
（2）在F中选取两棵根结点的权值最小的扩充二叉树作为左、右子树构造一棵新的二叉树，置新的二叉树的根结点的权值为其左、右子树上根结点的权值的之和。在F中删去这两棵二叉树，把新的二叉树加入F；
（3）重复步骤（2）直到F中仅剩下一棵树为止。

反正简单的理解就是说越是小的数越是放下面，然后每个根节点下面就放一个带有权的数，另一个当然就是根节点了，然后小的放下面，大的放上面，所谓WPL就是根节点到叶节点有几条路径，简单来说就是几条线，再乘以那个叶节点上的权值，然后都加起来就可以了。哈弗曼算法是这样的，怎么证明的忘记了。。。