设有一棵k叉树,其中只有度为0和k两种结点,设n0,nk分别表示度为0和度为k的结点个

首先声明,我没学过数据结构,以下专业术语不正确的或者做错了那么...请自己翻书查相关的准确术语
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就是根节点到叶节点有几条路径,简单来说就是几条线,再乘以那个叶节点上的权值,然后都加起来就可以了.哈弗曼算法是这样的,怎么证明的忘记了...